算法: 聪明的 A* 算法

2019-02-16 本文已影响22人写代码的海怪

问题

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

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

既然要优先找右边两个，那就要用到优先级了。A* 算法在访问每个节点时会给每个节点设置优先级，叫作 f 值。即选择哪个节点作为下一个节点会参考 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 加了一个优先级，在图论里可能使用十分简单，就是判断优先级就完了。但是在方格布局（如下图）就有点麻烦了。