CSCI3230 L09 · Part 4/7 Depth-first search

课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2025T1 本讲：L09，第 4 部分 / 共 7 部分 · 原件 L09-Uninformed-Search-2025T1.pdf（本地课件） p.41–48 定位：LIFO沿一条分支走到底，回溯不等于解路径。 前后：上一份 Uniform-cost search · 下一份 Depth-limited search

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

深度优先

先把一条路试到底，为什么能省记忆（p.41–42）

p.41是分节页。BFS要同时记住一整层候选；DFS（深度优先搜索）换一种探索习惯：先沿当前分支往下走，走不通再回到岔路口试另一个。它像逐条检查迷宫通道，但这是帮助理解的类比，程序实际上仍在操作搜索节点，不一定真的移动机器人。

**栈（stack）**最后放进去的先取出，叫LIFO。递归也可以实现同样的行为：每次调用记住“这一层还有哪些兄弟没试”，子调用失败后回到上一层。这不是把所有搜索历史永久保存。

先用已经认识的小树练栈（补充，沿用p.28树）

沿用A的孩子B/C，B的孩子D/E，C的孩子F/G，目标G。约定左边孩子优先，栈的左端是下一次取出的顶端。一次生成一组后继时，要使B最终位于C前面；若程序按右端作栈顶，就应先压C后压B。约定不同没关系，实际取出顺序必须对应。

访问次序是A,B,D,E,C,F,G，解仍然是A→C→G。回溯表示放弃失败子树、继续尝试；不表示最终动作列表必须包含先前所有尝试。父指针只记录当前路线。

再读课件较复杂的图（p.43）

图（p.43）：左边为有向状态图，右边为展开的搜索树；起点S、目标G。 元素：图中S有后继d/e/p；d有b/c/e，b与c均可到a；e可到h/r；h可到p/q，p可到q；r到f，f可到c/G。红线标出本次DFS探索的树边。 看什么：相同状态a、e、p、q可在不同路径中重复出现在搜索树，红色探索过的节点也未必在答案里。

按课件左到右顺序，先S→d→b→a，a是死端；退回d再试c→a，仍失败；再试e的h分支，最后进入r→f。f先试c→a，失败后才到G。最终父链为S→d→e→r→f→G。这里右侧画的是允许不同路径重复状态的搜索树演示；若实现全局去重，实际展开名单可能更短，不应强行逐节点照抄红色树。

为了看清大图的每次待办变化，以下直接按课件树搜索演示记状态标签（相同字母可对应不同路径节点）：

例如两个相邻e分别来自S→d→e和S→e，不能因为标签一样就把父链混在一起。

防环究竟保证什么（p.44）

p.44有A→B→D→A的环。若每次回到A都像第一次一样继续下探，永远不会回头试另一支。最简单的路径防环，是拒绝进入当前祖先链中已有的状态；全局visited则更强，连其他分支已处理的状态也跳过。

但“不绕圈”不等于一般空间里一定找到目标：补充设左边是永远向前的0→1→2→3→…，右边一步就是目标。左边没有重复状态，DFS仍可能一直深入。因此完备性要说条件：有限可达图且适当避免重复，可穷尽状态；无限深树上一般不完备。

找到的第一条路为什么未必最好（p.45）

课件DFS返回S→d→e→r→f→G，5条边；同图S→e→r→f→G只有4条边。若每条边成本1，前者5、后者4。DFS只是先试左分支，没有机制保证“第一条成功路径最短”。改变后继顺序甚至会改变答案，不能用一次运行很快找到好路线当作最优性证明。

补充 · 显式栈里不只有状态，还可能需要执行进度（通识讲解；演示数据不属于原题）。

递归DFS进入一个节点后，会记住“下一个还没尝试的后继是哪一个”；子调用返回时从那里继续。这份进度由调用栈隐式保存。若改写成迭代版但只保存一个状态，必须另行决定一次推入全部后继，还是保存后继迭代位置；两者都能实现DFS，但压栈顺序和内存账不同。

演示后继按A、B、C顺序访问：若一次全部入栈，为了让A先弹出，应按C、B、A压入。写成A、B、C压入却声称访问A在先，就是把容器里的排列与下一次取出顺序混淆。回溯时删除当前路径标记，也不等于删除一个用于全局图去重的visited集合；要先说集合承担哪种职责。

补充：防环集合退出递归时究竟删不删

自编有向图S先走A再走B，A→X，B→X，X无后继。使用“当前路径集合”时，走S→A→X暂存S、A、X；X返回后删X，A返回后删A；再走S→B→X时，X已不在当前祖先链，所以可以重新访问。这种集合防的是同一路线绕回祖先，不是整个搜索过程的重复。

若改用“全局已处理集合”，第一次处理X后便保留X，B再指向X就跳过，省掉重复探索。对普通有限可达性问题且状态表示充分，这可以保留找可行解的能力；但这个集合占据的空间随访问状态数量增长，不能继续只按当前递归深度计。

一份集合同时被口头称作path与visited，往往掩盖了矛盾：如果回退删除，它不是全局去重；如果不删除，它不只保存当前路径。先写出集合的数学含义，再决定何时插入和删除，比记住某行代码有用。深度限制、路径相关约束等变体还需要额外状态信息，不能照搬这个普通可达性结论。

时间看最深处，空间看同时压住多少（p.46–47）

$b$ 是最大分支数，$m$ 是搜索树最大深度。最坏要试完整树，所以时间 $O(b^m)$；它用的是 $m$，不是最浅目标深度 $d$，因为DFS可能先去比目标深得多的地方。

每深入一层，至多记住当前节点和若干尚未尝试的兄弟。深度 $m$，每层约 $b$ 条记录，路径式空间是 $O(bm)$。补充二叉树深10，完整叶层可有1024个节点，而沿一条路径主要只需约10层祖先/待办兄弟；数量级差异来自“同时保留”，不是DFS从不访问其他节点。

如果另保存全局visited，它还要随可达状态数增长；不能一边保存所有访问过的状态，一边说程序总空间必定只有 $O(bm)$。上述线性深度空间适用于路径式DFS记账。

p.47的原内存小例在当前路径ABD时保存A、B、D以及尚未尝试的E、C；F/G尚未由C生成，不必提前存在frontier。B分支全部探索完后可释放D/E及其路径记录，然后再探索C。这解释了“展开过就立刻删掉”并不准确：要等不再需要其祖先关系和剩余后继时才能释放。

课堂题按约定找第一个目标（p.48）

p.48 If node G is a goal node, what is the solution if use depth-first search?

原选项A.ABDG、B.ABDHG、C.ABEG、D.ACG。图中D的左孩子就是G，右孩子H再接一个G。按左到右DFS，不需要走到整棵树“最深的G”才停。

递归成功/失败的区别见附录 A1。

本讲核心考点

• 栈顶约定与后继压入顺序共同决定访问次序（p.42–43，C级）。
• 防环解决重复循环，不能消除无限无环深支（p.44，C级）。
• 解路径来自成功父链；时间深度与空间记账要分清（p.45–47，C级）。

附录

A1 回溯时到底撤掉什么

补充检查：递归试过A→B→D但D失败，准备试E时，动作列表中还该保留“B→D”吗？保留“已知D失败”这条知识和保留动作是一回事吗？

本节解释搜索机制，不给历史HW04的可提交代码，也未运行其自动评分器。

历史HW04为什么同时要递归与迭代（非讲义内容）

题面节选（HW04-2025T1-题目.pdf · Q1 · p.3–4）：

p.3 In this assignment, you need to provide two depth first search algorithm (recursive and iterative).

2025旧作业Q1占64%，要求graph search避免重复扩展，并使用所给数据结构、返回合法动作序列。递归版把“回来后继续谁”留在调用栈；迭代版显式放在Stack。两者若后继顺序不同，第一次找到的路径可以不同，不能仅凭路径不相同就断言其中一个错误。

p.4给mediumMaze的两种历史提示长度130和246，差异来自后继压栈顺序；这些是题面提示，不是本轮跑出的结果，也不是当前课程隐藏测试答案。学习时先用正文七节点树核对每次压入/弹出，再看路径是否合法。地图上的探索颜色表示搜索调查过哪些状态，执行动画只走成功动作列表，二者不应强行一致。

题面只给DFS与BFS两道计分题，尽管背景提及UCS/A*，不能据背景自行添加两题或编造分数。这里不生成可提交实现，不宣称通过tinyMaze/mediumMaze/bigMaze或自动评分。

回到正文

来源与证据

• 原件：L09-Uninformed-Search-2025T1.pdf（本地课件），具体页码标在各节。原课件保留本地。
• 例子标为“补充”时是为帮助理解而选取，不是教师题目或2026T1要求。
• 考试证据（沿用既有笔记的历史核对记录）：核对 HW04-2025T1-题目.pdf Q1–Q2（p.3–4）；只作为2025旧作业证据（A级），未运行作业程序。 补充练习与自检均为通识（C级）。