algorithm - 如何有效修改 A* 算法以提供第 n 条最短路径？

Question

如何有效地修改 A* 算法以提供例如第二或第八最短路径，不是第一？

Answer 1

如果可能的话，我建议您尝试让您的程序看起来像 Dijkstra 适用的最短路径问题，然后使用您已经指出的答案之一来找到这种情况下的第 k 条最短路径，例如 Eppstein's algorithm and Yen's algorithm for k shortest paths .

但还有另一种方法。有一种通用技术可以通过添加允许您拆分解决方案树的额外约束来找到组合问题的第 K 个最佳答案。它被称为 Lawler-Murty，例如在 http://www.vldb.org/pvldb/vol4/p1028-golenberg.pdf 的第 2 节中进行了描述。