图搜索的经典启发式算法A星(A*、A Star)算法详解

---

1. 引言

在许多场景中，我们常会遇到一类问题，即“找到一个位置到另一个位置的距离最短（用时最少）的路径”，解决这类问题可以将实际问题映射到一张网络图上，并通过图搜索算法进行求解，这里所说的图搜索算法指的是一系列基于图的算法，而本文将介绍的 A* 算法是其中最为流行的启发式搜索算法，由于 A* 算法结合了其他的基础图搜索的特点，因此本文将从最简单的图搜索算法“广度优先搜索”开始介绍，逐步扩展至 A* 算法。

刚才提到，图搜索算法都需要基于一张图，即将实际的复杂的地图映射成具有固定节点（$Nodes$）和边（$Edges$）的图（$Graph$），有些边是有方向限制的，为弧 $Arcs$。具体的映射方式很多，即同样一张地图，可以映射成具有 $10$ 个节点的路线图，也可以映射成 $100$ 个节点的网格图，在求解过程中，节点数越多的图的求解时间越长，尽管它在一定程度上更能近似于实际情况且更易处理。

2. 广度优先搜索

广度优先搜索（Breadth First Search, BFS）原本是一种在树形数据结构中搜索满足给定属性的节点的算法，后在 1961 年由 CY Lee 等人开发成一种路径搜索算法。

在图搜索中，有一个称为待探索边界 $frontier$ 的概念，即图搜索算法基于起点，不断地推进待探索边界，直到该边界触碰到目标点时结束，而由于该算法的特点是在所有方向上平等地探索，因此这个推进待探索边界的过程也被称为“洪水填充$(floodfill)$”，该算法由于简单易实现的特性，在许多寻路和图分析场景都有应用，具体如下图所示。

这里的 $frontier$ 在代码实现中，是一个待探索的节点队列。队列的初始元素为起始点，基于起始点向前一步探索（下一步可以走到哪些节点），将这些相邻节点扩展到 $frontier$ 队列当中，以此类推。每扩展一个节点，记录下该节点的父节点，方便在探索到目标节点后，返回出最优路线。该算法在路径搜索问题上的逻辑如下（伪代码）：

frontier = Queue() 			# 生成一个队列
frontier.put(start)			# 以起点作为开始
came_from = dict() 			# path A->B 存储为 came_from[B] == A
came_from[start] = None		# 存储每个节点的上一个位置

while not frontier.empty(): # 只要边界队列不为空就循环下去
   current = frontier.get() # 从边界中取出一个点
   if current = goal:		# 算法终止机制，判断当前节点是否为目标点
      break					# 路径长度限制、遍历的点数、寻到的目标点数......都可以是终止约束
   for next in graph.neighbors(current): # 基于这个点向相邻的点进行扩展
      if next not in came_from: # 只要这个扩展的点不曾遍历到，就添加到边界中和已遍历节点集合中
         frontier.put(next)
         came_from[next] = current

# 获得最有路线
current = goal 
path = []
while current != start: 
   path.append(current) # 从目标点回溯到起点
   current = came_from[current]
path.append(start)
path.reverse() 			# optional 获得最优路线
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3. Dijkstra 算法

前文的广度优先搜索算法，在待探索边界上，以同样的权重按顺序地推进待探索边界，即认为每个边的权重是一致的，但在实际的许多场景中，连接节点的边的权重往往并不相同，显然，在相同的探索深度下，累计代价最小的节点有更大的概率探索到总代价 $g(n)$ 小的路线，因此基于广度优先搜索的思路，将待探索边界从普通队列变更为优先队列，评估优先顺序时考虑当前节点到起始点的距离（成本）。

常常用 $g(n)$ 表示从起始节点到 $n$ 节点的路径成本。

由于 Dijkstra 算法带有权重地进行探索，改变了 $frontier$ 的推进方向，因此有可能出现多次（不同路线）探索同一个节点的情况，对于已经探索过的节点，如果新路线的累积代价更小，则更新该节点的信息。基于 Dijkstra 算法的伪代码如下：

frontier = PriorityQueue()			# 生成优先队列
frontier.put(start, 0)				# 优先遍历队列中优先度更好（小）的节点
came_from = dict()
cost_so_far = dict()				# 存储节点和起点之间的距离
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
   current = frontier.get()
   if current == goal:
      break
   for next in graph.neighbors(current):
      new_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
         # 判断新的总移动成本，
         cost_so_far[next] = new_cost
         priority = new_cost
         frontier.put(next, priority)
         came_from[next] = current
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

与广度优先搜索算法一样，Dijkstra 算法能保证最终找到最优的路径，而 Dijkstra 算法相比广度优先搜索节省了大量的计算时间。

4. 启发式优先搜索（Heuristic）

前面提到的广度优先搜索和 $Dijkstra$ 算法适合于找单个起点到多个节点的路径；而如果是找单个起点到具体某一个节点的路径，则由于我们的目标很明确，我们希望从目标节点中获取启发信息，例如在探索节点时，优先探索距离目标点更近的节点。当然，这里的“距离近”并不一定是真实距离，它为待探索边界的优先顺序提供了一定的启发信息。

例如：这里用当前点与目标点之间的曼哈顿距离作为启发信息：

def heuristic(a, b):
   # Manhattan distance on a square grid
   return abs(a.x - b.x) + abs(a.y - b.y) # 这里用的简答的曼哈顿距离
1
2
3

4.1 贪心最佳优先搜索

在启发式搜索方法中，最简单易实现的是贪心最佳优先搜索（Greedy Best First Search, GBFS），即优先探索距离目标最“近”的节点，在一些情况下，该算法的效率极高，但对于较为复杂（待障碍物等）的图搜索问题，该算法往往不能保证找到最优的路径。

算法逻辑其实就是在广度优先搜索 $BFS$ 算法上，增加启发信息 $heuristic$，具体的伪代码如下：

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
came_from[start] = None

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break
   
   for next in graph.neighbors(current):
      if next not in came_from:
         priority = heuristic(goal, next)
         frontier.put(next, priority)
         came_from[next] = current
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

对于节点到目标点的估计距离，常常用符号 $h(n)$ 进行表示。

4.2 A*搜索

前面提到的三种图搜索算法都各有优势，而 A* 算法简单而言，就是既学 Dijkstra 算法参考已产生的累积代价，又学了贪心最佳优先搜索参考了与目标节点的启发信息。前者能保证找到最优路线，而后者能提高算法的求解效率。

对于图中的每条边 $(x,y)$，用 $d(x,y)$ 表示边的长度，用 $h(x)$ 表示节点 $x$ 到目标点的估计距离，如果恒满足 $h(x)\le d(x,y)+h(y)$，则可得 $f(x)=h(x)+g(x)\le g(x)+d(x,y)+h(y)=f(y)$，此时 $h$ 满足三角不等式，可以称之具备一致性，通过一致性的 $h$ 函数，能使 A* 算法一定找到最优路径。

具体 A* 算法的计算逻辑伪代码如下：

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
came_from[start] = None
cost_so_far[start] = 0			# 与起点的距离

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break
   
   for next in graph.neighbors(current):
      new_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
         cost_so_far[next] = new_cost
         priority = new_cost + heuristic(goal, next) # 与目标点的估计距离
         frontier.put(next, priority)
         came_from[next] = current
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

A* 算法综合考虑 $g(n)$ 和 $h(n)$，如果 A* 算法中当前点到目标点的估计距离相对于与起点的实际距离很小，与起点的距离主导边界队列的搜索顺序，则 A* 算法表现出 $Dijkstra$ 算法的性能；反之，则表现出类似 $GBFS$ 的搜索性能。

总体而言，$BFS$ 无差别地探索所有的路径，但是复杂度太高，但适用于目标节点未知（寻宝）的情况；$Dijkstra$ 算法能保证找到最短路径，但因为没有用到目标点的信息，在探索方向上会花费大量时间；$GBFS$ 仅向着目标点优化，算法的效率很高，但是不能保证找到最优路径；而 $A^{\ast }$ 算法既考虑了和起点的距离，也考虑了和目标点的距离（两者求和），在预估函数满足一定条件下，能保证找到最优解，效率比 $Dijkstra$ 算法高一些，比 $GBFS$ 算法低一些。