🏠 总目录📚 本教程 06 · 无信息搜索 ← →

同一张地图,换出队规则会改变哪些保证?

读后可检查:比较 BFS、DFS 与 UCS 的扩展顺序,先核对代价与分支条件再用复杂度表。

📑 本页目录(点开跳转)

06 · 无信息搜索

⏱ 44 分钟 | 阅读参考 · 先分清:少走几步,和少走几公里,不是一件事。

可以分多次读。第一次先看三条路线的结果;复杂度和独立代码放在后面,需要时再展开。


🎯 一句话

无信息搜索知道能走哪些路、每条路多贵,也能检查是否到达目标;它没有使用“离目标还剩多远”的估计。

同一张地图上,BFS 先找步数少的路线,DFS 先把一条分支往深处探,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倍”。 检查相遇、存储、两边不对称等开销还没计入。

使用前检查三件事

  1. 能否枚举前驱? 只有正向模拟器、无法找哪些状态通向当前状态时,反向搜索可能很难。
  2. 能否枚举目标? 少量已知目标可以作为反向搜索的多个起点;像大量“将死”局面那样难以列出的目标集合,会让反向起步困难。
  3. 能否承担保存 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?

✅ 检查点

  1. “无信息”是不知道动作和代价,还是没有用到剩余代价的估计?
  2. 本页BFS、DFS、UCS怎样选出下一个候选?深度受限和IDS也只需改这一行吗?
  3. 地图中BFS、UCS分别多少公里、多少路段?为什么BFS的答案不是最短公里数?
  4. BFS为什么可能非常占内存?理想b=10、深度12的一层,以每节点100字节估算需要多少?目标在生成还是取出时检查为何影响数量级?
  5. 理想DFS的O(bm)空间来自哪里?带全局explored并复制完整路径的本页实现,是否能直接享有这个空间结论?
  6. Iasi/Neamt怎样使不查重的DFS不断循环?当前路径防环与全局去重有什么区别?深度受限为什么不能随意永久关闭同一状态?
  7. 规则树b=10、d=5,单轮深度受限与IDS分别访问多少节点?多多少次、约百分之几?
  8. b=2、d=5时上述数字是多少?这说明“IDS固定只慢11%”哪里不对?
  9. UCS为什么展开g=374的Dobreta?它的最优性对边代价有什么要求,目标何时检查?
  10. 理想对称双向搜索能减少多少深度?使用前要检查哪三件事?为何500倍节点规模比不是实测提速?
  11. 哪些深度优先家族实现可以使用随深度线性增长的搜索空间?本章有没有“无条件最优”或“永不内存不足”的算法?
对照答案:先判断条件,不必背运行计数
  1. 没使用“从当前状态到目标还要多少代价”的估计。动作、后继、边代价和目标测试仍是搜索问题的一部分。
  2. BFS取最早入队;DFS取最后入队;UCS取g最小,本文同g用FIFO。深度受限还要截止判断,IDS还要逐轮重启。
  3. BFS是450公里、3段;UCS是418公里、4段。BFS优先最少步数;不同边的公里数不同,所以步数少不保证总公里数少。
  4. frontier的一层就可能随深度指数增长。题设这一层为$10^{12}$个节点,按100字节算约100 TB。取出时才检测目标,可能先生成目标深度的下一层;故不能无说明混用$O(b^d)$和$O(b^{d+1})$。
  5. 理想实现只存当前路径及各层未探索分支,固定b后随深度线性。本页还保存全局状态集合和完整路径副本,不能直接套用该空间界。DFS也不一般保证最小代价。
  6. 不查重复时可不断生成Iasi→Neamt→Iasi。路径防环只排除当前路径上的状态;全局去重影响整次搜索。深度受限中,后来更短地到达同一状态会有更多剩余深度,不能因为之前到过就一概删掉。
  7. 单轮111,111次,IDS123,456次,多12,345次,约11.1%。最后一层占单轮约90%且只访问一次。这是指定规则树的访问数,不是墙钟时间。
  8. 单轮63,IDS120,多57次,约90.5%。分支较小时,重复浅层的相对代价更高;具体运行还取决于找到目标的位置和实现。
  9. 374小于最优目标代价418,而UCS只用已花代价排序,没有用剩余路程下界。本文有限图上需非负边,并在按g取出目标时返回;无限空间还要额外终止条件。
  10. 理想中两边各深入约d/2层,主导节点规模约2b^{d/2}。检查前驱是否可生成、目标是否可枚举、内存和相遇检测是否可承担。500倍只比较题设主导节点项,没测实际操作和时间。
  11. 合适实现下DFS为O(bm)、深度受限为O(bk)、IDS为O(bd),不包含任意大小全局闭集或完整路径复制的额外成本。没有这里所说的无条件最优或永不内存不足;例如UCS仍有代价/终止前提。

本节回顾

走神救援:带走这四点就够了。

  • BFS先找少步数;UCS在条件满足时找小代价;DFS先探索深分支。
  • 路径防环、全局去重和深度截止不是同一件事。
  • IDS用重复访问换搜索空间,11%只是一个例子的访问增量。
  • 所有保证都带前提;下一章用剩余代价估计帮助少检查分支。

下一节 👉 07-启发式与A星.md

打卡记录保存在你的浏览器里,首页能看到总进度