0

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

4

1 回答 1

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 顺序读取，因为您没有超出矩阵的边界。但是，正如您所说，这两个维度都非常大，我猜这没什么帮助。

于 2012-05-14T11:20:39.220 回答