06 · 无信息搜索
⏱ 44 分钟 | 阅读参考 · 先分清:少走几步,和少走几公里,不是一件事。
可以分多次读。第一次先看三条路线的结果;复杂度和独立代码放在后面,需要时再展开。
🎯 一句话
无信息搜索知道能走哪些路、每条路多贵,也能检查是否到达目标;它没有使用“离目标还剩多远”的估计。
同一张地图上,BFS 先找步数少的路线,DFS 先把一条分支往深处探,UCS 则先检查已经花费较少的路线。
“先检查谁”不同,可能得到不同答案。所以选算法之前,先说清你要最少步数、最小代价,还是任意一条可行路线。
- 想先看区别:从同一张地图的三种结果开始。
- 想知道如何省内存:看深度受限和迭代加深。
- 每一步价格不同、仍想保证便宜:看UCS 的条件。
🔁 一、三种出队规则,同一张地图
先认三个词:
| 词 | 在本章中表示什么 |
|---|---|
| 状态 | 当前在哪个城市,例如 Arad |
| 搜索节点 | 一条候选路线的记录:当前城市、走过的路径、累计代价 |
| frontier | 已经生成、还等着检查的候选节点集合 |
同一个城市可能对应几条不同路线,因此会有多个搜索节点。g 表示这条候选路线已经花掉的代价,不是对未来的估计。
先看结果,再决定要不要读代码
任务是从 Arad 去 Bucharest。路的代价是公里数。
| 策略 | 路段数 | 路线长度 | 非目标展开次数 |
|---|---|---|---|
| BFS | 3 | 450 公里 | 8 |
| DFS | 7 | 733 公里 | 7 |
| UCS | 4 | 418 公里 | 12 |
三条路线分别是:
- BFS:Arad → Sibiu → Fagaras → Bucharest。
- DFS:Arad → Timisoara → Lugoj → Mehadia → Dobreta → Craiova → Pitesti → Bucharest。
- UCS:Arad → Sibiu → RimnicuVilcea → Pitesti → Bucharest。
BFS 用较少路段到达,UCS 用较少公里到达。 DFS 这次很快找到一条能走通的路,但没有保证它便宜。这些展开数是这份地图、邻居顺序和代码的结果,不是三种算法永远不变的排名。
一个很短、可独立运行的出队例子
这里只练习“从已有候选里选谁”,不执行完整搜索。每个元组依次是城市、路径、累计公里数。
frontier = [
("Zerind", ["Arad", "Zerind"], 75),
("Sibiu", ["Arad", "Sibiu"], 140),
("Timisoara", ["Arad", "Timisoara"], 118),
]
BFS = lambda f: 0
DFS = lambda f: len(f) - 1
UCS = lambda f: min(range(len(f)), key=lambda i: f[i][2])
for name, pick in [("BFS", BFS), ("DFS", DFS), ("UCS", UCS)]:
print(name, frontier[pick(frontier)][0])
输出依次是 BFS Zerind、DFS Timisoara、UCS Zerind。BFS 和 UCS 这次碰巧选了同一个城市,理由不同:一个看入队先后,一个看代价。
完整实验的规则
- 本实验是有限图上的搜索,所有路长非负;给定地图的路长实际上都大于 0。
- BFS 取最早入队的节点;DFS 取最后入队的节点;UCS 取
g最小的节点,g相同则先入队先取出。 explored是全局集合:一个非目标状态展开后,后续到该状态的候选会被跳过。- 展开指通过检查后,执行“列出后继”的步骤。取出的目标和跳过的重复项都不计入
expanded。 - 目标在取出候选时检查,而不是一生成就立即返回。后面的 UCS 会解释原因。
运行完整罗马尼亚实验:保留地图、路线和三种比较
复制整段到空文件即可运行,不需要安装库。可以改变邻居列表的顺序,观察哪些计数或路线会变。
ROMANIA = {
"Arad": [("Zerind", 75), ("Sibiu", 140), ("Timisoara", 118)],
"Zerind": [("Arad", 75), ("Oradea", 71)],
"Oradea": [("Zerind", 71), ("Sibiu", 151)],
"Sibiu": [("Arad", 140), ("Oradea", 151), ("Fagaras", 99), ("RimnicuVilcea", 80)],
"Timisoara": [("Arad", 118), ("Lugoj", 111)],
"Lugoj": [("Timisoara", 111), ("Mehadia", 70)],
"Mehadia": [("Lugoj", 70), ("Dobreta", 75)],
"Dobreta": [("Mehadia", 75), ("Craiova", 120)],
"Craiova": [("Dobreta", 120), ("RimnicuVilcea", 146), ("Pitesti", 138)],
"RimnicuVilcea": [("Sibiu", 80), ("Craiova", 146), ("Pitesti", 97)],
"Fagaras": [("Sibiu", 99), ("Bucharest", 211)],
"Pitesti": [("RimnicuVilcea", 97), ("Craiova", 138), ("Bucharest", 101)],
"Bucharest": [("Fagaras", 211), ("Pitesti", 101), ("Giurgiu", 90), ("Urziceni", 85)],
"Giurgiu": [("Bucharest", 90)],
"Urziceni": [("Bucharest", 85), ("Hirsova", 98), ("Vaslui", 142)],
"Hirsova": [("Urziceni", 98), ("Eforie", 86)],
"Eforie": [("Hirsova", 86)],
"Vaslui": [("Urziceni", 142), ("Iasi", 92)],
"Iasi": [("Vaslui", 92), ("Neamt", 87)],
"Neamt": [("Iasi", 87)],
}
def search(graph, start, goal, pick):
"""本章有限、非负代价图;返回路径、代价、非目标展开次数。"""
if any(cost < 0 for edges in graph.values() for _, cost in edges):
raise ValueError("本章比较只使用非负边代价")
frontier = [(start, [start], 0)]
explored, expanded = set(), 0
while frontier:
state, path, g = frontier.pop(pick(frontier))
if state == goal:
return path, g, expanded
if state in explored:
continue
explored.add(state)
expanded += 1
for nxt, cost in graph[state]:
if nxt not in explored:
frontier.append((nxt, path + [nxt], g + cost))
return None, None, expanded
BFS = lambda f: 0
DFS = lambda f: len(f) - 1
UCS = lambda f: min(range(len(f)), key=lambda i: f[i][2])
for name, pick in [("BFS", BFS), ("DFS", DFS), ("UCS", UCS)]:
path, cost, expanded = search(ROMANIA, "Arad", "Bucharest", pick)
print(f"{name:4s} 代价={cost:4d} 展开={expanded:2d} {' -> '.join(path)}")
这是一份方便读懂的列表实现,不是高性能通用搜索库:BFS 的 pop(0) 会移动列表,UCS 的 min 会扫描 frontier,每个候选还复制完整路径。复杂度小节会把这些实现成本与理想算法分开。
在这个框架里,BFS、DFS、UCS 的选择规则确实只差 pick。深度受限还要判断深度;迭代加深还要重新启动搜索,不能只改这一行。Berkeley CS188:无信息搜索
🌊 二、广度优先 BFS
BFS 先检查浅层,再检查深层,因此先找到路段数最少的解。 “浅一层”表示少走一步,不表示少花钱。
地图上,Sibiu 的 g=140 会在 Timisoara 的 g=118 之前展开。它没有按公里数排序。
看本次完整取出记录:8次展开为什么不等于第8次取到目标
| 第几次取出 | 城市 | g:公里 | 处理 |
|---|---|---|---|
| 1 | Arad | 0 | 展开 |
| 2 | Zerind | 75 | 展开 |
| 3 | Sibiu | 140 | 展开 |
| 4 | Timisoara | 118 | 展开 |
| 5 | Oradea | 146 | 展开 |
| 6 | Oradea | 291 | 已展开过,跳过 |
| 7 | Fagaras | 239 | 展开 |
| 8 | RimnicuVilcea | 220 | 展开 |
| 9 | Lugoj | 229 | 展开 |
| 10 | Bucharest | 450 | 是目标,返回 |
结论:取出10次,其中8次真正展开、1次重复跳过、1次返回目标。 这四种数字不能互换。
它保证什么
- 完备:若每个节点的后继有限,而且某个解在有限深度,BFS 最终能找到一个解。完备性说的是资源不受限时的保证。
- 最优:BFS 保证最少步数。在所有动作代价相同的常见设定下,最少步数也意味着最小代价。
- 不保证:边价格不同时,步数较少可能更贵;450 和 418 的地图例已经说明这一点。
代价是:一层可能已经很大
假设每个节点都产生10个新孩子,深度12这一层就有 $10^{12}$ 个节点。若一个节点占100字节,光这一层约需100 TB,还没算程序对象、队列等额外开销。
这是理想大树的数量级示例,不是本页20城市的内存消耗。BFS 可能既耗时又耗内存;不能因为主要担心内存,就说时间总能等得起。
⛏️ 三、深度优先 DFS
DFS 先深入当前分支,走不下去再回来尝试其他分支。 栈的“后进先出”会自然产生这种顺序。
本例在 Arad 最后放入 Timisoara,于是先沿这一侧探索。它没有比较哪条路线最终更便宜,所以找到了733公里的路线也会返回。
有限图和无限搜索树,要分开说
Iasi 与 Neamt 互相连通。如果不检查重复,DFS 可能沿 Iasi → Neamt → Iasi → Neamt 一直生成新节点;图只有少数城市,搜索树仍可以无限深。
若在有限图中禁止当前路径重复状态,DFS 能穷尽简单路径,恢复找到可达目标的保证。它仍然不保证最小代价。
本页代码用了更强的全局去重,因此在给定有限地图上也会终止。但全局集合和当前路径不是同一个东西。
| 做法 | 记住什么 | 影响 |
|---|---|---|
| 当前路径防环 | 当前这条路已经过的状态 | 回到上一层时可以撤销;保留其他路线到同一状态的机会 |
全局 explored |
整次搜索中已展开的状态 | 减少重复探索,但需要额外内存;某些算法还必须允许更优候选重开 |
线性搜索空间来自哪里
理想深度优先实现只保留当前路径和各层尚未探索的分支。在分支上界为 $b$、最大深度为 $m$ 时,额外搜索记录可用 $O(bm)$ 空间;固定 $b$ 后,随深度线性增长。
本页列表实现不等于这个省内存版本。 它有全局 explored,还存多份完整路径。不能一边运行这份代码,一边声称内存只保留当前路径。Poole 与 Mackworth:路径防环与多路径剪枝
深度受限、IDS 和后面的 IDA* 都利用深度优先的低搜索空间特性,再补充截止条件或逐轮探索;不意味着这些方法永远不会内存不足。
✂️ 四、深度受限搜索
给 DFS 一个深度上限 $k$:已经走了 k 步,就不再往下生成孩子。 起点深度记为0。
- 若最浅解深度为 $d$,而 $k<d$,当然看不到解。
- 若后继有限、$k\ge d$,并且没有错误地剪掉仍有机会的路径,就能在限制内找到一个解。
- 它不一般保证最优:同一轮内仍可能先找到一个更深或更贵的解。
“这一轮被深度限制挡住了”和“已经穷尽,没有解”也不同。前一种情况可以再加深,后一种情况不应无限重试。
k很大也不是免费:可能先在不必要的深分支里花很多时间。若上限已经覆盖整棵有限搜索树,它就与没有深度限制的DFS行为相同。
为什么不能机械复用永久闭集
设上限为3。到同一个状态 X,可能先走 S → A → X,只剩1步预算;后来走 S → X,却还剩2步。
如果第一次看到 X 后就永久禁止再处理它,第二条虽然更短、能继续走到目标的路线也会被挡住。下一段代码用当前路径防环,保留这种机会。
独立运行:深度2被挡住,深度3能找到解
这是一个明确的小图,不是罗马尼亚地图。每条边算一步,目标是 G。
GRAPH = {"S": ["A", "X"], "A": ["X"], "X": ["Y"], "Y": ["G"], "G": []}
def depth_limited(graph, start, goal, limit):
def visit(path, remaining):
state = path[-1]
if state == goal:
return "找到", path
children = [nxt for nxt in graph[state] if nxt not in path]
if not children:
return "无解", None
if remaining == 0:
return "深度截止", None
saw_cutoff = False
for nxt in children:
status, result = visit(path + [nxt], remaining - 1)
if status == "找到":
return status, result
saw_cutoff = saw_cutoff or status == "深度截止"
return ("深度截止" if saw_cutoff else "无解"), None
return visit([start], limit)
def iterative_deepening(graph, start, goal):
limit = 0
while True:
status, path = depth_limited(graph, start, goal, limit)
if status != "深度截止":
return limit, status, path
limit += 1
for limit in (2, 3):
print("DLS", limit, depth_limited(GRAPH, "S", "G", limit))
print("IDS", iterative_deepening(GRAPH, "S", "G"))
深度2返回“深度截止”;深度3找到 S → X → Y → G。IDS 也在上限3这一轮找到它。
这里为了可读,仍复制 path 列表;它示范截止与防环逻辑,不作为严格 $O(bk)$ 内存实现的基准。
地图中,k能不能提前算出来
本章罗马尼亚图的无权直径为9:所有城市对的最少路段数中,最大值是9;对应的最远一对是 Neamt 和 Lugoj。
因此,采用不会漏掉限制内路径的深度受限搜索时,$k=9$ 足以找到任意两城之间的一条路线。它不保证这条路线公里数最少。
这个9来自对整张图的检查,不是搜索算法凭空知道的先验。真实任务中,常常没有一个事先算好的深度上限。
⭐ 五、迭代加深 IDS:重复的工作有多贵
不知道解多深,就依次把深度上限设为0、1、2……。 每轮重新做一次深度受限搜索;找到解就停。
它确实会重复工作。是否划算,要看浅层相对于最深一层有多小,而不是直接记住“只多11%”。
先算一棵规则树
下面只统计访问次数:包括访问达到深度上限、因而不再生成孩子的节点。它不是前面地图实验的 expanded,也不是秒数。
假设每个节点都有 $b$ 个孩子,各轮都把对应深度完整访问,直到深度 $d$。深度 $i$ 的节点会被访问 $d+1-i$ 次。
$$N_{\text{IDS}}=\sum_{i=0}^{d}(d+1-i)b^i$$
读法:这一层有多少节点 × 这一层被访问多少遍,再把各层相加。
按层展开就是:$(d+1)b^0+d\,b^1+\dots+2b^{d-1}+b^d$。
当 $b=10,d=5$ 时:
| 方式 | 按层累计的访问数 | 合计 |
|---|---|---|
| 只跑一次深度5 | 1 + 10 + 100 + 1,000 + 10,000 + 100,000 | 111,111 |
| 依次跑深度0—5 | 6 + 50 + 400 + 3,000 + 20,000 + 100,000 | 123,456 |
多12,345次访问,约多 11.1%。最后一层的100,000个节点约占单轮总数90%,而它只访问一次,所以重复浅层的代价相对小。
分支少时,结论就不同
| 树的设定 | 只跑最深一轮 | IDS各轮合计 | 多访问多少 |
|---|---|---|---|
| b=10,d=5 | 111,111 | 123,456 | 约11.1% |
| b=2,d=5 | 63 | 120 | 约90.5% |
| b=1,d=20:一条链 | 21 | 231 | 1,000% |
IDS 不是固定收取11%的时间代价。 上表还是完整规则树的访问计数;实际找到目标的位置、重复状态、后继生成成本也会影响运行时间。
什么时候考虑它
后继有限、存在有限深度解时,正确的 IDS 是完备的。它首先到达最浅解深度;若动作代价相同,就同时得到最小代价解。
它适合“想找浅层解,但不愿保留庞大 BFS frontier”的场景。理想的深度优先实现用 $O(bd)$ 搜索空间,代价是反复访问浅层;不是所有任务的默认最优选择。
下一章的 IDA* 使用类似思想,但逐轮提高的是估计总代价门槛,不是深度门槛。
💰 六、一致代价搜索 UCS
UCS 每次取出累计代价 g 最小的候选。 它不要求每条边一样贵,但保证最小代价需要条件。
本章有限图、非负边、正确按 g 出队并处理重复状态的设定下,UCS 能找到可达目标的最小代价路线。零代价边也可以存在。Berkeley CS188:UCS 的代价条件
若所有边是相同的正代价,按 g 的顺序就是按深度的顺序;再使用相同的 FIFO 并列规则,会得到 BFS 的行为。
为什么目标要等到取出再返回
一个目标候选已经生成,只能说明“找到了一条路”。队列里仍可能有另一条更便宜的路还没走完。
例如 S→G 代价10,而 S→A→G 的两段分别是1和1。生成 G 的10代价路线时就停,会错过2;按 g 取出,则会先检查 A,最后返回便宜的 G。
本次地图为什么展开了 Dobreta
查看12次非目标展开,以及最后取出的目标
| 展开次序 | 城市 | g:公里 |
|---|---|---|
| 1 | Arad | 0 |
| 2 | Zerind | 75 |
| 3 | Timisoara | 118 |
| 4 | Sibiu | 140 |
| 5 | Oradea | 146 |
| 6 | RimnicuVilcea | 220 |
| 7 | Lugoj | 229 |
| 8 | Fagaras | 239 |
| 9 | Mehadia | 299 |
| 10 | Pitesti | 317 |
| 11 | Craiova | 366 |
| 12 | Dobreta | 374 |
| 不计入展开 | 取出 Bucharest,返回 | 418 |
这一次非目标展开的 g 严格递增;一般可能出现相等,保证的是不下降,不是必须严格上升。
Dobreta 在地图西南方向,并不是朝 Bucharest 直奔过去的选择。但到 Dobreta 的代价374仍小于目标的418,UCS 没有理由仅凭方向把它排除。
在本章条件下,到目标前会展开最短起点代价小于最优解代价的可达状态。它没有利用“剩余路程”的下界去排除这些分支。 下一章会把这部分估计加进来。
两个不能省略的边界
负边:不能继续保证最优。 S→A=2、S→G=1、A→G=-3 时,按 g 出队会先返回1;但最便宜的路线是 S→A→G,代价-1。上面的实验函数因此直接拒绝负边输入。
无限空间:非负边还不够保证终止。 若从 S 一边能以代价1到目标,另一边却有无限多个不同状态、沿路代价始终为0,UCS 可能一直优先检查0代价节点。
有限图中的零代价环则不同:全局去重能阻止反复展开同一状态。常见的无限搜索树充分条件是:分支数有有限上界,且每步代价至少为某个固定 $\epsilon>0$。它排除了无限条越来越便宜或零费用的前进步骤。Poole 与 Mackworth:搜索终止的充分条件
↔️ 七、双向搜索:从两头靠近
从起点向前搜索,同时从目标沿反向图找前驱,尝试把两段路线接起来。
前驱指“哪个状态能一步走到这里”。即使实际道路是单向的,只要知道它的前驱关系,也可以在计算时反向搜索;这不要求车辆真的逆行。
收益来自少深入几层
在两端分支相近、各需搜索约一半深度的理想情形,主要节点规模从 $b^d$ 变为约 $2b^{d/2}$。
当 $b=10,d=6$,这两项分别是1,000,000和2,000,相差500倍。这是理想主导项的数量级比较,不是“实测快500倍”。 检查相遇、存储、两边不对称等开销还没计入。
使用前检查三件事
- 能否枚举前驱? 只有正向模拟器、无法找哪些状态通向当前状态时,反向搜索可能很难。
- 能否枚举目标? 少量已知目标可以作为反向搜索的多个起点;像大量“将死”局面那样难以列出的目标集合,会让反向起步困难。
- 能否承担保存 frontier 和相遇检测的内存? 对称双向 BFS 的搜索空间仍约为 $O(b^{d/2})$,只是指数中的深度减少了。
碰到一条连接两端的路,不自动证明它最优。 单位代价的双向 BFS 要按正确层次检查与停止;加权搜索还需相应的代价界,不能随便两个 DFS 一碰面就宣布最短。Poole 与 Mackworth:反向和双向搜索
📊 八、复杂度对照:先看前提,再看式子
只想选方法,可以先读这一张:
| 方法 | 优先做什么 | 常见保证 | 主要代价 |
|---|---|---|---|
| BFS | 浅层候选 | 有限分支下找到最浅解;等步价时最小代价 | 保存宽阔的待处理层 |
| UCS | g小的候选 | 有限图、非负边等条件下最小代价 | 可能检查许多廉价但方向不佳的状态 |
| DFS | 深入当前分支 | 有限图加正确防环可找到解;不一般最优 | 可能深入很久;全局去重另外用内存 |
| 深度受限 | 在k步内深搜 | 不错误剪枝时能找到限制内的解 | k太小会挡住解 |
| IDS | 逐轮加深 | 有限分支下找到最浅解;等步价时最小代价 | 重复访问浅层,换较低搜索空间 |
想比较增长速度:查看理想搜索树的数量级与实际代码的差别
符号先放在这里:$b$ 是分支上界;$d$ 是最浅解深度;$m$ 是最大搜索树深度;$k$ 是深度上限;$C^*$ 是最优代价;$\epsilon$ 是正的单步代价下界。
下表按规则搜索树估计,把生成/处理一个定长节点当作常数工作,使用适合算法的队列/栈与共享父指针。通常讨论 $b>1$;一条链的情况不能照套指数主导项。
| 方法 | 访问/生成节点的数量级 | 额外搜索记录的空间 |
|---|---|---|
| BFS:生成时检查目标 | $O(b^d)$ | $O(b^d)$ |
| BFS:本页取出时检查目标 | 最坏可生成到d+1层,$O(b^{d+1})$ | 最坏 $O(b^{d+1})$ |
| UCS:单步至少ε | $O(b^{1+\lfloor C^*/\epsilon\rfloor})$ | 同一数量级的上界 |
| DFS:有限最大深度m | $O(b^m)$ | 不保存全局闭集时 $O(bm)$ |
| 深度受限k | $O(b^k)$ | 深度优先实现可用 $O(bk)$ |
| IDS:最浅解深度d | 规则分支b>1时 $O(b^d)$ | 深度优先实现可用 $O(bd)$ |
BFS 的两种式子不是矛盾:如果在取出目标前先展开了同层的其他节点,它们可能已经生成下一层。比较资料时要先确认目标测试时机,以及是在数“展开”还是“生成”。
UCS 这一行是搜索树规模的保守上界,不是有限图上基于堆的 Dijkstra 复杂度。后者可按顶点/边数量分析;不能把两个模型的记号混在一起。
上面也不是前面 Python 列表实现的严格运行时间。 前面的全局集合随已展开状态增长;完整路径复制引入与路径长度有关的成本;min 和 pop(0) 也不是常数时间。
因此,线性搜索空间是一种实现条件下的优势,不是“永远不会OOM”。任何方法都有资源边界。
🔗 这一章连到哪里
| 去哪 | 带着什么问题看 |
|---|---|
| 强化学习基础 04 · 动态规划 | 已知转移规则时如何求长期结果?本章是确定性的最短路线;价值迭代还能处理随机转移与期望回报,不能把两者当作同一个算法。 |
| 机器学习与深度学习基础 04 · 决策树:怎么切一刀 | 区分“按什么顺序遍历”和“用什么目标选分裂”。贪婪分裂不等于DFS;模型过拟合也不是路径搜索返回高代价路线的同义词。 |
| 代码题拆解 02 · 树:递归到底在替你保存什么 | 本章用列表表现队列和栈;递归版是谁在保存调用现场?层序遍历如何对应BFS? |
✅ 检查点
- “无信息”是不知道动作和代价,还是没有用到剩余代价的估计?
- 本页BFS、DFS、UCS怎样选出下一个候选?深度受限和IDS也只需改这一行吗?
- 地图中BFS、UCS分别多少公里、多少路段?为什么BFS的答案不是最短公里数?
- BFS为什么可能非常占内存?理想b=10、深度12的一层,以每节点100字节估算需要多少?目标在生成还是取出时检查为何影响数量级?
- 理想DFS的O(bm)空间来自哪里?带全局explored并复制完整路径的本页实现,是否能直接享有这个空间结论?
- Iasi/Neamt怎样使不查重的DFS不断循环?当前路径防环与全局去重有什么区别?深度受限为什么不能随意永久关闭同一状态?
- 规则树b=10、d=5,单轮深度受限与IDS分别访问多少节点?多多少次、约百分之几?
- b=2、d=5时上述数字是多少?这说明“IDS固定只慢11%”哪里不对?
- UCS为什么展开g=374的Dobreta?它的最优性对边代价有什么要求,目标何时检查?
- 理想对称双向搜索能减少多少深度?使用前要检查哪三件事?为何500倍节点规模比不是实测提速?
- 哪些深度优先家族实现可以使用随深度线性增长的搜索空间?本章有没有“无条件最优”或“永不内存不足”的算法?
对照答案:先判断条件,不必背运行计数
- 没使用“从当前状态到目标还要多少代价”的估计。动作、后继、边代价和目标测试仍是搜索问题的一部分。
- BFS取最早入队;DFS取最后入队;UCS取g最小,本文同g用FIFO。深度受限还要截止判断,IDS还要逐轮重启。
- BFS是450公里、3段;UCS是418公里、4段。BFS优先最少步数;不同边的公里数不同,所以步数少不保证总公里数少。
- frontier的一层就可能随深度指数增长。题设这一层为$10^{12}$个节点,按100字节算约100 TB。取出时才检测目标,可能先生成目标深度的下一层;故不能无说明混用$O(b^d)$和$O(b^{d+1})$。
- 理想实现只存当前路径及各层未探索分支,固定b后随深度线性。本页还保存全局状态集合和完整路径副本,不能直接套用该空间界。DFS也不一般保证最小代价。
- 不查重复时可不断生成Iasi→Neamt→Iasi。路径防环只排除当前路径上的状态;全局去重影响整次搜索。深度受限中,后来更短地到达同一状态会有更多剩余深度,不能因为之前到过就一概删掉。
- 单轮111,111次,IDS123,456次,多12,345次,约11.1%。最后一层占单轮约90%且只访问一次。这是指定规则树的访问数,不是墙钟时间。
- 单轮63,IDS120,多57次,约90.5%。分支较小时,重复浅层的相对代价更高;具体运行还取决于找到目标的位置和实现。
- 374小于最优目标代价418,而UCS只用已花代价排序,没有用剩余路程下界。本文有限图上需非负边,并在按g取出目标时返回;无限空间还要额外终止条件。
- 理想中两边各深入约d/2层,主导节点规模约2b^{d/2}。检查前驱是否可生成、目标是否可枚举、内存和相遇检测是否可承担。500倍只比较题设主导节点项,没测实际操作和时间。
- 合适实现下DFS为O(bm)、深度受限为O(bk)、IDS为O(bd),不包含任意大小全局闭集或完整路径复制的额外成本。没有这里所说的无条件最优或永不内存不足;例如UCS仍有代价/终止前提。
本节回顾
走神救援:带走这四点就够了。
- BFS先找少步数;UCS在条件满足时找小代价;DFS先探索深分支。
- 路径防环、全局去重和深度截止不是同一件事。
- IDS用重复访问换搜索空间,11%只是一个例子的访问增量。
- 所有保证都带前提;下一章用剩余代价估计帮助少检查分支。
下一节 👉 07-启发式与A星.md