algorithm - A* 何时终止

Question

在具有 1 个源节点（树的根）和更多目标节点的树上运行 A* 搜索时，算法何时终止？

它是在找到第一个目标后终止还是继续直到树被完全访问

标签： algorithmsearchtreepath-findinga-star

Answer 1

这些终止条件都不是完全正确的。

当您实际找到的目标的最佳路径的成本小于或等于任何其他路径的最佳可能成本时，A* 终止。

由于可接受的启发式函数永远不会高估成本，因此只需在找到目标顶点时将其放入优先级队列中即可完成，其估计成本等于其实际成本。

然后，当目标顶点作为具有最小成本的目标顶点从队列中弹出时，该算法将终止。