数据结构与算法 / 系统课时
BFS 状态爆炸怎么控制
BFS 状态爆炸怎么控制
带钥匙、开关、剩余次数的 BFS 难点通常不是队列,而是“同一个位置是否算同一个状态”。如果把所有历史都塞进状态,空间会迅速爆炸;如果压缩过度,又会错误剪掉仍有价值的路径。本节建立可执行的状态设计与压缩方法。
学习目标
- 能判断哪些变量会影响后续可选动作,并据此定义完整 BFS 状态。
- 能用位掩码压缩多个布尔条件,正确设计访问标记。
- 能估算状态空间上界,并通过去重和支配关系控制无效状态。
状态为什么会比位置更多
普通网格 BFS 可以把 (row, col) 作为唯一状态,因为两次到达同一格后,未来可走的路径完全相同。但如果角色第一次到达时没有钥匙,第二次到达时已经拿到钥匙,两种情况能够打开的门不同,不能合并。
因此应使用 (row, col, extra) 表示顶点,其中 extra 只保存会改变未来决策的信息。例如钥匙集合、开关状态、还剩几次破墙机会。已经走过的完整路径通常不会影响未来,就不应该放入状态。

错误做法是只记录 visited[row][col]。它会认为“这个位置来过了”,从而把携带不同资源再次到达的状态直接丢弃,导致本来存在的路径被错误剪枝。
只保留影响未来的变量
设计状态时可以问一个问题:如果两个搜索节点拥有这些变量的相同取值,它们从现在开始的合法动作是否完全一致? 如果答案是肯定的,状态通常已经足够;否则还缺少变量。
例如“最多允许破墙两次”,需要保存剩余次数或已使用次数;“踩过哪些普通空地”通常无需保存,因为访问普通空地不会改变后续规则。若把整条路径中的访问历史也编码进去,原本多项式规模的问题很容易膨胀成指数级状态空间。
对于 R × C 网格和 K 个独立的二值开关,最直接的状态上界约为 R × C × 2^K。这也是为什么十几个布尔条件还能使用位掩码 BFS,而几十个独立条件通常需要寻找更强的结构或剪枝。
用位掩码压缩钥匙集合
当额外状态由若干“有或没有”的条件构成时,可以给每个条件分配一个二进制位。下面的例子搜索收集所有钥匙的最短步数:小写字母是钥匙,大写字母是对应的锁,# 是障碍。
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)}')预期输出
steps = 8这里两个钥匙只需要两个 bit。取得钥匙时执行按位或,把对应位设为 1;经过锁时检查对应位。集合比较、复制和哈希因此都变成了整数操作。
用去重和支配关系继续剪枝
第一层控制永远是精确去重:只有 (位置, 额外状态) 完全相同才直接丢弃。BFS 第一次到达某个完整状态时已经使用最少步数,因此以后再次到达相同状态不会得到更短路径。
某些题还存在支配关系。例如在同一位置、步数不更多的前提下,持有钥匙集合 A 包含集合 B,那么 A 往往比 B 更有能力,B 可能被淘汰。但这种剪枝必须依据题目规则证明:如果携带更多资源可能产生额外代价或限制,就不能简单按照集合包含关系删除状态。
状态设计正确后,再估算 位置数量 × 额外状态数量 是否可承受。如果上界已经远超内存或时间限制,就应继续寻找对称性、支配关系或问题特有的压缩,而不是指望更换队列实现解决指数级增长。