A*算法实现疑问：路径回溯失败的两种情况为何不会发生？如何预防？

1. 子节点存在多个父节点的情况 #

这种情况是A*运行过程中正常会出现的现象，但不会导致回溯路径失败。

A*的核心是维护每个节点的g(n)值（从起点到节点n的实际路径代价），当同一个子节点从不同父节点被访问时，会计算两种路径的g值：

• 如果新路径的g值比当前记录的更小，说明这条路径更优，此时会更新该子节点的父指针为新的父节点，并更新g值；
• 如果新路径的g值更大或相等，就直接忽略这条路径，保留原来的父指针。

最终回溯路径时，每个节点只会保留最优路径对应的父节点，不会出现多个父节点导致的回溯混乱。

2. 路径中出现循环结构的情况 #

在标准A算法的最终路径中，绝对不会出现循环，原因如下：
A适用的场景中，每一步移动的代价都是正数（比如网格移动每步代价至少为1）。假设存在循环：起点→...→P→...→Q→P，那么从起点到P的新路径代价g'(P) = g(Q) + cost(Q→P)，而g(Q) = g(P) + cost(P→...→Q)，代入后可得g'(P) = g(P) + cost(P→...→Q) + cost(Q→P)。由于每步代价都是正数，所以g'(P) > g(P)，也就是这条带循环的路径代价比原来直接到P的路径更高。

当A*处理到这个循环中的P时：

• 如果P已经在**关闭列表（closed set）**中，说明P的最优路径已经确定，新的更高代价路径会直接被跳过；
• 如果P还在开放列表（open set）中，新的g'(P)比已记录的g(P)大，不会更新父节点，因此循环不会被保留到最终路径里。

预防与处理总结 #

标准A*的逻辑已经天然避免了这两个问题对最终路径的影响：

• 针对多父节点：始终只保留g值最小的路径对应的父节点，无需额外处理；
• 针对循环：确保移动代价为正，严格遵守关闭列表规则——已加入关闭列表的节点不再重新处理，即可杜绝循环出现在最终路径中。

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