2

ゲームをしましょう:

n 枚のコインが一列に並んでいます。i 番目のスタックは d_i コインで構成されます。2 人のプレーヤー: Player1、Player2 が交互に移動します。自分の番のプレーヤーは、最初のスタックまたは最後のスタック、またはその両方しか取得できません。コインがなくなるとゲーム終了。各プレイヤーは、最後にできるだけ多くのコインを持ちたいと考えています。Player1 が起動します。

私は、両方のプレイヤーが最適なプレイをしたときに、ゲームの最後に各プレイヤーが持っているコインの数をカウントするアルゴリズム (貪欲なアルゴリズムのように聞こえます) について疑問に思っていました。

そのようなアルゴリズムにアプローチする方法がわかりません。戦略を推測するだけですか、それともそれを推測する方法はありますか? それとも、アルゴリズムを実装するにはあまりにも奇妙な問題でしょうか?

例 (1 番目から n 番目までのスタック内のコイン):

1、100、1 - プレイヤーはそれぞれ 2 枚と 100 枚のコインを持っています (残念ながら、最初のプレイヤーは最初と最後のスタックしか取得できません - 2 番目のプレイヤーは常に 100 コインのスタックを取得します)

1, 1, 100, 1, 1, 5 - プレイヤーはそれぞれ 8 枚と 101 枚のコインを持っています (これは最適なゲームの後であると思います - 最初に 5 と 1 を取り、次に 1 を取り、player1 が 100 コインでスタックを取得するのを防ぎます。最初の移動で 6 枚未満のコインしか持っていない場合、彼は常に 8 枚未満のコインしか持っていません)。

問題を十分に特定したことを願っています。面白いことに同意しますか？:) 誰か助けてくれませんか？

4

2 に答える 2

1

@Peterの動的プログラミング ソリューションへの追加: 再発は

次のようになると思います。それで、

A[i,..j]
dp[i, j]

dp[i, j] = MAX {
                MIN( dp[i+2, j], dp[i+1, j-1], dp[i+2, j-1]) + A[i], //Case when Player2 will try to make the most of it if Player1 picks ith coin.
                MIN( dp[i+1, j-1], dp[i, j-2], dp[i+1, j-2]) + A[j], //Case when Player2 will try to make the most of it if Player1 picks the jth coin.
                MIN( dp[i+2, j-1], dp[i+1, j-2], dp[i+2, j-2]) + A[i] + A[j] // Case when Player2 will try to make the most of it when Player1 picks both the ith and jth coins.
               }

N^2 の可能なゲーム状態しかないためです。サイズ N^2 の dp テーブルを埋めることで実装できます。

C++ ファン向け:

#include<iostream>
using namespace std;
int Solve(int A[], int N, int **dp, int i, int j){
        if(dp[i][j] != -1)
                return dp[i][j];
        if(j<i)
                return 0;
        else if(j==i)
                return A[i];
        else if( (j-i) == 1)
                return (A[i] + A[j]);
        else{
                int opt1 = min(Solve(A, N, dp, i+2, j), Solve(A, N, dp, i+1, j-1));
                opt1 = min(opt1, Solve(A, N, dp, i+2, j-1));
                int opt2 = min(Solve(A, N, dp, i+1, j-1), Solve(A, N, dp, i, j-2));
                opt2 = min(opt2, Solve(A, N, dp, i+1, j-2));
                int opt3 = min(Solve(A, N, dp, i+2, j-1), Solve(A, N, dp, i+1, j-2));
                opt3 = min(opt3, Solve(A, N, dp, i+2, j-2));
                int res = max(opt1+A[i], opt2+A[j]);
                res = max(res, opt3+A[i]+A[j]);
                dp[i][j] = res;
                return res;

        }
}
int main(){
        int N;
        int A[N];
        cin >> N;
        for(int i=0; i<N; ++i)
                cin >> A[i];
        int **dp;
        dp = new int* [N];
        for(int i=0; i<N; ++i)
                dp[i] = new int[N];
        for(int i=0; i<N; ++i)
                for(int j=0; j<N; ++j)
                        dp[i][j] = -1;
        Solve(A, N, dp, 0, N-1);
        cout << dp[0][N-1] << endl;
        for(int i=0; i<N; ++i)
                delete [] dp[i];
        delete []dp;
        return 0;
}

また、@Peterが指摘したように、2 番目の例の分析は間違っています。プレイヤー 1 は、102 コインを獲得してそのゲームに勝つという戦略を実際に持っています。

于 2012-11-26T22:20:27.330 に答える
0

これは、a から b-1 の範囲のスタックのみが存在する場合に最適な戦略は何かという部分問題を解くことにより、O(n^2) の動的計画法を介して解決できます。

Python コード:

A=[1, 1, 100, 1, 1, 5]
#A=[1, 100, 1]

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
    v=max(v,A[a]+A[b-1]-go(a+1,b-1)) # taking both stacks

    cache[key]=v
    return v

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

これは、あなたの 2 番目のケースの最適なゲームは、実際には最初の人が一番左の 1 を取ることであるということです。それ以降、彼は 100 を取ることを保証できるので、彼が勝ちます。

(プレイヤー 1 は 102 勝、プレイヤー 2 は 7 勝)

O(n^2) 個のサブゲームがあるため、このアルゴリズムには O(n^2) の時間がかかります

サブゲーム (および最適な最初のプレーヤー/2 番目のプレーヤーのコイン) は次のとおりです。

 [1, 5] 6 0
 [1, 1] 2 0
 [1, 100] 101 0
 [100, 1] 101 0
 [1, 1] 2 0
 [1, 100, 1] 2 100
 [1, 1, 5] 6 1
 [100, 1, 1] 101 1
 [1, 1, 100] 101 1
 [100, 1, 1, 5] 105 2
 [1, 100, 1, 1] 101 2
 [1, 1, 100, 1] 101 2
 [1, 100, 1, 1, 5] 7 101
 [1, 1, 100, 1, 1] 102 2
 [1, 1, 100, 1, 1, 5] 102 7

たとえば、小規模なゲームの最適なプレイをすべて見つけて、[1,1,100,1,1,5] の最適なプレイを見つけたいとします。

私たちがすることは、それぞれの動きを順番に検討することだけです:

  1. 最初のスタックを取り、これで 1 を獲得し、[1,100,1,1,5] という部分問題からわかっているゲームを終了すると、合計 102 で 101 を獲得します。
  2. 最後のスタックを取り、これで 5 を獲得し、[1,1,100,1,1] でゲームを終了すると、さらに 2 を獲得して合計 7 を獲得します。
  3. 両方のスタックを取り、これで 6 を獲得し、ゲーム [1,100,1,1] を終了します。プレーヤー 2 が最適にプレイした場合、さらに 2 つしか獲得できず、合計 8 になります。

したがって、最善の方法は、最初のスタックのみを取得することです。

于 2012-11-26T20:04:40.883 に答える