如何使用A*算法找到前100条最短路径？

Question

如何使用A*算法找到前100条最短路径？

algorithmgraph-algorithmshortest-patha-star

3

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

- user1815763

你希望用这些路径做什么？第n短路径通常是在某个点上绕路的最短路径，对于任何实际目的都没有用处。可能会有一些合理的替代路径，但难题在于如何判断路径是否“合理”符合人类的思维方式。 - Jan Hudec

@Jan Hudec：在我的程序中，我将实现航班搜索系统。边缘的成本是飞行时间。我将寻找价格合理的航班解决方案。但最快的路径可能不是最便宜的路径。因此，我将首先找到100个最快的航班，然后根据情况定价路径。 - user1815763

寻找100条最快的航班可能会给你大量垃圾信息，并且实际上并没有给你提供便宜的路径，因为没有办法知道哪条路径是最便宜的。相反，你要么找到所有基于偏序关系（通过组合各种标准创建）的最小路径，要么使用不同目标函数多次运行算法。或者对深度和距离应用启发式限制并进行详尽的搜索；我猜这对于航班来说是可行的，但对公交连接等其他情况来说就不一定了。 - Jan Hudec

无论如何，那是一个完全不同的问题，所以在你制定新问题之后会有更详细的讨论 - 要么是“如何使用多个标准（更便宜、更短、更快等）搜索时间表并找到所有最小路径”，要么是“如何在航班时间表中搜索当需要许多替代结果时”。如果你感兴趣，两者都可以。 - Jan Hudec

如果您正在为航班搜索系统实施此功能，您可能需要查看替代路线：http://algo2.iti.kit.edu/2073.php，http://algo2.iti.kit.edu/english/1805.php等。 - Karussell

4个回答

0

除了这个问题是NP难问题之外，使用A*或Dijkstra算法进行操作是不可能的，除非进行重大修改。以下是一些主要原因：

首先，该算法在每一步只保留到目前为止最佳的路径。考虑下面的图形：

  A
 / \
S   C-E
 \ /
  B

假设距离为。

当访问C时，您将选择通过A的路径，但您不会在任何地方存储通过B的路径。因此，您必须保留此信息。

但是，第二点，您甚至没有考虑到每条可能的路径，假设以下图形：

S------A--E
 \    /
  B--C

假设距离为。您的访问顺序将是{S,A,B,C,E}。因此，当访问A时，您甚至不能通过B和C节省迂回路线，因为您不知道它。您需要为每个未访问的邻居添加类似“通过C的潜在路径”的内容。

第三，您必须合并循环和 cul-de-sacs's，因为是的，具有循环的路径最终可能成为您的100条最短路径之一。当然，您可能希望将其限制在外，但这是一种通用可能性。例如，考虑以下图形：

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

很明显，在这里你可以轻松地开始循环，除非你禁止“回溯”（例如，如果路径中已经有 A->D ，则禁止 D->A）。事实上，即使没有明显的图形循环，这也是一个问题，因为在一般情况下，你总是可以在两个相邻节点之间来回移动（路径A-B-A-B-A-...）。

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

请注意，这些问题中大部分也使得开发通用算法变得非常困难，尤其是最后一部分，因为在存在循环的情况下，很难限制你的可能路径数量（“无限循环”）。

- KillianDS

0

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

- ghedas

Yen算法实际上运行在伪多项式时间，因为运行时间取决于k的数值。尽管对于任何固定的k - 在这里，k = 100 - 它确实会在多项式时间内运行。 - templatetypedef

-1

使用A*搜索算法，当目标点第k次被加入队列时，它将成为第k短的路径。

- LazyChild

2

我不认为这个说法是正确的。你能证明吗？ - amit

@Mehrdad 当目的地第一次被推入队列时，值应该是最短路径。这样对吗？ - LazyChild

@LazyChild：对于最短路径-确实如此。假设您的启发式函数为h(v) = 0（这始终是可接受的，并且基本上意味着您的问题是未知的）。您能证明算法适用于第k短路径吗？（我怀疑，因为我刚刚展示了一般情况下k的问题是NP-Hard的，必须进行其他修改，例如禁用“关闭”集） - amit

@ LazyChild，你能否解释一下如何使用A*算法找到前k短路径（不是第k短）？ - user1815763

例如，考虑一个具有节点 {S,A,B,C,E}、连接关系 S-A, S-B, A-E, B-C, C-A 以及所有距离均为 1 的图形。您永远不会考虑路径 S-B-C-A-E。为什么？您的访问顺序将类似于 S,A,B,C,E。由于距离相等，A 和 B 可能会交换位置，C 和 E 也可能会交换位置，但这并不重要。您可以看到，当访问 A 时，您甚至不知道通过 C 的绕路，因为 C 尚未被访问。 - KillianDS

显示剩余4条评论

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- amit · Accepted Answer

找到第k短路径的问题是NP-Hard，因此对A-Star进行任何修改以实现您想要的功能都将随着输入规模的增加呈指数级增长。 证明：
（注意：我将在简单路径上展示）
假设您有一个多项式算法，在多项式时间内运行并返回k短路径的长度，让该算法为A（G，k）。

最大路径数为n!，通过在范围[1,n!]上应用二分查找来找到长度为n的最短路径，您需要调用A O(log(n!)) = O(nlogn)次。
如果发现存在长度为n的路径，则它是哈密顿路径。
通过对图中每个源和目标重复该过程（O(n^2)个），假设存在这样的A，您可以在多项式时间内解决哈密顿路径问题。
证毕

由此我们可以得出结论，除非P=NP（根据大多数计算机科学研究人员的说法，这很不可能），否则该问题无法在多项式时间内解决。

一种替代方案是使用统一代价搜索的变体，而不维护 visited/closed 集合。你也可以修改 A*，通过禁用关闭节点，在遇到解决方案时生成/产生它们，而不是返回它们并结束，但目前我无法想到一种证明它对于 A* 有效的方法。