数据结构与算法 / 系统课时

BFS 状态爆炸怎么控制

BFS 状态爆炸怎么控制

带钥匙、开关、剩余次数的 BFS 难点通常不是队列,而是“同一个位置是否算同一个状态”。如果把所有历史都塞进状态,空间会迅速爆炸;如果压缩过度,又会错误剪掉仍有价值的路径。本节建立可执行的状态设计与压缩方法。

学习目标

  • 能判断哪些变量会影响后续可选动作,并据此定义完整 BFS 状态。
  • 能用位掩码压缩多个布尔条件,正确设计访问标记。
  • 能估算状态空间上界,并通过去重和支配关系控制无效状态。

状态为什么会比位置更多

普通网格 BFS 可以把 (row, col) 作为唯一状态,因为两次到达同一格后,未来可走的路径完全相同。但如果角色第一次到达时没有钥匙,第二次到达时已经拿到钥匙,两种情况能够打开的门不同,不能合并。

因此应使用 (row, col, extra) 表示顶点,其中 extra 只保存会改变未来决策的信息。例如钥匙集合、开关状态、还剩几次破墙机会。已经走过的完整路径通常不会影响未来,就不应该放入状态。

位置与钥匙状态组成的 BFS 状态空间

错误做法是只记录 visited[row][col]。它会认为“这个位置来过了”,从而把携带不同资源再次到达的状态直接丢弃,导致本来存在的路径被错误剪枝。

只保留影响未来的变量

设计状态时可以问一个问题:如果两个搜索节点拥有这些变量的相同取值,它们从现在开始的合法动作是否完全一致? 如果答案是肯定的,状态通常已经足够;否则还缺少变量。

例如“最多允许破墙两次”,需要保存剩余次数或已使用次数;“踩过哪些普通空地”通常无需保存,因为访问普通空地不会改变后续规则。若把整条路径中的访问历史也编码进去,原本多项式规模的问题很容易膨胀成指数级状态空间。

对于 R × C 网格和 K 个独立的二值开关,最直接的状态上界约为 R × C × 2^K。这也是为什么十几个布尔条件还能使用位掩码 BFS,而几十个独立条件通常需要寻找更强的结构或剪枝。

用位掩码压缩钥匙集合

当额外状态由若干“有或没有”的条件构成时,可以给每个条件分配一个二进制位。下面的例子搜索收集所有钥匙的最短步数:小写字母是钥匙,大写字母是对应的锁,# 是障碍。

python
from collections import deque


def shortest_path_all_keys(grid: list[str]) -> int:
    rows, cols = len(grid), len(grid[0])
    key_to_bit: dict[str, int] = {}
    start = None

    # 只为实际出现的钥匙分配连续 bit,避免浪费状态空间。
    for r in range(rows):
        for c in range(cols):
            ch = grid[r][c]
            if ch == '@':
                start = (r, c)
            elif 'a' <= ch <= 'z' and ch not in key_to_bit:
                key_to_bit[ch] = len(key_to_bit)

    if start is None:
        return -1

    full_mask = (1 << len(key_to_bit)) - 1
    queue = deque([(start[0], start[1], 0, 0)])
    visited = {(start[0], start[1], 0)}
    directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]

    while queue:
        r, c, mask, steps = queue.popleft()
        if mask == full_mask:
            return steps

        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if not (0 <= nr < rows and 0 <= nc < cols):
                continue

            ch = grid[nr][nc]
            if ch == '#':
                continue

            next_mask = mask
            if 'a' <= ch <= 'z':
                next_mask |= 1 << key_to_bit[ch]
            elif 'A' <= ch <= 'Z':
                key = ch.lower()
                # 没有对应钥匙时,这扇门不能通过。
                if key not in key_to_bit:
                    continue
                if not (mask & (1 << key_to_bit[key])):
                    continue

            state = (nr, nc, next_mask)
            if state in visited:
                continue

            # 必须按“位置 + 钥匙集合”去重,而不是只按位置去重。
            visited.add(state)
            queue.append((nr, nc, next_mask, steps + 1))

    return -1


grid = [
    '@.a..',
    '###.#',
    'b.A.B',
]
print(f'steps = {shortest_path_all_keys(grid)}')

预期输出

text
steps = 8

这里两个钥匙只需要两个 bit。取得钥匙时执行按位或,把对应位设为 1;经过锁时检查对应位。集合比较、复制和哈希因此都变成了整数操作。

用去重和支配关系继续剪枝

第一层控制永远是精确去重:只有 (位置, 额外状态) 完全相同才直接丢弃。BFS 第一次到达某个完整状态时已经使用最少步数,因此以后再次到达相同状态不会得到更短路径。

某些题还存在支配关系。例如在同一位置、步数不更多的前提下,持有钥匙集合 A 包含集合 B,那么 A 往往比 B 更有能力,B 可能被淘汰。但这种剪枝必须依据题目规则证明:如果携带更多资源可能产生额外代价或限制,就不能简单按照集合包含关系删除状态。

状态设计正确后,再估算 位置数量 × 额外状态数量 是否可承受。如果上界已经远超内存或时间限制,就应继续寻找对称性、支配关系或问题特有的压缩,而不是指望更换队列实现解决指数级增长。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

BFS 状态爆炸怎么控制

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通