有序前沿与路径 · HTML
数学 / 逻辑形态
令 dist[s]=0。FIFO 按非递减 dist 扩展节点；首次发现 v 时设置 dist[v]=dist[u]+1。
识别信号
- 每个动作都计一次，代价完全相同。
- 目标是 minimum moves、fewest transformations 或 nearest。
- 状态图可按需生成，无需预建全部边。
- 需要多源到最近目标时，可把所有源同时放入第 0 层。
容易误判的相似信号
| Signal | Why it is different |
|---|
| 0/1 两种边权 | 权重虽小但不等；普通队列层数不再等于代价，应用 0-1 BFS。 |
| 只问可达 | 若不使用距离，bfs-components 或 DFS 已足够，别把层逻辑复杂化。 |
核心不变量
节点出队时 dist 非递减；首次被发现的距离就是从任一源到它的最少边数。
状态、转移与处理顺序
| Item | Definition |
|---|
| State | 队列、dist（也可兼作 visited）、当前状态及可选 parent。 |
| Transition | 从 u 生成每个合法未访问 v，赋 dist[v]=dist[u]+1 并入队。 |
| Frontier / order | FIFO 队列；其头部总是当前最小层，因所有边都把距离恰加 1。 |
Python 骨架
from collections import deque
def shortest_steps(start, is_goal, neighbors):
q = deque([start])
dist = {start: 0}
while q:
u = q.popleft()
if is_goal(u):
return dist[u]
for v in neighbors(u):
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
return -1
正确性思路
- 队列先处理第 d 层再处理第 d+1 层，因此出队距离非递减。
- 若首次发现 v 的路径不是最短，则更短路径的前驱应位于更早层并先发现 v，矛盾。
- 目标出队时所有可能更短的节点已处理，故可安全提前返回。
复杂度
| Time | Space | Parameters |
|---|
| O(V+E) | O(V) | V、E 指实际可达状态及生成的转移；隐式图也按这些量计。 |
边界条件
- 起点就是目标时返回 0。
- 目标不可达时队列耗尽返回约定哨兵。
- 多源 BFS 必须把所有源都设为距离 0。
- 状态若可哈希但很大，需设计紧凑编码。
错误模式
| Pattern | Why it fails / fix |
|---|
| 目标生成时过早返回 | 标准等权 BFS 在发现时也可正确，但统一在出队检查更易扩展到其他前沿并避免边界特判。 |
| 按层循环却层数错位 | 用 dist 随节点保存通常比手工 level 增减稳。 |
| 把 visited 与合法性混在一起 | 先判断状态合法，再判断是否已发现。 |
选择与排除规则
- 所有转移代价恒为同一正数：BFS。
- 代价仅为 0/1：换 deque 的 0-1 BFS。
- 多个等价起点求最近距离：多源同时入队。
相关模板
原创微型例子
| 环节 | 内容 |
|---|
| Result | 最少 3 步，例如 0→2→4→5。 |
| Setup | 状态 x 每步可变为 x-1 或 x+2，求 0 到 5 的最少动作。 |
| Trace | 层 0={0}，层 1={-1,2}，层 2 包含 1,4，层 3 首次到 5。 |
Recall prompts
我的补充