1

これは単純なゲームです:
セット A={a1,...,an} があり、対戦相手はセットの最初または最後の要素のいずれかを選択でき、最後により多くの数を集めた人が勝ちます。ここで、各参加者が最善を尽くしたとします。私がする必要があるのは、スコアを推定する動的アルゴリズムを作成することです。
どんなアイデアや手がかりも本当に感謝しています。

4

4 に答える 4

2

ここにヒントがあります。動的計画法アルゴリズムを作成するには、通常、再帰が必要です。与えられた

A={a1,...,an}

再発は次のようになります

f(A)= max( f({a1,...,a_n-1}) ,  f({a2,...,a_n}) )
于 2012-11-29T22:41:27.193 に答える
1

実際には、dfb によって与えられる再帰関係は、正しい次善の構造につながらないため、正しい答えにつながらない可能性があります。プレーヤー A がゲームを開始すると仮定します。彼にとっての問題の構造は [a1,a2,...an] です。 a1 または an のいずれかの要素を選択した後、そのプレーヤー B がプレイする順番になり、その後、その手がプレーヤーになります。 Aさんの動き。したがって、2 つの手の後、プレーヤー A の番が再び来ます。これは、彼にとって正しいサブ問題になります。正しい再帰関係は、次のようになります。

i から j までの要素が残っているとします:

A(i,j)= max(min( A(i+1,j-1),A(i+2,j)+a[i] ), min(A(i,j-2),A(i+1,j-1))+a[j])

次のリンクを参照してください: http://people.csail.mit.edu/bdean/6.046/dp/

于 2012-11-30T10:29:22.227 に答える
0

上記のゲームの明示的な解決策を見つけるのは簡単なので、実際には動的計画法は必要ありません。

ケースnは偶数またはn=1です。2番目に移動するプレーヤーは常に負けます。

ケースnが奇数でn>1。次の2つのシナリオのいずれかが発生した場合、2番目のプレーヤーは勝利戦略を持っています。

  1. インデックスが偶数の要素は、インデックスが奇数のすべての要素よりも合計が大きくなります

  2. 最後を除くすべての奇数要素は、残りのすべてよりも合計が大きく、最初を除くすべての奇数要素は、残りのすべてよりも合計が大きくなります。

証明スケッチ：

ケースnは偶数またはn=1です。SoddとSevenを、偶数/奇数のインデックスを持つすべての要素の合計とします。Sodd> Sevenと仮定すると、それ以外の場合も同じ議論が成り立ちます。最初のプレイヤーは、すべての奇数のインデックス付きアイテムを取得するような方法でプレイできるため、勝利戦略を持っています。

nが奇数で、n>1の場合も直接解決できます。実際、最初のプレイヤーには2つのオプションがあり、セットの最初または最後の要素を取得できます。残りの要素のうち、奇数と偶数のインデックスで2つのサブセットを分割します。上記の議論により、2番目のプレーヤーは合計が最大のサブセットを取得します。ツリーゲームを展開すると、上記のステートメントになります。

于 2012-11-29T23:17:40.393 に答える
0

サンプルコード

1 番目と 2 番目のプレーヤーの最適なスコアを計算する Python コードを次に示します。

A=[3,1,1,3,1,1,3]

cache={}
def go(a,b):
    """Find greatest difference between player 1 coins and player 2 coins when choosing from A[a:b]"""
    if a==b: return 0 # no stacks left
    if a==b-1: return A[a] # only one stack left
    key=a,b
    if key in cache:
        return cache[key]

    v=A[a]-go(a+1,b) # taking first stack
    v=max(v,A[b-1]-go(a,b-1)) # taking last stack

    cache[key]=v
    return v

v = go(0,len(A))
n=sum(A)
print (n+v)/2,(n-v)/2

反例

コードには、この質問に対する他の回答の 1 つに対する反例が含まれていることに注意してください。

[3,1,1,3,1,1,3] の場合を考えてみましょう。

対称性により、最初のプレイヤーは常に [1,1,3,1,1,3] のパターンから離れます。

この場合、偶数要素の合計は 1+3+1=5 ですが、奇数要素の合計は 1+1+3=5 です。したがって、この位置からは 2 番目のプレーヤーが常に 5 を獲得し、最初のプレーヤーは常に 5 を獲得します。は常に 5 を獲得するため、最初のプレーヤーが勝ちます (最初の移動からの 3 に加えて 5 を獲得するため)。

ただし、2 番目のプレーヤーが実際にはより多くを獲得できるため、このロジックには欠陥があります。

First player takes 3, leaves [1,1,3,1,1,3] (only choice by symmetry)
Second player takes 3, leaves [1,1,3,1,1]
First player takes 1, leaves [1,3,1,1] (only choice by symmetry)
Second player takes 1, leaves [1,3,1]
First player takes 1, leaves [3,1] (only choice by symmetry)
Second player takes 3, leaves [1]
First player takes 1

したがって、全体として、最初のプレーヤーは 3+1+1+1=6 を取得し、2 番目のプレーヤーは 3+1+3=7 を取得し、2 番目のプレーヤーが勝ちます。

欠点は、2 番目のプレーヤーがすべての偶数またはすべての奇数の位置を獲得するようにプレーできることは事実ですが、これは最適なプレーではなく、場合によっては実際にはこれよりもうまくいく可能性があることです。

于 2012-11-30T09:25:55.903 に答える