4

4 行と 4 列のチェッカー ボードがあるとしNます。マトリックスの各セルには値があります。ボード2Nに (それぞれが 1 つのセルに) 配置する必要があるトークンを指定すると、マトリックスのセル内のすべての値の合計が可能な限り大きくなります (最大値)。

トークンを配置する際の制限は、2 つのトークンを水平方向または垂直方向に隣接させることはできません。

2Nすべてのトークンを配置する必要はありません。

トークンを列に配置する正当な方法は 8 つありNます。そのため、それぞれがオプションを記述するときのサイズで 8 つの配列を定義します。

とにかく、動的計画法を使用して、問題の再帰方程式を作成する必要があります。

私が思いついた：

A(i,j) = max { A(i,j) , A(i,j) + max { A(i-1,j-1) , ... , H(i-1,j-1) } } , B(i,j) = .... , H(i,j) = ...

Aが最初の配列で、Hが 8 番目の配列である場合。

さて、私の再帰方程式は良くないと思います。たとえそうであったとしても、再帰方程式に条件 (2 つのトークンを水平または垂直に隣接させることはできません) を追加する方法がわかりません。

誰でも助けようとすることができますか？

4

2 に答える 2

2

そうです、列にトークンを配置するには 8 つの方法があります。

A B C D E F G H
e *       *   *
m   *       *
p     *   *
t       *   * *
y

これで、他の列の後に特定の列のみを持つことができます。例えば：

  1. A任意の列の隣になることができます。
  2. 自分自身の隣人にしかAなれません。
  3. BCおよびの隣人になることはできますがG、別のBまたはFまたはHの隣人になることはできません。
  4. HA、CまたはDなどの隣人にしかなれません。

注意すべきことの 1 つは、指定された列が と の両方にA隣接している場合に役立つ可能性があることです。FG

したがって、（無向）グラフがあります。

  A B C D E F G H
A + + + + + + + +
B + - + + + - + -
C + + - + + + - +
D + + + - + - + +
E + + + + - + - -
F + - + + + - + -
G + + - + - + - -
H + - + + - - - -

上は入射行列です。

その後、列がタイプトークンの配置で終了した場合に、最初の列A(i)から取得できる最大の合計を定義します。、、 ...、についても同様です。ii thABCH

次に、再帰式があります。

X(i+1) = {max Y(i) where X and Y can be neighboring columns} + 
         {sum of the cells in the i+1 column for placement X}

ここでXは、考えられるすべての配置A、B、C、 ... を実行しHます。

初期値はA(0) = 0, B(0) = 0, ..., H(0) = 0.

最終的な答えはmax{ A(N), B(N), C(N), D(N), ..., H(N) }です。

ノート：

上記は解決策またはアイデアであり、実装は異なる場合があります。たとえば、すべてをハードコーディングできます (Board[i][j]がボードに配置された値であると仮定すると、インデックスは から始まります0):

F(i+1) = max{ A(i), C(i), E(i), G(i) } +  // This is from the matrix above
         Board[0][i+1] + Board[2][i+1]    // This is from the definition of F type column

そして、すべての文字について同様です。プログラムで実際のエンティティとして発生行列を使用する必要はありません。式を作成するときに念頭に置いてください。

于 2013-05-11T11:18:20.650 に答える