← Back to the notebookVEINSURE / WRITING

Technical Articles

网格搜索:BFS、A* 与 DFS

带有墙壁的网格其实就是一张图。通过代码和实时交互示例,比较 BFS、A* 与 DFS 在保证可达的随机地图上的搜索过程。

带有墙壁的网格,其实是一张换了外观的图:每个可通行格子是节点,相邻格子之间上下左右的移动是边。网格搜索很适合用来入门图搜索,因为你能直接看见搜索前沿如何在地图上扩展,抽象的图很难带来同样的直观感受。

本文介绍三种经典的网格搜索算法: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:你能看见它沿着一条路径冲出去、遇到死路再回溯。如果只看最终返回的路径,很难理解这种行为。

交互实验:随机地图寻路

在同一张地图上运行三种算法,观察搜索如何逐步扩展。每张地图都由一个随机种子生成,修改种子或点击 🎲 就能换一张地图,也可以调整宽度和高度。生成器保证起点到终点至少有一条可行路径。点击 ▶ 开始,即可逐帧观看。网格颜色含义为:灰色是墙壁、紫色是起点、红色是终点、蓝色是搜索前沿、浅灰色是已访问区域、橙色是最终路径,具体见下方图例。状态行显示“已展开”和“搜索前沿”,对应前文的两个指标。

随机地图寻路

Python
算法
主程序
render
OUTPUTLoading editor…

Your output will appear here.

Runs locally in your browser · Pyodide 0.26.4 · 10s execution limit / 30s for visualizations · 64 KiB output

试着给三种算法设置相同的种子: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,就能得到一个虽然朴素却能运行的贪吃蛇大脑。

进一步的难点在于:当墙壁会移动(例如蛇尾)、地图大到无法完整扫描,或者希望蛇始终存活时,该怎么办?可达性检查、追尾策略和哈密顿回路,都会在那篇文章中继续讨论。

END OF NOTEBack to top ↑

Search the notebook

Search published writing. Use ↑ ↓ to select, Enter to open.