6

装身具 (ランダムな量) で満たされたx個のビンの行があるとします (各ビンにいくつの装身具があるかがわかります)。これで、自分の番になったときにどちらかの端からビンを選ぶことができる 2 人のプレーヤーがいます。彼らは順番を忘れることはできません。プレーヤーが最大限の装身具を獲得するための戦略を考え出します。

×は偶数です。

これは np 完全な問題ですか? ブールSATに似ていますか？

4

4 に答える 4

5

いいえ、動的計画法で簡単に解決できますO(x^2)。ここで問題 10 を見てください。

于 2010-06-25T10:02:37.453 に答える
5

これは非常に単純な問題であり、NP 完全ではありません。これはアルゴリズムの簡単な説明です。動的計画法に基づいています。

Can[i] - 装身具の数を格納する配列。
F[i,j] - i から j までの缶のみが利用可能である場合に最適な動きを決定する配列。0 は左側から取ることを意味し、1 は右側から取ることを意味します。
G[i,j] - 移動の「良さ」が格納される配列。 

for (i=1 to n) F[i,i] = 0
for (i=1 to n) G[i,i] = Can[i]

for (i=1 to n-1)
   for (j=1 to n-i)
       tmp1 = Can[j] - G[j+1,j+i]
       tmp2 = Can[j+i] - G[j,j+i-1]
       if (tmp1>tmp2)
       {
             F[j,j+i] = 0;
             G[j,j+i] = tmp1;
       }
       else
       {
             F[j,j+1] = 1;
             G[j,j+i] = tmp2;
       }

コメント不足で申し訳ありませんが、動的計画法に関するいくつかの記事を読むと、問題なく取得できます。

于 2010-06-25T10:07:27.277 に答える
0

最初のプレーヤーが引き分け/勝利戦略を持っていることは明らかです。彼がしなければならないことは、奇数の位置のビンと偶数の位置のビンの合計が大きいかどうかを確認することだけです。そうすれば、対戦相手に「負けた」パリティのビンを拾わせるようなプレイを簡単に行うことができます。

例えば：

2,6,11,4,7,3

ここでは奇数の位置の方が有利なので (20 対 13)、プレーヤー 1 は 2 を選択する必要があります。次に、プレーヤー 2 は偶数の位置にある 6 または 3 のいずれかを選択する必要があります。3 が選択された場合、プレーヤー 1 は 7 を選択する必要があります。実際には、プレイヤー 1 は常に対戦相手が選んだポジションの次のポジションを選択する必要があり、引き分けか勝利が保証されます。

于 2010-06-25T22:10:53.483 に答える
0

この問題は、ポイントの下限を簡単に導出できるため、アルファ ベータ プルーニングに最適なようです。プレイヤーが偶数のビンに直面していると仮定します。次に、すべてのビンを偶数またはすべて奇数の位置にする方法でプレーできます。

1 0 1 0 1 0 があるとすると、彼は左側の 1 を取ることができ、対戦相手が何をしようとも、彼は 1 を拾い続けます。

したがって、計算しやすい下限は、偶数位置のすべてのビンの合計と奇数位置のすべてのビンの合計の最大値です。

「奇数」プレーヤーの場合は、(長さ + 1)/2 の最小値の合計を取ることができます。これは、「偶数」プレーヤーの範囲ほどではありませんが、計算も簡単です。

これらの境界を使用すると、実際のアプリケーションでは検索ツリーがまばらになると思います（ただし、このタイプの問題の「病理学的」な反例をいつでも見つけることができると思います）ので、解決策は非常に高速になるはずです。

于 2010-06-25T11:43:41.537 に答える