我如何使用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级明星，会做什么后，你是 - 将指数在输入的尺寸

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（日志（N！））= O（nlogn） A的invokations 。
如果您发现有长度的路径 N - 这是一个的哈密尔顿路径的。
通过重复该过程为每个源和目标图中的（为O（n ^ 2）的那些），就可以解决的Hamiltonian路径问题的多项式，假设这样的 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.

这是另一种方法是使用统一成本搜索的变化没有保持走访 / 关闭设置。你也许可以修改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屋！