A *何时终止

问题描述 投票:0回答:1

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

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

algorithm search tree path-finding a-star
1个回答
0
投票

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

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

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

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

© www.soinside.com 2019 - 2024. All rights reserved.