2

我们给定一个加权 N*N 网格 W。两个机器人 r1,r2 分别从左上角和右上角开始。R1 必须到达右下角，R2 必须到达左下角。这是有效的动作。

  • R1 向下移动一格，R2 向左移动一格。
  • R1 向右移动一格，R2 向下移动一格。

他们必须以这样一种方式移动，即他们所访问的方格（包括起始方格和结束方格）的权重之和最大化。

例如，如果网格是：

6   0   3   1
7   4   2   4
3   3   2   8
13  10  1   4

在这个例子中，如果 R1 遵循 * 标记的路径，R2 遵循 ^ 标记的路径，如下所示，它们的组合得分为 56。

 6*   0     3^   -1^
 7*   4*^   2^    4
-3    3*^  -2*    8*
 13^  10^  -1    -4*

可以验证这是该网格可以达到的最佳组合分数。

我们不能通过递归来解决这个问题，因为 N <= 2500 并且时间限制是 2 秒。
如果问题只有一个机器人，我们可以使用动态规划来解决这个问题。

我尝试对这个问题使用类似的方法；

我们有两个额外的 N*N 网格 G1,G2,

for i from 1 to N:
   for j from 1 to N and K from N down to 1:  
     if (G1[i-1][j] + G2[i][k+1]) > (G1[i][j-1] + G2[i-1][k]):
        G1[i][j] = G1[i-1][j] + W[i][j]
        G2[i][k] = G2[i][k+1] + W[i][k]
     else:
        G1[i][j] = G1[i][j-1] + W[i][j]
        G2[i][k] = G2[i-1][k] + W[i][k]

return G1[N][N] + G2[N][1]

但这给出了错误的答案。我无法理解我的算法有什么问题，因为对于每个正方形，它都在计算到达那里的最大加权路径。

谁能告诉我我的方法有什么问题，我该如何纠正它以获得正确的答案？

4

2 回答 2

1

我可以在第二个有效场景中看到一个错字

有效的第二种情况应该是

R1向右移动一格，R2 向下移动一格

但被认为是

R2向右移动一格，R2 向下移动一格

于 2012-12-28T07:20:01.170 回答
1

这是一个图问题，图在G=(V,E)哪里：

  • V = Squares x Squares（所有正方形的笛卡尔积）
    （您可能想要排除 (x1,y1)=(x2,y2) 的点，这很容易做到）。
  • E = { 所有可能的转弯移动方式} = (或正式) =
    { (((x1,y1),(x2,y2)),((x1-1,y1),(x1,y1-1) )), (((x1,y1),(x2,y2)),((x1,y1-1),(x1-1,y1))) | 每 x1,y1,x2,y2 }

现在，一旦我们有了图 - 我们可以看到它实际上是一个DAG - 这是一件好事，因为对于一般情况图 -最长路径问题是NP-Hard，但不是 DAG。

现在，给定一个 DAG G，我们想找到从((0,0),(n,n))到的最长路径((n,n),(0,0))，可以通过以下方法完成：

为简单起见，定义weight((x1,y1),(x2,y2)) = weight(x1,y1) + weight(x2,y2)：

算法：

  1. 在图上使用拓扑排序
  2. Init D((n,n),(0,0)) = weight((n,n),(0,0)) （目标节点）
  3. 根据降序迭代图并对每个顶点执行v：
    D(v) = max { D(u) | 如上所述，对于 E 中的每个 (v,u) } + weight(v)

完成后 D((0,0),(n,n)) 将获得最佳结果。

于 2012-12-28T07:26:00.690 回答