A*算法终止时机及单源多目标树搜索终止规则问询

让我来拆解你的两个问题，都是A*算法实践中常遇到的关键点：

A*的终止逻辑主要分两种情况：

• 核心终止场景：当从优先队列（也就是大家常说的open list）中取出的节点恰好是目标节点时，算法可以直接终止。这里要强调，如果你的启发式函数是可采纳的（简单说就是永远不会高估从当前节点到目标的代价），那第一次取出目标节点时，你就已经找到了起点到目标的最短路径，继续运行完全没必要。
• 不可达场景：如果优先队列已经被清空，但始终没取出目标节点，那就说明目标节点从起点根本走不到，算法也会终止。

这个得看你的具体需求，不能一概而论：

• 如果你的目标只是找到任意一个目标节点的最短路径，那当A*第一次从open list里取出某个目标节点时就可以停了。还是靠可采纳启发式的保证，这时候拿到的路径就是到这个目标的最优解，不用再遍历整棵树。
• 但如果你的需求是找到所有目标节点的路径，或者要找离起点最近的那个目标节点，那中途终止就不行了。你得继续运行算法，直到open list为空，同时记录下所有找到的目标节点的路径和代价，最后再对比选出最优的。
• 额外提个优化点：如果启发式是可采纳的，其实不用完全遍历到open list为空。当你已经记录了当前找到的最小目标代价，而open list里剩下的所有节点的f值（g+h，g是起点到当前节点的实际代价，h是启发式预估代价）都大于等于这个最小代价时，就可以提前终止了——因为剩下的节点不可能找到更优的目标路径了。

内容的提问来源于stack exchange，提问作者smith