如何使用A星算法来查找前100条最短路径？

Question

如何使用A星算法来查找前100条最短路径？

Answer 1

这不是一个NP难算法，下面的链接是在多项式时间内计算图中K-最短路径的Yen算法。日元算法链接

Answer 2

除了这个问题是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时，您将通过A选择路径，但您将无法通过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时，你甚至不能通过B和C来节省绕道，因为你不知道。您必须为每个未访问的邻居添加类似“通过C的潜在路径”的内容。

第三，你必须合并环路和死胡同，因为是的，一条有环路的路径很可能是你100条最短路径中的一条。当然，你可能会想限制这一点，但这是一种普遍的可能性。例如，考虑以下图形：

S-A--D--E
  |  |
  B--C

很明显，你可以很容易地在这里开始循环，除非你不允许“返回”（例如禁止）-

现在我甚至可能忘记了一些问题。

请注意，大多数情况下，开发通用算法也非常困难，当然是最后一部分，因为使用循环很难限制可能路径的数量（“无限循环”）。

Answer 3

寻找第k条最短路径的问题是NP困难的，因此对A-Star的任何修改都将按输入的大小成指数。

证明：
（注意：我会在简单路径上显示）
假设你有一个多项式算法，它以多项式时间运行并返回k的长度，最短路径让算法是A（G， k）

最大路径数为n ，并在范围[1，n！]上应用二进制搜索要找到长度为n的最短路径，您需要O（log（n！）=O（nlogn）调用A<如果你发现有一条长度为n的路径，那就是哈密顿路径<通过对图中的每个源和目标重复该过程（O（n^2）），您可以多项式求解哈密顿路径问题，假设存在这样的哈密顿路径问题<量化宽松

由此我们可以得出结论，除非P=NP（根据大多数CS研究人员，这是非常不可能的），否则问题无法多项式求解。

另一种方法是使用统一成本搜索的变体，而不维护已访问的集。你也可以通过禁用闭合节点来修改A*，并在遇到解决方案时产生/生成解决方案，而不是返回并完成，但目前我想不出一种方法来证明它。