私の問題はここの問題と似ていますhttps://cs.stackexchange.com/questions/2244/need-a-np-complete-proof-on-an-exampleですが、少し異なります。
これが私の問題です：
A、B、Cの3つの島があり、扇型の筏がたくさんあります。A-->B-->C から橋を架ける必要があり、各部分に必要なラフトの数は既にわかっています。たとえば、AB を接続するには 4 つのラフトが必要であり、BC を接続するには 3 つのラフトが必要です。
これらの筏はもともと別の位置にあり、コストをかけずに回転できます。興味深いのは、必要に応じてそれらを重ねることができることです。1 台のラフトが移動する距離は、重心の元の位置とその展開位置の間の距離として計算できます。
目的は、橋 A-->B-->C を実現し、橋の各部分の筏の正確な数を使用して、筏を移動する最小の合計距離を持つ解を見つけることです。
私は自分の質問を示すために次の図を使用しました。
この図から、配置が直線ではない可能性があり、筏が別の筏と重なる可能性があることがわかります。
これらの筏の候補地が多すぎます。問題はNPCのようです。自分が正しいかどうか、NPC であることを証明する方法がわかりません。誰でもそれを解決する方法を知っていますか? ありがとう！