4

给定一个有 4 行和 4 列的棋盘N。矩阵中的每个单元格都有一个值。给定2N需要放置在板上的标记（每个标记在单个单元格上），因此矩阵单元格中所有值的总和将尽可能大（最大值）。

放置令牌的限制是两个令牌不能水平或垂直相邻。

您不必放置所有2N令牌。

有八种合法的方式将标记放在一列中，所以我定义了 8 个数组，N每个数组的大小都描述了一个选项。

无论如何，使用动态编程，我需要为这个问题建立一个递归方程。

我想出了：

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 个数组。

现在，我不认为我的递归方程是好的。即使是这样，我也不知道如何将条件（两个标记不能水平或垂直相邻）添加到递归方程中。

任何人都可以尝试帮助吗？

4

2 回答 2

2

是的，您有 8 种可能的方式将标记放在列中：

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

现在，您只能将特定列放在其他列之后。例如：

  1. A可以是任何列的邻居，
  2. 只能A做自己的邻居，
  3. B可以是 and 的邻居C，G但不能是另一个Bor ForH的邻居
  4. H只能是A、C或D等的邻居。

需要注意的一件事是，如果给定的列是和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 回答
0

这个答案实际上与 unkulunkulu 的相同，尽管是独立派生的。我在这里包含它是因为它在处理数组时可能在符号上更好或更简单。

接下来，让p或q在 {0..7} 中为八种配置之一的索引，并让k为列索引。设为columnV(k,p)中配置的值。设以column中的配置结尾的列的最佳配置的值。如果允许配置相邻，则为 1，否则为 0。（相当于unkulunkulu的图关联矩阵。）符号 ∞ 表示大于矩阵的正单元格值之和的数字。pkW(k,p)0..kpkφ(p,q)p,qφ

那么 W(k+1,p) = V(k+1,p) + max q∈{0..7} (W(k,q)·φ(p,q) + ∞·(φ(p, q)-1))
当 k≥0 且 W(0,p)=V(0,p) 时。

于 2013-05-11T15:25:13.217 回答