前言

前面的Dijkstra算法能很好的求出一个位置到其他所有位置的路径。但是实际项目中，我们更多的只需要求一个位置到另一个位置的路径。

在这个问题上，我们可以运行Dijkstra算法直到计算出到目标点的路径便终止。

A*算法是Dijkstra算法的修改版本，它每次前进会优先考虑看起来更接近目标点的路径。

算法核心

A*算法的核心公式：
f(n)=g(n)+h(n)
g(n) 表示起点到点 n 的实际距离，这个距离是在算法实现过程中算出来的。

  • 如果公式没有 h(n)，相当于使用Dijkstra算法求解。

h(n) 表示点 n 到目标点的估计距离，这个距离是在算法执行前估计出来的。

  • 常用的评估函数有 欧几里得距离，曼哈顿距离，切比雪夫距离 等等。

算法流程

A*算法的代码与Dijkstra算法十分相像，只是在拓展的时候选择f(n)最大的点而不是g(n)最大的点即可。

  • A*算法作为一种启发式搜索算法，可以使搜索向着最有希望的方向前进，运行时能更快的找到目标点。
  • 结果虽然不一定是最优解，但总会是令人接受的解，在工程中十分实用。