如何使用 A 星算法找到前 100 条最短路径？
问问题
2936 次
4 回答
8
找到第 k 条最短路径的问题是NP-Hard，因此任何对 A-Star 的修改都会按照您的要求进行 - 输入的大小将成指数增长。
证明：（
注意：我将在简单路径上展示）
假设您有一个多项式算法，它在多项式时间内运行并返回k最短路径的长度让算法为A(G,k)
路径的最大数量是n!，并且通过在范围上应用二进制搜索[1,n!]来找到长度最短的路径n，您需要O(log(n!)) = O(nlogn)调用A.
如果你发现有一条长度的路径n——它是一条汉密尔顿路径。
通过对图中（其中的）每个源和目标重复该过程O(n^2)，您可以多项式地解决哈密顿路径问题A，假设存在这样的问题。
量子点
由此我们可以得出结论，除非P=NP（根据大多数 CS 研究人员的说法，这不太可能），否则问题无法通过多项式解决。
另一种方法是使用统一成本搜索的变体，无需维护visited/closed设置。您也可以通过禁用关闭的节点来修改 A* ，并在遇到时产生/生成解决方案，而不是返回它们并完成，但我目前想不出一种方法来证明 A* 。
于 2012-12-30T07:11:07.397 回答
0
除了这个问题是-hard 之外，无论有没有重大修改NP，都不可能做到这一点。以下是一些主要原因：A*dijkstra
首先，该算法在每一步都只保留迄今为止的最佳路径。考虑下图：
A
/ \
S C-E
\ /
B
假设距离d(S,A)=1, d(S,B)=2, d(A,C)=d(B,C)=d(C,E)=10。
访问 C 时，您将选择路径 via A，但您将无处存储路径 via B。所以你必须保留这些信息。
但是，其次，您甚至没有考虑所有可能的路径，假设如下图：
S------A--E
\ /
B--C
假设距离d(S,A)=1, d(S,B)=2, d(B,C)=1, d(A,E)=3。您的访问顺序将是{S,A,B,C,E}。因此，当您访问时，您甚至无法通过并且因为您不知道而A绕道而行。您必须为每个未访问的邻居添加诸如“通过 C 的潜在路径”之类的内容。BC
第三，您必须合并循环和死胡同，因为是的，其中包含循环的路径很可能最终成为您的 100 条最短路径之一。您当然可能希望限制这一点，但这是一种普遍的可能性。例如，考虑这样的图表：
S-A--D--E
| |
B--C
很明显，您可以轻松地在此处开始循环，除非您不允许“返回”（例如D->A，如果A->D已经在路径中，则禁止）。A-B-A-B-A-...实际上，这甚至是一个没有明显图形循环的问题，因为在一般情况下，您总是可以在两个邻居（路径）之间进行乒乓球。
现在我什至可能忘记了一些问题。
请注意，这些事情中的大多数也使得开发通用算法变得非常困难，当然是最后一部分，因为使用循环很难限制可能路径的数量（“无限循环”）。
于 2013-01-02T10:56:58.830 回答
0
这不是 NP 硬算法，下面的链接是 Yen 算法，用于在多项式时间内计算图中的 K 最短路径。 日元的算法链接
于 2017-02-20T04:05:32.333 回答
-1
当目的地是第 k 次推入队列时，使用 a* 搜索。这将是第 k 条最短路径。
于 2012-12-30T06:57:42.943 回答