研究 A* 算法的一些变体
Studying some variants of the A* algorithm
我最近开始学习 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* 的强大之处在于启发式算法可以将 'sense of direction' 编码到算法中。如果你的目标节点在你的北方，那么开始向北搜索路径是有意义的。但是在完美的迷宫中，这种方向感是没有用的。向北的道路可能是死胡同，你将被迫原路返回。 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.用它来画迷宫，看看“贪心”选项的效果
我最近开始学习 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* 的强大之处在于启发式算法可以将 'sense of direction' 编码到算法中。如果你的目标节点在你的北方，那么开始向北搜索路径是有意义的。但是在完美的迷宫中，这种方向感是没有用的。向北的道路可能是死胡同，你将被迫原路返回。 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.用它来画迷宫，看看“贪心”选项的效果