我最近开始学习 A* 算法及其变体，并发现了这篇论文 [1]。它基本上具有算法的三种变体，每种变体的启发值都发生了变化。
对于 A*(1)，它具有 f(i) = g(i) + h(i)，其中 g(i) 表示路径 -从起始点到当前位置i的成本函数，启发函数h(i)是当前点到目标点的欧氏距离。
对于 A*(2)，它有 f(i) = g(i) + h(i) + h(j)，其中 j当前点的父节点，h(j)是当前点的父节点到目标点的欧氏距离。
结果表明，在随机生成的迷宫上进行尝试时，A*(2) 通常比 A*(1) 更快。我无法解释为什么会这样。我尝试比较这两种启发法，并得出相反的结论。
我的逻辑是，如果我们从距离目标较远的点移动到较近的点，f(i) 值将高于从距离目标较近的点移动时的值。目标为较远的一个，因为我们正在考虑父节点的欧几里得距离。基本上，要到达特定节点，远离目标的路径将具有较低的 f(i)。
由于 f(i) 值较低，因此它会进入优先级队列。这违背了我们的目标，因为远离目标的路径优先于越来越近的路径。
这个逻辑有什么问题？为什么它与论文中引用的结果不一致？
最佳答案
在论文中使用的完美迷宫中，A* 与深度优先搜索、广度优先搜索和 Dijkstra 相比几乎没有优势。它们的表现都或多或少相同。
A* 的强大之处在于启发式算法可以将“方向感”编码到算法中。如果您的目标节点位于您的北方，那么开始搜索向北的路径是有意义的。但在完美的迷宫中，这种方向感是没有用的。向北的道路可能是一条死胡同，你将被迫原路返回。 A* 更适合障碍物稀疏的开放网格。
将其设置为 h(i) + h(j) 或多或少会使启发式的权重因子加倍。我认为，如果您使用类似 f(i) = g(i) + h(i) * 1.5 或 f(i) = g( i) + h(i) * 2 这将使算法更加贪婪，更有可能检查更接近目标的节点。缺点是，你不再保证找到最短路径，你会找到/any/路径。但在完美迷宫中，只能找到一条路径，因此在这种情况下这不是真正的问题。
I wrote an online widget that allows you to experiment with a few path finding algorithms.用它画一个迷宫，看看“贪婪”选项的效果。
关于algorithm - 研究 A* 算法的一些变体，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/67145653/