假设地图中存在起点和终点，路径搜索算法可以用于搜索起点到终点的路径。在机器人路径规划，或者游戏中都需要用到路径搜索算法。本文介绍一种经典的 A* 算法，和 Dijkstra 算法相比，A* 采用启发式的搜索策略，能够更快地搜索出最短路径。

1.前言

图中的起点和终点

给定一个包含起点 (白色圆点) 和终点 (黑色圆点) 的图，有很多条路径可以从起点到达终点，但是很多不是最短路径。如上图所示，黑色虚线为最短路径，红色虚线不是。

Dijkstra 算法是其中一种求解起点到终点最短路径的算法，在用于无权重图时，Dijkstra 算法就是宽度优先 (BFS) 的方法。A* 对 Dijkstra 进行了优化，引入启发式的搜索策略，可以更快地搜索出最短路径。

2.Dijkstra算法

假设起点是 s，终点是 e，Dijkstra 算法的主要包括下面的流程。

• 步骤一：用一个集合 F 保存已经访问过的节点，初始时 F 只包含起点 s。用一个数组 D 保存起点 s 到其余所有节点的最短路径。在开始时，D 的数值用下面的公式计算。

初始距离数组 D

• 步骤二：找到一个不在 F 中，并且 D[u] 最小的节点 u。D[u] 就是起点 s 到节点 u 的最短距离，把 u 加入 F。
• 步骤三：用节点 u 更新数组 D 中的最短距离，如下面的公式。

更新距离数组 D

• 步骤四：如果 F 中已经包含终点 e，则最短路径已找到，否则继续执行步骤二。

Dijkstra 算法可以用于有权重 (即节点之间的距离是不同的) 和无权重 (节点间距离一样) 的图，如果用于无权重的图，Dijkstra 算法就是 BFS 算法。

下图展示了用 Dijkstra 算法搜索无权重图最短路径的过程，橙色表示算法搜索过的区域，颜色由浅到深，表示搜索的深度 (先后顺序)。浅橙色表示最先搜索到的节点，而深橙色表示最后搜索到的节点。

Dijkstra 算法搜索过程

3.A* 算法

A* 算法加入了启发式的搜索策略，在搜索时间上通常优于 Dijkstra 算法。A* 使用了一个估计值 F 代表某一个节点到终点的估计距离，计算公式如下：

A* 算法估计值 F 计算公式

另外 A* 包含两个列表，open list 和 close list，open list 保存了等待探索的节点，而 close list 表示已经探索过的节点。

A* 算法的流程如下：

• 步骤一：把起点 s 放入到 open list 里面。
• 步骤二：检查 open list，如果终点 e 在 open list 里面，则路径搜索完成。如果 open list 为空，则说明不存在路径。
• 步骤三：在 open list 里面选择估计值 F 最小的节点 u，作为当前节点，然后加入 close list 里面。
• 步骤四：取得所有节点 u 可以直接到达的节点 v，然后更新 open list。更新规则：如果 v 在 close list 里，则不处理；如果 v 不在 open list 里面，则把 v 加入 open list，其对应 F 值为 G(u)+distance(u,v)+H(v)；如果 v 在 open list 里面，则检查 v 是否有更小的 F 值 (如果有更小 F 值，就更新 v 的 F 值)；
• 重复步骤二到步骤四，直到终止。

下面是 A* 搜索最短路径的示例，每一个节点中左边的数字表示 G(n) 即真实距离，右边的数字表示 H(n) 即启发函数计算的距离。F 值就是 G(n)+H(n)，在下面的例子中 H(n) 用曼哈顿距离计算 (在下面的例子中等于没有障碍物时，n 到终点 e 的最短距离)。

A* 算法的例子

4.A* 启发函数的选择与区别

如果不设置启发函数，则 A* 就是 Dijkstra 算法，这时可以找到最短路径。

如果启发函数 H(n) 的值一定小于等于 n 到终点的实际距离，则 A* 可以保证找到最短路径。

如果 H(n) 的值等于 n 到终点的实际距离，则 A* 会直接找到最短路径，而不用扩展搜索额外的节点，此时运行是最快的。

如果 H(n) 的值有可能大于 n 到终点的实际距离，则 A* 算法不一定可以找到最短路径，但是运行速度会比较快。

5.参考文献

Amit’s A* Pages 地址： http://theory.stanford.edu/~amitp/GameProgramming/