如何使用 A 星算法找到前 100 条最短路径? [英] How can I use the A star algorithm to find the first 100 shortest paths?

问题描述

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

How can I use the A star algorithm to find the first 100 shortest paths?

推荐答案

求第k条最短路径的问题是NP-Hard，因此对 A-Star 所做的任何修改都可以满足您的要求 - 输入的大小将呈指数级增长.

The problem of finding k'th shortest path is NP-Hard, so any modification to A-Star that will do what you are after - will be exponential in the size of the input.

证明:
(注意:我会在简单路径上显示)
假设你有一个多项式算法，它在多项式时间内运行并返回k的长度，最短路径让算法为A(G,k)

Proof:
(Note: I will show on simple paths)
Assume you had a polynomial algorithm that runs in polynomial time and returns the length of kthe shortest path let the algorithm be A(G,k)

最大路径数为n!，通过对[1,n!]范围进行二分查找，找到长度为的最短路径n，您需要O(log(n!)) = O(nlogn) 次A 调用.
如果您发现有一个长度为 n 的路径 - 它是一个 汉密尔顿路径.
通过对图中的每个源和目标(O(n^2))重复该过程，您可以解决Hamiltonian Path Problem 多项式，假设这样的 A 存在.
QED

The maximal number of paths is n!, and by applying binary search on the range [1,n!] to find a shortest path of length n, you need O(log(n!)) = O(nlogn) invokations of A.
If you have found there is a path of length n - it is a hamiltonian path.
By repeating the process for each source and target in the graph (O(n^2) of those), you can solve the Hamiltonian Path Problem polynomially, assuming such A exists.
QED

由此我们可以得出结论，除非 P=NP(根据对于大多数 CS 研究人员而言)，该问题无法通过多项式解决.

From this we can conclude, that unless P=NP (and it is very unlikely according to most CS researchers), the problem cannot be solved polynomially.

另一种方法是使用 Uniform Cost Search 的变体，而无需维护 visited代码>/<代码>关闭设置.您也可以修改 A*，通过禁用封闭节点，并在遇到时产生/生成解决方案而不是返回它们并完成，但我想不出一种方法来证明 A* 目前.

An alternative is using a variation of Uniform Cost Search without maintaining visited/closed set. You might be able to modify A* as well, by disabling the closed nodes, and yielding/generating solutions once encountered instead of returning them and finishing, but I cannot think of a way to prove it for A* at the moment.

这篇关于如何使用 A 星算法找到前 100 条最短路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！