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

Question

已知 A 星算法是完备的。但是，我在网上搜索发现的所有实现似乎只返回第一个(最佳)解决方案。

例如，这个实现: A star algoritthm implementation

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

Answer 1

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