java - A* (A Star) 算法输出所有可能的解

Question

已知 A 星算法是完整的。但是，我在网上找到的所有实现似乎只返回第一个（最佳）解决方案。

例如，这个实现： 星型算法实现

由于该算法总是扩展具有最小 f 值的节点，并且当第一个节点是一个解决方案时，实现似乎停止了，如何调整上述代码以输出所有（或前n 个）导致目标，而不考虑重复的动作（即一遍又一遍地包含相同动作的路径）？

Answer 1

它是完整的，这意味着如果存在解决方案，它将找到解决方案，但该算法专门只返回一个路径。广度优先搜索将找到两个节点之间的所有非循环路径，但是：http ://en.wikipedia.org/wiki/Breadth-first_search

更新- 这是 k 最短路径算法，它将按从最短到最长的顺序返回 n（或在本例中为 k）最短路径的列表。http://code.google.com/p/k-shortest-paths/

Answer 2

对于所有路径，使用呼吸优先搜索可能更有意义。或者，如果您想找到前 n 条最短路径，可以尝试Dijkstra 算法。