The A Star Algorithm

A* 算法的学习笔记

$A*$（A Star）算法是一种经典的路径查找和图形遍历算法，然而一直没有想去好好了解它。路径查找算法在本科课程里就学了 Dijkstra，而且时到今日在脑子里也仅残存一丝丝印象。倒是现在因为工作原因，开始接触一个基于 C++ 的开源项目 Valhalla。听同事说，这个项目里计算起始点到目的点路径的算法，就是业界知名的 $A*$ 算法。正好也借此机会，好好梳理一下学过的知识。

抽象来讲，$A*$ 算法通过下面这个函数来计算每个节点的优先级：

$$f(n)=g(n)+h(n)$$

其中：

• $f(n)$ 是节点 $n$ 的综合优先级。当我们选择下一个要遍历的节点时，我们总会选取综合优先级最高（值最小）的节点。
• $g(n)$ 是节点 $n$ 距离起点的代价。
• $h(n)$ 是节点 $n$ 距离终点的预计代价，这也就是 $A*$ 算法的启发函数。关于启发函数我们在下面详细讲解。

A* 算法在运算过程中，每次从优先队列中选取 f(n) 值最小（优先级最高）的节点作为下一个待遍历的节点。

另外，A* 算法使用两个集合来表示待遍历的节点，与已经遍历过的节点，这通常称之为 open_set 和 close_set。

完整的A*算法描述如下：

* 初始化 open_set 和 close_set；
* 将起点加入 open_set 中，并设置优先级为 0（优先级最高）；
* 如果 open_set 不为空，则从 open_set 中选取优先级最高的节点 n：
    * 如果节点 n 为终点，则：
        * 从终点开始逐步追踪 parent 节点，一直达到起点；
        * 返回找到的结果路径，算法结束；
    * 如果节点 n 不是终点，则：
        * 将节点 n 从 open_set 中删除，并加入 close_set 中；
        * 遍历节点 n 所有的邻近节点：
            * 如果邻近节点 m 在 close_set 中，则：
                * 跳过，选取下一个邻近节点
            * 如果邻近节点 m 也不在 open_set 中，则：
                * 设置节点 m 的 parent 为节点 n
                * 计算节点 m 的优先级
                * 将节点 m 加入 open_set 中

上面已经提到，启发函数会影响 A* 算法的行为。

• 在极端情况下，当启发函数h(n)始终为0，则将由g(n)决定节点的优先级，此时算法就退化成了Dijkstra算法。
• 如果h(n)始终小于等于节点n到终点的代价，则A*算法保证一定能够找到最短路径。但是当h(n)的值越小，算法将遍历越多的节点，也就导致算法越慢。
• 如果h(n)完全等于节点n到终点的代价，则A*算法将找到最佳路径，并且速度很快。可惜的是，并非所有场景下都能做到这一点。因为在没有达到终点之前，我们很难确切算出距离终点还有多远。
• 如果h(n)的值比节点n到终点的代价要大，则A*算法不能保证找到最短路径，不过此时会很快。
• 在另外一个极端情况下，如果h()n相较于g(n)大很多，则此时只有h(n)产生效果，这也就变成了最佳优先搜索。

由上面这些信息我们可以知道，通过调节启发函数我们可以控制算法的速度和精确度。因为在一些情况，我们可能未必需要最短路径，而是希望能够尽快找到一个路径即可。这也是A*算法比较灵活的地方。

对于网格形式的图，有以下这些启发函数可以使用：

• 如果图形中只允许朝上下左右四个方向移动，则可以使用曼哈顿距离（Manhattan distance）。
• 如果图形中允许朝八个方向移动，则可以使用对角距离。
• 如果图形中允许朝任何方向移动，则可以使用欧几里得距离（Euclidean distance）。