1.1 状态空间、BFS、DFS 与一致代价搜索：先定义什么算同一个局面
搜索算法的差别常被压缩成“队列还是栈”。真正决定正确性和成本的，是问题表示、边代价、重复状态和停止条件。
本课目标
- 用状态、动作、转移、目标和路径代价定义搜索问题；
- 区分 tree search 与 graph search；
- 说明 BFS、DFS 和 Uniform-Cost Search 的完整性与最优性条件；
- 返回一条可验证路径，而不只是
True/False。
1. 一个搜索问题的六个部件
可以把问题写成：
initial_state：从哪里开始
actions(state)：当前允许哪些动作
transition(state, action)：动作产生什么后继
goal_test(state)：怎样算到达目标
step_cost(state, action, next_state)：一步代价
state_key(state)：怎样判断两个状态等价路径是动作/状态序列；解是到达目标的路径；最优解还需要明确总成本。若目标只是“步数最少”，每步代价可以设为 1；若道路距离、风险或时间不同，就不能用 BFS 代替最低代价搜索。
2. 状态表示会改变搜索空间
同一迷宫可表示为：
- 像素、方向、速度和背包内容的完整世界状态；
- 只保留当前位置的网格状态；
- 把房间压成节点、走廊压成边的拓扑图。
抽象太细，分支和深度爆炸；抽象太粗，不同真实局面被合并，可能返回不可执行路径。
状态 key 必须包含所有会影响未来动作、目标和代价的信息。例如门是否打开会改变可达性，就不能只用坐标去重。相反，若到达某格的历史不影响以后，把整条路径放进 key 会阻止有效合并。
3. Tree search 与 graph search
Tree search 把每条不同路径当成新节点。图中存在环时，它可能反复绕圈。Graph search 用 frontier 与 reached/visited 记录已发现状态，避免或控制重复。
但“见过就永不再看”只在特定算法下正确：
- BFS 在单位边代价下，第一次发现状态已是最少步数；
- DFS 第一次到达不保证最短或最低代价；
- Uniform-Cost/A* 若发现更低
g，需要更新并可能重新打开状态。
如果 BFS 在弹出后才登记 visited，同一节点可能在弹出前多次入队。入队时登记可以避免这类重复；UCS 则记录当前最佳代价。队列里排了三份同一个状态，并不会让答案更有把握。
4. BFS：按深度逐层扩展
下面是 Python 3 函数片段（partial）。调用者提供后继函数和目标判断；状态必须可哈希，且本例保留 None 作为父节点哨兵，不能用它表示真实状态。
from collections import deque
def reconstruct(parent, goal):
path = [goal]
while parent[path[-1]] is not None:
path.append(parent[path[-1]])
return list(reversed(path))
def bfs(neighbors, start, is_goal):
frontier = deque([start])
parent = {start: None} # 同时表示 reached
while frontier:
state = frontier.popleft()
if is_goal(state):
return reconstruct(parent, state)
for next_state in neighbors(state):
if next_state not in parent:
parent[next_state] = state
frontier.append(next_state)
return None在分支因子有限、目标深度有限时，BFS 完整；每步代价相同且非负才保证最低代价。若最浅目标深度为
5. DFS：把内存换成搜索风险
DFS 每次深入一个分支，适合：
- 内存紧张；
- 解可能很深；
- 只需任意解；
- 搜索树有限或有可靠深度界限。
它不保证最浅或最低代价解。在无限深分支中可能永远不到另一个近处目标。Graph DFS 使用全局 visited 时，空间还包括访问集合，不能笼统说“只需要
可用 depth-limited search 防止无限下降，再逐步增加深度形成 iterative deepening DFS（IDDFS）。在单位代价、有限分支下，IDDFS 获得 BFS 的浅层最优性，同时保持接近 DFS 的 frontier 空间，代价是重复展开浅层。
6. Uniform-Cost Search：按累计代价扩展
当边代价不同且非负时，使用优先队列，每次扩展当前累计代价 reconstruct，edges(state) 返回 (后继状态, 有限非负代价)。
import heapq
from itertools import count
def uniform_cost_search(edges, start, is_goal):
tie = count()
frontier = [(0.0, next(tie), start)]
best_g = {start: 0.0}
parent = {start: None}
while frontier:
g, _, state = heapq.heappop(frontier)
if g != best_g.get(state): # 跳过旧队列项
continue
if is_goal(state):
return reconstruct(parent, state), g
for next_state, step_cost in edges(state):
if step_cost < 0:
raise ValueError("UCS requires non-negative edge costs")
new_g = g + step_cost
if new_g < best_g.get(next_state, float("inf")):
best_g[next_state] = new_g
parent[next_state] = state
heapq.heappush(frontier, (new_g, next(tie), next_state))
return NoneUCS 与 Dijkstra 的核心一致。有限图允许零代价边；在无限图上，有限分支和每一步代价至少为某个正数 ε 是常用的完整性条件。仅限制正代价边还不够：无限长的零代价链也可能让搜索迟迟不取出目标。
7. 复杂度不只看节点数
真实系统还要计算：
- 生成后继的成本；
- 状态 key 的大小与 hash 成本；
- parent/动作存储；
- 重复状态率；
- 目标测试与边代价计算；
- 图是否能预先物化。
隐式图（谜题、规划、博弈）通常不能列出全部节点，只能按需生成后继。
8. 正确性测试
起点就是目标
目标不可达
有环和自环
同一状态由多条路径到达
单位代价与非单位代价
零代价边
多个目标
状态 key 过粗/过细对小图可穷举所有简单路径或与可信最短路实现对照，验证路径连续、到达目标和总成本。
例如设 S→G 代价为 9，S→A 和 A→G 各为 2。按这个顺序提供后继时，BFS 返回 [S, G]，UCS 返回 [S, A, G] 和总代价 4。再加入 A→S 的零代价边，两者仍应终止；这能同时检查去重和成本判断。
常见误区
- BFS 总能找到最短路：只在步数/等代价意义下。
- DFS 空间一定是
：graph search 还保存 visited。 - 节点出队时再 visited 没区别：frontier 可能积累大量重复项。
- 状态等于屏幕上看到的全部信息：应保留影响未来的最小充分状态。
练习
- 为带钥匙和门的迷宫设计 state key，解释为何不能只用坐标。
- 在有环图上比较 tree BFS 与 graph BFS 的扩展次数。
- 构造 BFS 选少步高成本、UCS 选多步低成本的图。
- 为 UCS 增加 action 记录，并验证返回路径总成本。
小结
搜索从问题建模开始。BFS、DFS 和 UCS 只是不同 frontier 策略；它们的保证依赖边代价、状态等价和搜索空间条件。
下一课加入启发式：A* 怎样使用目标下界减少无谓扩展，又为什么不一致启发式要求重新打开节点。