为什么我实现的A*搜索算法性能看起来远低于贪心搜索？

问题原因及解答 #

1. 代码存在可导致性能下降的bug

• 子节点路径代价赋值逻辑错误：处理扩展子节点时，仅当节点未被访问过（不在reached表）时才会更新s.pCost，当找到一条到已访问节点的更短路径时，没有更新该节点的pCost，导致后续计算f(x) = g(x) + h(x)时使用的是旧的、更大的g(x)值，优先队列排序错误，大量无效节点被扩展，拉低了A*的执行效率。
• 状态更新逻辑不完整：A*允许节点多次进入优先队列，只要新路径的f值更小，但代码中没有同步更新节点存储的路径代价，就算把节点加入队列，计算出的f值也存在误差，进一步降低执行效率。

2. 无bug前提下A*比贪心慢属于正常表现

• 贪心搜索的逻辑是永远优先扩展离目标最近的节点，不需要考虑已经走过的路径长度，在没有复杂障碍物的场景下，几乎可以直线到达终点，扩展的节点数量极少，速度自然更快。但贪心搜索无法保证找到最短路径，遇到需要绕路的障碍物时很容易陷入局部最优，出现走冤枉路甚至卡死的情况。
• A*的核心价值是在启发函数满足可采纳性（永远不会高估到目标的距离，本次使用的欧氏距离符合要求）的前提下，一定能找到全局最短路径。为了这个最优性保证，它需要兼顾已走路径代价和到目标的预估代价，必然会扩展比贪心更多的节点，在无障碍物、少障碍物的简单场景下速度慢于贪心属于正常情况。

3. 降低pCost权重后性能提升的原因

降低g(x)权重时，算法的决策逻辑会更偏向贪心“朝目标前进”的策略，自然会减少扩展的节点数量，速度变快。但这个操作本质上破坏了启发函数的可采纳性，A*的最优性保证会消失，最终得到的路径大概率不是最短路径，属于牺牲正确性换取速度的操作。

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