0

たとえば、一連の数字がある 2 プレーヤーのゲームがあります2 -6 12。それらがカードに書かれているとしましょう。

ゲームは順番に時間がかかります。各ターン プレイヤーは、シーケンスの最初または最後から正確に 1 枚のカードを取得する義務があります (スキップなし)。最後のカードが取られた後、ゲームは終了します。目標は、できるだけ高い正のスコアでゲームを終了することです (スコアは、プレイヤーが取ったカードのすべての数字の合計です)。また、両方のプレーヤーが最適な戦略を使用してプレイしていることもわかっています (利益を最大化するため)。彼らが最終的にどのスコアに到達するかを言わなければなりません。

最適な戦略がどのように見えるか考えていますか?

これまでの私の研究：

1-3 cards is trivial
{a}, no choice take a;
{a,b} take max(a,b) reduces to problem {a}
{a,b,c} take max(a,c) reduces to problem {a,b}
4 cards : {a,b,c,d}
if (a + max(c, min(b,d)) > d + max(b, min(a,c)))
    take a;
else
    take d;

私が取ることに決めた場合a、対戦相手は 3 枚のカードの戦略が示すように max(b,d) を取るので、私がしなければならないことは (対戦相手のターン中に「安全」である) から最大のカードを取り、 のカードcから小さくすることです。より大きなものを取るでしょう。との双子の状況。しかし、n-cards の場合に (可能であれば) 展開する方法がわかりません。bdd

手がかりはありますか？

4

4 に答える 4

1 
//globals
int[N] cards;
int[N][N] v;  //initialized to 0
int[N][N] sum; // precomputed such that sum(i,j)=cards[i]+...+cards[j]

void updateValue(int i,int j){
    int left=cards[i]+sum(i+1,j)-v(i+1,j);
    int right=cards[j]+sum(i,j-1)-v(i,j-1);
    v[i,j]=max(left,right);
}

void do(){
    for (int d=1;d<N;d++)
        for (int i=0;i<N-d;i++)
            updateValue(i,i+d);  
}

答えは値[0、N-1]になります

次のことに注意することで、メモリ使用量を改善できます。v を大きな正方形のテーブルとして見ると、上三角の半分を埋めます。外側のループの d の値ごとに、[0,d] から [Nd,N-1] までの対角線を埋めます。ここで、この対角線を埋める間、その前の最後の対角線の値のみを使用することに注意してください。そのため、以前のすべての値をメモリに保持する必要はありません。

于 2013-04-06T04:58:30.610 に答える
0

一見、Knackpack の問題を思い出すのですが、それが再帰的な問題であることに気付きました。OCaml をご存知ですか？この問題について考える方法は、「関数のセット」の観点からです。

基本的なケースから始めて、基本的な関数を定義する必要があります。

e.g. f1(a) -> a
     f2(x, y ) -> max(x,y)
     f3(x, y, z) -> max(f(x,y),z)

次に、次のようなより複雑なケースを定義する必要があります。

if (a + max(c, min(b,d)) > d + max(b, min(a,c)))
    take a;
else
    take d;

これは、前に定義した最大値と最小値を使用する 4 つの入力関数のように見えます。このようなもの：

f2 (a, b,c, d) -> if (a + max(c, min(b,d)) > d + max(b, min(a,c))) then true, else false
f3(a, b,c, d) -> if(f2(a,b,c,d) then a else d

必要に応じて「基本的な」関数 f2、f3 などを定義し、入力値を他の関数の出力に置き換える必要があります。

これが解決策ではないことは理解していますが、希望は再帰的な方法で推論を開始するのに十分なヒントです。

于 2013-04-03T01:25:28.593 に答える
0

私はこのようなものがうまくいくと思います:

int[] cards;

int low = 0;
int high = cards.length - 1;

int bestScore(int low, int high)
{
  if (low > high)
    return 0;

  // our best score is our immediate score minus the opponents best response
  int lowScore = cards[low] - bestScore(low + 1, high);
  int highScore = cards[high] - bestScore(low, high - 1);

  if (lowScore >= highScore)
    return lowScore;
  else
    return highScore;
}

int bestMove(int low, int high)
{
  int lowScore = cards[low] - bestScore(low + 1, high);
  int highScore = cards[high] - bestScore(low, high - 1);

  if (lowScore >= highScore)
    return low;
  else
    return high;
}
于 2013-04-03T01:31:40.857 に答える
0

シーケンスの長さが偶数の場合の答え:

最初のプレーヤーは常に負けない戦略を持っています。重要な観察事項は、最初のプレーヤーは、必要に応じて偶数の場所のすべての数字を収集でき、必要に応じて奇数の場所のすべての数字を収集できることです。したがって、彼はどちらの合計が大きいかを事前に確認する必要があります。

シーケンスが {x_1, x_2, ...,x_n} の場合、n=2k

計算: A=x_1+x_3_...x_2k-1 および B=x_2+x_4+...+x_2k

A>=B の場合、x_2k をピックすることから始めます。対戦相手が何をしようと、最初のプレイヤーはいつでも i に対して x_2i をピックできます。A< B の場合、x_1 をピックすることから始めます。対戦相手が何をしようと、最初のプレイヤーはいつでも i に対して x_2i+1 をピックできます。

于 2013-04-03T20:35:35.287 に答える