A*搜索算法输出非最优路径问题咨询，算法与启发函数正确性排查

A*只要满足启发函数可采纳、启发函数满足一致性（针对带closed集的实现）两个条件，就一定能输出最优解，你遇到的问题属于实现逻辑错误，和算法本身无关。

常见排查方向如下：

• 终止条件错误：A的最优解判定时机是终点节点被从优先队列（开放集）中弹出时*，而非终点被首次加入开放集时。如果在后者阶段直接终止，大概率会得到非最优路径。
• 开放集节点更新逻辑错误：同一个节点如果后续被探索到更小的g(n)值（路径成本），需要同步更新该节点的f(n)值并调整其在优先队列中的排序，或是直接将新的低f值节点加入开放集，不能因为节点曾进入过开放集就忽略更优的路径分支。
• 启发函数计算错误：曼哈顿距离的计算公式是|x1 - x2| + |y1 - y2|，请检查是否存在坐标写反、终点/起点参数传反的低级错误，导致h(n)被高估，违反可采纳性。
• 路径成本计算错误：确认每移动一步的成本累加是否正确，是否存在多算/漏算步长导致g(n)异常的情况。

你提到当前探索路径的f(n)始终低于最优路径首节点的f(1)，这本身就违背曼哈顿距离的可采纳性属性，建议优先核对你手动计算和代码计算的f(n)数值是否一致，大概率是数值计算环节出错。

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