A* 搜索

Dijkstra 算法能找到通往终点的最短路线,但它同时朝每个方向搜索,连远离终点的方向也不放过。A* 搜索只多加了一点信息:对终点还有多远的估计,搜索便一下子直奔终点。

一张图:已确定的节点从起点朝终点形成一条窄带,一条虚线直指终点,下方画着队列
一张图:已确定的节点从起点朝终点形成一条窄带,一条虚线直指终点,下方画着队列

基本思路

在地图上找路线时,你不会像对待通往目的地的道路那样,仔细探索背离目的地的道路。A* 搜索也是这样。每个节点都有一个得分:从起点到目前的距离 g,加上对剩余距离的估计 h。搜索总是从得分最低的节点继续,所以朝向终点的节点排在前面。

逐步过程

把起点的距离设为 0,以得分 h(start) 放入队列。重复以下步骤:取出得分最低的节点,把它的距离标为确定。如果它是终点,就停止:沿记下的节点往回走就得到路径。否则,对每个尚未确定的邻居,算出经过该节点到它的距离。如果比它目前的距离短,就更新它,记下该节点作为来路,并把邻居的得分设为新距离加上它的估计值。两个得分相等时,先取估计值较小的节点通常能更快到达终点。

一个例子

设起点为 A,终点为 D。A–B 长 2,B–D 长 2,而 A–C 长 1,C–D 长 5。到 D 的直线估计:A 为 3,B 为 2,C 为 3。A 的初始得分为 0 + 3 = 3。取出 A 后,B 的得分为 2 + 2 = 4,C 的得分为 1 + 3 = 4。得分相同,A* 取估计值较小的 B,B 让 D 的得分为 4 + 0 = 4。现在 D 得分最低且估计最小,于是被取出:最短路径是 A → B → D,长度为 4,而走错方向的 C 从未被确定。Dijkstra 算法则会先确定 C,因为它是离 A 最近的节点。

好的估计

估计值绝不能超过到终点的真实距离;这样的估计称为可采纳的,有了它,A* 总能找到最短路径。直线是可采纳的,因为没有哪条路线比直线更短。如果从一个节点到下一个节点,估计值的下降也从不超过边的长度,它就是一致的,已确定的节点永远不需要再查看。估计越接近真实值,A* 需要的节点越少。估计为 0 是可采纳的,但没有用处:A* 这时就变成了 Dijkstra 算法。估计过大会让 A* 更快,但可能错过最短路径。

历史与应用

斯坦福研究所的 Peter Hart、Nils Nilsson 和 Bertram Raphael 在研制最早的移动机器人之一 Shakey 时,于 1968 年发表了 A*。他们更早的版本叫 A1 和 A2;星号标志着他们证明为最优的那个版本。如今,A* 在电子游戏中让角色绕过障碍物,规划路线和机器人运动,还能求解 15 数码等谜题,其中的估计把每个方块离原位的距离加起来。

沙基,斯坦福研究所的移动机器人,摄于计算机历史博物馆。彼得·哈特、尼尔斯·尼尔森和伯特伦·拉斐尔在研制它的过程中于1968年发表了A*。
沙基,斯坦福研究所的移动机器人,摄于计算机历史博物馆。彼得·哈特、尼尔斯·尼尔森和伯特伦·拉斐尔在研制它的过程中于1968年发表了A*。

动手试试

打开应用,按“单步”。边上的数字是边的长度,这里与画出来的长度一致,虚线表示到终点的直线估计。图下方的队列按得分列出节点,最低的在前。终点确定后,状态栏会比较 A* 确定了多少个节点,以及 Dijkstra 算法需要多少个。在大图中把终点放在远处的角落,就能看到最大的差别。

常见问题

A* 中的星号是什么意思?

Hart、Nilsson 和 Raphael 最早描述的算法叫 A1 和 A2。A*(“A星”)是他们证明过的版本:当估计是一致的时,在使用同一估计的同类算法中,它展开最少的节点就能找到最短路径。

A* 的时间复杂度是多少?

最坏情况下,估计毫无用处,A* 的工作量和 Dijkstra 算法相同:使用二叉堆时为 O((V + E) log V)。有了好的估计,它只需确定一小部分节点,所以在实际中很快。

怎样的启发式适合 A*?

它应该计算快,从不高估真实距离,并且尽量接近真实距离。在只能上下左右移动的网格上,常用曼哈顿距离;在地图上,则用直线距离。

如果启发式高估了会怎样?

那么 A* 可能返回一条不是最短的路径,因为它可能在查看更好的路线之前就结束了。有些程序故意这样做(加权 A*),用一点路径质量换取大幅提速。

准备好尝试了吗?

在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。

试试 A* 搜索