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

Question

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

Answer 1

找到第k个最短路径的问题是NP-Hard,因此对A-Star进行的任何修改都会使输入的大小成为指数.

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

最大路径数是n!,并且通过在范围上应用二进制搜索[1,n!]来找到最短的长度路径n,您需要O(log(n!)) = O(nlogn)调用A.
如果你发现有一条长长的路径n- 这是一条哈密​​尔顿路径.
通过对图中的每个源和目标重复该过程(O(n^2)那些),您可以多项式求解哈密​​顿路径问题,假设A存在这样.
QED

由此我们可以得出结论,除非P = NP(并且根据大多数CS研究人员的说法很不可能),否则问题不能通过多项式求解.

另一种方法是使用统一成本搜索的变体而不进行维护visited/ closed设置.您也可以通过禁用关闭的节点来修改A*,并且一旦遇到而产生/生成解决方案而不是返回它们并完成,但我想不出一种方法来证明A*目前.