基本上，我有一个n乘m的浮点值数组，我试图找到第一行值和第二行值之间的最短路径图中的node(i, j)对于不在边上且不在底行的任何节点都有子节点。我在找一个算法来及时解决这个具体问题我现在的想法是围绕着A*搜索，但让我知道你的想法。
最佳答案
列表项
动力学解为o（nm）或o（m^2）。但这是不可能的-这里有一个更好的解决方案的反例。假设您想在第一行最左边的元素和最后一行最左边的元素之间找到一条路径。让我们来看看这个形式的矩阵：
10000000000000
11000000000000
11100000000000
11110000000000
11111000000000
11111100000000
11111110000000
11111111000000
11111110000000
11111100000000
11111000000000
11110000000000
11100000000000
11000000000000
10000000000000
“1”是可能在从源元素到目标元素的路径上经过的元素。“0”是不能通过的元素。
“1s”的数目为NM/4阶，所以O（NM）（实际上，Min（NM，M^2），见下文）因此，在该矩阵中读取每个1s的算法将是>＝O（NM）复杂度。
另一方面，不读取所有“1”的算法将是不正确的。
证明：让矩阵中的数字成为权重。选择一个“1”算法没有读取。把1改成0.5。对于这个输入，算法失败了，因为最优路径现在经过一个它从未读取过的元素（因为它第一次读取的元素都没有改变，所以这次也会读取相同的元素，除非它是不确定的，在这种情况下，它是否工作是随机的，这也使得它不正确）。
然而，好的o（nm）溶液对于1000x1000个矩阵（不到一秒钟）应该可以很好地工作。如果只命中必须命中的元素（例如，在我的示例矩阵中，如果宽度增加到10000000，则不必读取添加的元素），则可以将其优化为m in（m^2，mn）。类似地，如果高度增加到10000000，则没有m^2顺序读取，因为没有超出矩阵的边界。然而，正如你所说的，这两个维度都非常大，我想这对我没什么帮助。
关于algorithm - 有向无环图的最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/10573710/