带有墙壁的网格,其实是一张换了外观的图:每个可通行格子是节点,相邻格子之间上下左右的移动是边。网格搜索很适合用来入门图搜索,因为你能直接看见搜索前沿如何在地图上扩展,抽象的图很难带来同样的直观感受。
本文介绍三种经典的网格搜索算法:BFS、A* 和 DFS。除了代码,还提供实时交互示例,让你在随机地图上观察搜索过程,同时通过已展开格子数量比较它们的效率。
问题定义
我们有一个 W × H 的网格。部分格子是墙壁(1),其余格子可通行(0)。给定起点和终点,每次只能向上下左右移动一格。我们想知道:是否存在路径,以及怎样找到一条合适的路径?
下面会反复出现两个指标:
expanded(已展开):算法从数据结构中取出并实际检查过的格子数量,反映搜索的实际工作量。frontier(搜索前沿):当前等待检查的格子数量,也就是正在向外推进的“波前”。
广度优先搜索(BFS)
BFS 按照与起点距离递增的顺序逐层探索:先检查一步可达的格子,再检查两步可达的格子,以此类推。它使用先进先出的队列。一整层处理完之后才会进入下一层,所以第一次到达终点时,得到的一定是按移动步数计算的最短路径。
from collections import deque
def neighbors(cell, grid):
x, y = cell
for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nx, ny = x + dx, y + dy
if 0 <= ny < len(grid) and 0 <= nx < len(grid[0]) and grid[ny][nx] == 0:
yield (nx, ny)
def reconstruct_path(came_from, goal):
path = []
cur = goal
while cur is not None:
path.append(cur)
cur = came_from[cur]
return path[::-1]
def bfs_path(grid, start, goal):
q = deque([start])
came_from = {start: None}
while q:
cur = q.popleft()
if cur == goal:
break
for nb in neighbors(cur, grid):
if nb not in came_from:
came_from[nb] = cur
q.append(nb)
if goal not in came_from:
return None # 不存在可行路径
return reconstruct_path(came_from, goal)
缺点在交互示例里非常明显:BFS 会向所有方向均匀扩展,探索许多远离终点的区域。它简单、能保证最优,但在开阔地图上会检查很多原本不必访问的格子。
A*:带指南针的 BFS
A* 保留了最短路径搜索的思路,同时利用方向信息减少盲目扩展。每个候选格子的评分为 f = g + h:
g:目前已经走过的实际距离;h:启发式估计,也就是对剩余距离的估计值。对于只能上下左右移动的网格,曼哈顿距离是合适的可采纳启发式。
A* 使用按照 f 排序的优先队列,而不是普通队列。配合正确的代价更新,只要 h 不高估剩余距离,仍能找到最短路径。更接近终点、h 较小的格子会优先得到探索,因此通常能减少工作量。
import heapq
def manhattan(a, b):
return abs(a[0] - b[0]) + abs(a[1] - b[1])
def a_star(grid, start, goal):
open_q = [(0, start)] # (f 评分, 格子)
g = {start: 0}
came_from = {}
while open_q:
f, cur = heapq.heappop(open_q)
if cur == goal:
return reconstruct_path(came_from, goal)
for nb in neighbors(cur, grid):
tentative = g[cur] + 1
if tentative < g.get(nb, float("inf")):
came_from[nb], g[nb] = cur, tentative
heapq.heappush(open_q, (tentative + manhattan(nb, goal), nb))
return None
交互示例中,A* 的 expanded 往往明显更小:BFS 像水一样向四周铺开,A* 则更集中地朝终点推进。
DFS:沿一条路深入
深度优先搜索使用后进先出的栈。它选中一条通道后就尽可能深入,走不通时再回溯。它可以较快找到一条路径,但通常不是最短路径;在大型网格上,也可能绕很远才回头。递归搜索栈通常与搜索深度有关,而这里的网格实现还会存储已发现节点和父节点,最坏仍需要 O(W·H) 空间。
def dfs_path(grid, start, goal):
stack = [start]
came_from = {start: None}
while stack:
cur = stack.pop()
if cur == goal:
return reconstruct_path(came_from, goal)
for nb in neighbors(cur, grid):
if nb not in came_from:
came_from[nb] = cur
stack.append(nb)
return None
动画尤其适合展示 DFS:你能看见它沿着一条路径冲出去、遇到死路再回溯。如果只看最终返回的路径,很难理解这种行为。
交互实验:随机地图寻路
在同一张地图上运行三种算法,观察搜索如何逐步扩展。每张地图都由一个随机种子生成,修改种子或点击 🎲 就能换一张地图,也可以调整宽度和高度。生成器保证起点到终点至少有一条可行路径。点击 ▶ 开始,即可逐帧观看。网格颜色含义为:灰色是墙壁、紫色是起点、红色是终点、蓝色是搜索前沿、浅灰色是已访问区域、橙色是最终路径,具体见下方图例。状态行显示“已展开”和“搜索前沿”,对应前文的两个指标。
随机地图寻路
PythonYour output will appear here.
试着给三种算法设置相同的种子:BFS 与正确实现的 A* 都能找到最短路径,具体路线可能因选择顺序而不同,A* 通常展开更少的格子。DFS 也能找到路径,但往往更长。
算法比较
| 算法 | 最短路径 | 额外探索 | 内存 | 适用场景 |
|---|---|---|---|---|
| BFS | 是 | 向所有方向扩展 | 队列和访问记录,最坏 O(W·H) | 小地图,或需要最短路径 |
| A* | 是 | 利用启发式优先探索更有希望的格子 | 堆和代价记录,最坏 O(W·H) | 较大地图,需要最短路径且希望减少展开 |
| DFS | 否 | 可能深入很远 | 本文的栈和访问记录,最坏 O(W·H) | 只需要找到一条路径 |
在网格上,BFS 和 DFS 的时间复杂度为 O(V+E),其中 V 是格子数、E 是相邻关系数;使用堆的 A* 还需要考虑优先队列操作的开销。在 20×20 的地图上,交互示例主要展示的是搜索速度的直观差异,以及各算法实际访问了多少格子。
接下来可以探索什么
很多游戏 AI 都建立在这套工具之上。贪吃蛇算法文章 使用同样的思路寻找食物:把蛇身视为墙壁,再调用 bfs_path,就能得到一个虽然朴素却能运行的贪吃蛇大脑。
进一步的难点在于:当墙壁会移动(例如蛇尾)、地图大到无法完整扫描,或者希望蛇始终存活时,该怎么办?可达性检查、追尾策略和哈密顿回路,都会在那篇文章中继续讨论。