A*算法节点扩展顺序疑问：为何是ACBDG而非ACG？

核心公式回顾 #

A*算法的核心是每个节点的代价评估函数：
f(n) = g(n) + h(n)
其中：

• g(n)：从起始节点A到节点n的实际路径代价
• h(n)：从节点n到目标节点G的启发式估计代价（需满足可采纳性，即h(n)≤实际代价）
  扩展节点时，始终从open列表（待扩展节点集合）中选择f值最小的节点，和当前正在扩展的节点的f/g值无关。

问题1：为什么扩展顺序是ACBDG而非ACG？ #

当扩展完A、C后，C的邻居（比如B、G）会被加入open列表。此时需要比较B和G的f值：

• 如果f(B) = g(B) + h(B) 小于 f(G) = g(G) + h(G)（注意h(G)=0，因为G是目标节点），那么下一个扩展的节点就是B，而非G。
  举个具体数值例子：
  假设A到C的实际代价g(C)=2，C到G的实际代价是10（所以g(G)=2+10=12），h(G)=0 → f(G)=12；
  C到B的实际代价是1（g(B)=2+1=3），h(B)=5 → f(B)=3+5=8。
  此时f(B)=8 < f(G)=12，所以优先扩展B，而非G。

问题2：扩展节点时的判断逻辑 #

扩展节点的唯一依据是待选节点自身的f值，不需要结合当前节点的f值或g值。open列表本质是一个按f值升序排列的优先队列，每次取出队列头部（f值最小）的节点进行扩展，同时将该节点的未访问邻居计算f值后加入队列。

问题3：扩展完A、C、B后，为何选D而非G？ #

你提到H(G) < H(D)，但A*算法看的是f值而非单独的h值。即使h(G)更小（甚至为0），如果G的f值（g(G)+h(G)）大于D的f值（g(D)+h(D)），依然会优先扩展D。
比如：
假设B到D的实际代价是1，g(D)=g(B)+1=3+1=4，h(D)=5 → f(D)=4+5=9；
而此时G的f值还是12（如之前的例子），那么f(D)=9 < f(G)=12，所以会先扩展D。只有当G的f值成为open列表中最小的那个时，才会被优先扩展。

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