c - 我们如何在网格中找到两条权重最大的路线？

Question

We a given a weighted N*N grid W. Two robots r1,r2 start from top left and top right corners respectively. R1 has to reach to the bottom right and R2 the bottom left corners. Here are the valid moves.

• R1 moves one square down, R2 moves one square left.
• R1 moves one square right, R2 moves one square down.

They must move in such a way that the sum of the weights of the squares they visit (including the starting and ending square) is maximized.

For Examples, if the grid is:

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

In this example, if R1 follows the path marked by * and R2 follows the path marked by ^, as shown below, their combined score is 56.

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

It can be verifyed that this is the best combined score that can be achieved for this grid.

我们不能通过递归来解决这个问题，因为 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]

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

谁能告诉我我的方法有什么问题，我该如何更正才能得到正确的答案？

Answer 1

这是一个图问题，图是G=(V,E) 其中:

• V = 正方形 x 正方形(所有正方形的 Cartesian product)
  (您可能希望排除 (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 - 这是一件好事，因为对于一般情况图 - longest path problem是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. 使用topological sort在图表上
2. 初始化D((n,n),(0,0)) = weight((n,n),(0,0))(目标节点)
3. 根据降序对图进行迭代，并对每个顶点 v 执行以下操作:
   D(v) = 最大值 { D(u) |如上所述，对于 E 中的每个 (v,u) } + weight(v)

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