1

给定一个所有整数的矩阵positive，从最左边的列开始0th，找到到最右边的列的最小路径(n - 1)th。例如：
在此处输入图像描述

最小路径是包含 1 的路径。

在任何给定的方格m[i, j]上，我们可以移动到 4 个方向 ( left, right, up, down)；当然，除了最左边，最右边的行/列的所有角落案例。例如，在 处[0, 0]，我们只能移动right或down。
我的解决方案是构建一个m x n顶点图，然后运行​​Floyd-Warshall计算任意两个顶点的所有对最短路径(u, v)。然后运行另一个嵌套for循环以检查0th列的所有顶点与列的所有顶点(n - 1)th以找到最小路径。
但是，我的教授通过使用以下递归提出了另一种算法：

S[i, j, L] = 
    min(
        S[i - 1, j, L - 1] + cost[i - 1, j],
        S[i + 1, j, L - 1] + cost[i + 1, j],
        S[i, j - 1, L - 1] + cost[i, j - 1],
        S[i, j + 1, L - 1] + cost[i, j + 1]);

我不知道它是如何工作的！因为在任何给定的方格[i, j]上，我们都可以在 4 个方向上移动，这使得不可能根据之前的预先计算的值来构建表格。
我在这里错过了什么吗？我看不出这种重复是如何进行的。任何想法？

4

1 回答 1

4

如果你有 S[i,j,0] = infinity，除了 S[0,j,L] = 0，那么它应该可以工作。最终所有 S[i,j,L]==S[i,j,L+1] 并且您可以停止迭代。S[i,j,L] 然后具有从第一列到该单元格的最短路径的成本。

这就是这个递归在左上角的样子，以增加 L 的值。

0   inf inf inf inf
0   inf inf inf inf
0   inf inf inf inf

0   1   inf inf inf inf
0   20  inf inf inf inf
0   21  inf inf inf inf

0   1   2   inf inf inf
0   2   30  inf inf inf
0   21  22  inf inf inf

0   1   2   3   inf inf
0   2   3   39  inf inf
0   12  22  23  inf inf

0   1   2   3   4   inf
0   2   3   4   47  inf
0   12  12  23  24  inf

0   1   2   3   4   5  
0   2   3   4   5   48  
0   12  12  12  24  25 

0   1   2   3   4   5  
0   2   3   4   5   6   
0   12  12  12  6   25 

0   1   2   3   4   5
0   2   3   4   5   6
0   12  12  7   6   7

0   1   2   3   4   5
0   2   3   4   5   6
0   12  8   7   6   7

0   1   2   3   4   5
0   2   3   4   5   6
0   9   8   7   6   7

左上角不会发生进一步的变化。您可以看到它正在慢慢发现到达每个单元格的最低成本。

于 2013-03-24T07:13:42.237 回答