最佳优先搜索疑问：为何重复探索路径成本更高的节点？

你的观点完全正确——标准的A*实现确实会在从优先队列（frontier）弹出节点时，先检查该节点对应状态的已知最低PATH-COST：只有当当前节点的g值（即PATH-COST）低于该状态所有已记录的路径成本时，才会处理（扩展）这个节点；否则直接跳过，避免冗余计算。

示例中出现“不必要路径”的原因 #

你提到的示例属于未做重复节点优化的基础最佳优先搜索，而非严格意义上的A*。严格的A*会维护一个存储每个状态最低g值的结构（比如哈希表或已访问集合），处理逻辑如下：

• 当节点['S', 'B']被弹出时，此时状态B的最低g值已经是通过S->A->B得到的更低值，因此这条路径会被直接跳过，不会被扩展
• 同理，当['S', 'A', 'B', 'C']被弹出时，状态C的最低g值已经由S->D->C确定，这条路径也会被直接忽略

关键原理 #

A*的最优性和效率依赖两个核心条件：

• 启发函数h(n)是可采纳的（即h(n)不超过从节点n到目标节点的实际最小路径成本）
• 对重复节点的过滤：确保每个状态仅以最低的PATH-COST被扩展，避免无效的重复探索

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