algorithm - 有向无环图的最短路径

Question

所以基本上，我有一个 n x m 的浮点值数组，我试图找到第一行值中的任何一个值和第 m 行值中的任何一个之间的最短路径。节点 (i, j)图中有 child {(i, j+1), (i-1, j+1), i+1, j+1)}对于不在边缘的任何节点 (0 < i < n-1)并且不在底行 (j < m-1) .我正在寻找一种算法来及时解决这个特定问题。我目前的思路围绕着 A* 搜索，但请告诉我您的想法。

Answer 1

• 列表项

动态解是 O(NM) 或 O(M^2)。而且它不能低于这个 - 这是任何更好解决方案的反例。假设您想在第一行最左边的元素和最后一行最左边的元素之间找到一条路径。让我们看一下这种形式的矩阵:

10000000000000
11000000000000
11100000000000
11110000000000
11111000000000
11111100000000
11111110000000
11111111000000
11111110000000
11111100000000
11111000000000
11110000000000
11100000000000
11000000000000
10000000000000

“1s”是您可能在从源元素到目标元素的路径上经过的元素。 “0s”是你不能通过的元素。

“1”的数量是 NM/4 阶，所以 O(NM)(实际上是 Min(NM, M^2)，见下文)。因此，读取该矩阵中每个 1 的算法的复杂度 >=O(NM)。

另一方面，不读取所有“1”的算法是不正确的。

证明:令矩阵中的数字为权重。选择算法不读取的“1”。将 1 更改为 0.5。该算法对该输入失败，因为最佳路径现在经过一个它从未读取过的元素(因为它第一次读取的元素都没有改变，所以这次它也会读取相同的元素，除非它是不确定的，在这种情况下它是它是否会起作用是随机的，这也使得它不正确)。

但是，好的 O(NM) 解决方案应该适用于 1000x1000 矩阵(不到一秒)。如果您只命中必须命中的元素，则可以将其优化为 Min(M^2, MN) (例如，在我的示例矩阵中，如果宽度增加到 10000000，则不必读取添加的元素).同样，如果高度增加到 10000000，则没有 M^2 顺序读取，因为您没有超出矩阵的边界。但是，正如您所说的两个维度都非常大，我想这没什么帮助。