algorithm - A*什么时候终止

Question

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

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

Answer 1

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

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

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

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