启发式仅可采纳非一致时的A*重开：目标状态提前返回合理性问询

这个问题问得太到位了——这刚好戳中了一致启发式和仅可采纳但不一致启发式下A*行为的核心区别，尤其是当你启用了节点重开机制的时候。

先给你理清楚两种场景的本质差异：

• 要是用的是一致（单调）启发式，咱们都知道A*第一次从OPEN队列里弹出目标节点时，直接返回这条路径就完事了。因为一致启发式有个关键特性：任何后续能到达目标的路径，代价都不可能比当前找到的更小，所以没必要再折腾其他节点。
• 但如果你的启发式只是可采纳，但不一致，还开了节点重开机制（就是允许把已经进了CLOSED列表的节点重新放回OPEN，当发现更优路径的时候），那情况就完全不一样了：

为啥不能在目标进CLOSED时直接返回？ #

道理很直白：哪怕目标已经被标成CLOSED了，后面说不定会冒出某个OPEN里的节点n，它的f(n)=g(n)+h(n)比当前目标的g(goal)（也就是当前找到的目标路径代价）还小。因为启发式是可采纳的，h(n)肯定不超过n到目标的真实最短路径代价h*(n)，所以g(n)+h*(n)（也就是从起点经n到目标的真实最短路径总代价）肯定≤g(n)+h(n)。如果g(n)+h(n)都比g(goal)小，那说明大概率存在一条比当前找到的更优的路径到目标，这时候必须把目标节点重新拉出来处理，更新它的g值，直到没有任何可能的路径能带来更小的代价为止。

那正确的返回时机该怎么判断？ #

在这种带重开机制的A*实现里，你得等到OPEN队列为空，或者OPEN队列里所有节点的f值都大于等于当前已知的目标节点的g值时，才能返回目标的最优路径。只有这时候，才能确保不会再有任何路径能比当前的g(goal)更优。

举个接地气的例子：假设起点是S，目标是G，中间有个节点A。边的代价是S→A=1，A→G=1，S→G=3。启发式函数设成：h(S)=2（可采纳，因为S到G的真实最短代价是2，h(S)≤这个值），h(A)=0，h(G)=0。这时候h是可采纳但不一致的——因为h(S)=2 > c(S,A)+h(A)=1+0=1，违反了一致性条件。

A*运行时可能先直接走S→G，把G放进CLOSED，此时g(G)=3。接着处理S→A，算出g(A)=1，f(A)=1+0=1，比当前的g(G)=3小。这时候发现从A到G的路径总代价是1+1=2，比3小，所以得把G从CLOSED放回OPEN，更新g(G)=2。直到OPEN队列里没有节点的f值小于2时，这时候返回的g(G)=2才是真正的最优路径。

所以一句话总结：

• 一致启发式：第一次弹出目标就可以直接返回。
• 仅可采纳但不一致+重开机制：必须等OPEN里没有能带来更优路径的节点（要么OPEN空了，要么所有节点的f值都≥当前目标的g值），才能返回，不然拿到的可能不是最优解。

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