CSCI3230 L09 · Part 6/7 Iterative deepening depth-first search

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2025T1 本讲：L09，第 6 部分 / 共 7 部分 · 原件 L09-Uninformed-Search-2025T1.pdf（本地课件） p.55–61 定位：重复较浅层，以较小内存找到最浅解。前后：上一份 Depth-limited search · 下一份 Summary

版本边界：本篇依据2025T1旧课件作预习与基础补课，不表示2026T1已经讲到这里；今年范围以今年教师公告为准。页码均为原PDF页号。

不知道该限几层，就从浅到深重来

用重新开始换取少用内存（p.55–56）

p.55为分节页。DLS需要深度上限，但我们通常不知道目标多深。IDDFS（迭代加深深度优先搜索）按0、1、2、3……逐轮做DLS，某轮找到就停止。每轮内部是深度优先，不是BFS；多轮合起来却保证浅解先于深解被发现。

为什么愿意重复？因为它不用同时保存整层，只保留当前DFS路径和兄弟；代价是浅层会重做。它适合分支有限、每步成本相同、希望最少步解又受内存限制的情形。若边权不等，最少步不等于最低价。

把三轮连起来看（p.57–59）

沿用课件A→B/C，B→D/E，C→F/G，目标G的图。p.58还在D下画出回到A的路径，说明原状态图可有环；深度限制使每轮不会永远往下。表中左端先取，数字为深度。

轮次	取出序列及每次处理后的完整frontier
限制0	初[A0]；取A0非目标且到边界→[]，截断
限制1	初[A0]；取A0→[B1,C1]；取B1截断→[C1]；取C1截断→[]
限制2	初[A0]；取A0→[B1,C1]；取B1→[D2,E2,C1]；取D2截断→[E2,C1]；取E2截断→[C1]；取C1→[F2,G2]；取F2截断→[G2]；取G2成功

每轮起点都是A，不是从上一轮最后一个节点继续。限制2那轮，D达到上限，所以不会生成更深的A；环被边界挡住。p.59有深度2、3、4的多个G，第二层已有G，于是在允许第三层前就停了。

p.57动画汇总实际包含Limit=0、1、2、3四轮，文字从1开始叙述只是省略了初态检验。每轮黑色表示该轮已经走过的节点，空心当前位置沿左子树先走再回溯，灰色表示更深处尚不允许进入的节点；深度上限改变后重新从根计算，而非保留上一轮黑色就跳过。

为什么重复起点不会造成错误（补充）

“已经访问过A”只能描述上一轮在旧限制下做过的事情。本轮多了一层额度，A下面可能有新内容可到达，所以不能跨轮保留一份永久visited把起点挡掉。路径防环和每轮的深度管理应重新开始；若使用更精细缓存，必须记录它在什么剩余额度下已被完整探索。

这与现实中“换更长的时间预算重新检查路线”相似，但数学上仍是多次从根运行，不是逐渐延长同一条DFS分支。后者会重新落入无限深支问题。

完备与最少步保证从哪里来（p.58–59）

假设每个节点后继数有限，存在一个有限深度 $d$ 的目标。任何固定限制 $\ell$ 的树都有限，所以一轮能结束；限制最终到达 $d$ ，该轮会检查最浅目标，所以完备。这里 $d$ 表示最少边数， $\ell$ 表示当前允许的最多边数。

前面所有小于 $d$ 的轮次都失败，成功那轮不允许大于 $d$ 的路径。因此第一条成功解恰好最浅。若每步成本为同一个正数 $c$ ，成本 $dc$ 也最小。若两步路每步10、三步路每步1，IDDFS仍先返回20，不会继续寻找3；它没有成本最优的普遍保证。

重做浅层到底花了多少（p.60）

设最浅目标深度 $d=2$ ，每节点最多 $b=2$ 个孩子，并按最坏情况访问完目标层。根会在限制0/1/2三轮各访问一次；第一层在限制1/2两轮访问；第二层只在最后一轮访问。因此

3\cdot1+2\cdot2+1\cdot4=11.

BFS只看每节点一次，对应1+2+4=7。IDDFS多了4次访问，却不用一直保留整层。

一般式是

N=(d+1)b^0+db^1+(d-1)b^2+\cdots+b^d.

为什么最底层系数1？因为只有限制够深的最后一轮才能到那里。为什么根系数 $d+1$ ？因为从0到 $d$ 总共有 $d+1$ 轮。把每一项的“层节点数×被访问轮数”想清楚，比背展开式可靠。

当固定 $b>1$ 时，最底层节点占大头，尽管浅层重复，增长阶仍为 $O(b^d)$ 。补充二叉树深3：4×1+3×2+2×4+1×8=26，单次完整树15；不是简单“每个节点重做4次”，因为8个最底层节点只做一次。

边界 $b=1$ 是一条链，没有指数增长的底层来摊薄重做：总工作 $1+2+\cdots+(d+1)$ ，是二次量级。把 $O(b^d)$ 不带条件套到链上会得出荒谬常数，所以需要知道公式背景。

补充 · 分支只有一条时，重复开销不能仍说是常数倍（通识讲解；演示数据不属于原题）。

常见“重做浅层代价不大”的直觉依赖分支数大于1，因为最深层节点占大头。若搜索空间是一条链，目标深度为 $d$ ，一次BFS或足够深的DFS访问约 $d+1$ 个节点；迭代加深每轮访问1、2、…、 $d+1$ 个，总数为 $(d+1)(d+2)/2$ ，随深度平方增长。

演示目标深度4：五轮分别访问1、2、3、4、5个节点，合计15，而一次沿链走到目标只需5个。它仍保留逐步加深、较小空间的思路，但这个边界说明复杂度结论必须带分支假设。不要把适合指数增长树的求和近似机械套到 $b=1$ 上。

补充：分支为二时，额外开销可以算到一个比值

对满二叉树最深目标位于深度 $d$ 的最坏计数，BFS访问 $2^{d+1}-1$ 个节点；迭代加深的加权和为 $\sum_{k=0}^{d}(d-k+1)2^k$ 。将每个节点按出现轮次重新计数，也就是把每轮完整树相加：

N=\sum_{\ell=0}^{d}(2^{\ell+1}-1) =2(2^{d+1}-1)-(d+1) =2^{d+2}-d-3.

取 $d=4$ ，各轮节点数为1、3、7、15、31，总57；BFS为31，比值 $57/31\approx1.8387$ 。随着深度变大，这个满二叉树计数的比值趋近2，而不是随轮数无限增长，因为最大的底层只访问一次。

这是特定满树最坏计数的精确关系，不是任何图、任何目标顺序都恰好多一倍。若目标很早遇到、分支不均匀或采用图去重，实际计数会变；单链的二次重复成本也不能套这里的二叉树公式。把一般增长阶与具体数字分开，才能解释什么时候重复工作值得用来换内存。

空间为什么跟最终深度线性相关（p.61）

每轮都用DFS，只保存一条最长至限制层的路径及待试兄弟，最后一轮限制 $d$ ，因此路径式空间 $O(bd)$ 。前几轮结束就释放其搜索记录，不是把各轮整棵树全部存下来。

若为了“优化重做”把所有历史路径都缓存，当然可能失去这个内存优势。理论复杂度总和实现保留哪些数据有关。

本讲核心考点

每轮从根重来、限制递增；跨轮不能用永久visited挡住新深度（p.56–59及补充，C级）。
最浅目标先被找到；等步成本才导出成本最优（p.59，C级）。
重做次数按层加权，固定分支数大于1时仍为指数同阶（p.60–61，C级）。

附录

补充检查：有人把限制0、1、2三轮的完整frontier都留下供查看，然后称“总内存仍为DFS的线性空间”。这句话缺少什么条件？

参考答案

空间结论要求旧轮次不再占用搜索存储，并且每轮使用路径式DFS。若保存全部展开记录用于可视化或调试，额外日志也算内存，不能继续无条件称线性深度空间。算法理论分析与教学记录表不是同一个存储约定。

来源与证据

原件：L09-Uninformed-Search-2025T1.pdf（本地课件），具体页码标在各节。原课件保留本地。
例子标为“补充”时是为帮助理解而选取，不是教师题目或2026T1要求。
考试证据：本轮只核对上述讲义，没有据此预测今年考题；练习与自检均为通识（C级）。