算法: 聪明的 A* 算法

问题

当说到求最短路径我们可能首先想到的是用 Dijkstra 算法去做，而使用 Dijkstra 算法基本是以开始节点往外扩散，直到找到终点的。如下图，从开始节点开始扩散就会以同心圆那样扩散，左右的扩散速度是一样。

但是很明显终点在右边呀，我们能不能让 Dijkstra 稍微往右去扩散找呢？即优先找右边那两个点呢？这就是 A* 算法的由来了。

A* 算法思想

既然要优先找右边两个，那就要用到优先级了。A* 算法在访问每个节点时会给每个节点设置优先级，叫作 f 值。即选择哪个节点作为下一个节点会参考 f 值。f 值有以下公式

• g 值：开始节点到当前节点的距离
• h 值：当前节点到终点节点的估算距离，为什么叫估算呢？要是你知道那不就不用去求最短路径了嘛，这个估算值有很多种算法去估，这里就假设你都知道这个估算值了

关键的步骤来了，首先会检测当前节点里相邻的节点，并选择 f 值最小的节点，把它作为当前要处理的节点。然后动态规划方程判断和更新最短路径。

if (dist[v] > didst[u] + length(u -> v)):
    dist[v] = dist[v] + length(u -> v)
    pred[v] = u

后面就一直重复选节点和更新路径了。

总结

A* 算法其实就是 Dijkstra 加了一个优先级，在图论里可能使用十分简单，就是判断优先级就完了。但是在方格布局（如下图）就有点麻烦了。

具体请参考 A星算法详解(个人认为最详细,最通俗易懂的一个版本)