CSCI3230 L09 · Part 5/7 Depth-limited search
课程：CSCI3230 (ESTR3108) Fundamentals of Artificial Intelligence · 2025T1 本讲：L09，第 5 部分 / 共 7 部分 · 原件 L09-Uninformed-Search-2025T1.pdf（本地课件） p.49–54 定位：给DFS一条深度边界，区分截断与真失败。 前后：上一份 Depth-first search · 下一份 Iterative deepening depth-first search
版本边界：本篇依据2025T1旧课件作预习与基础补课，不表示2026T1已经讲到这里；今年范围以今年教师公告为准。页码均为原PDF页号。
给深度优先加一条停止线
防止一条路永远走不完（p.49–50）
p.49为分节页。DFS的风险是左边太深，右边目标永远轮不到。DLS（深度限制搜索）给DFS加一个整数上限 ：只允许考虑深度不超过它的节点。根深度0，所以限制2允许走两条边，而不是只看两层含根节点。
到限制层仍要先检查是否目标；只有“不是目标且已到上限”才停止向下生成后继。不先检查的话，恰在边界的目标会被错过。
这条停止线的含义是“今天先只看这么深”，不是“世界只有这么深”。p.50以罗马尼亚20座城市说明：若有路线，总能删去绕圈部分，得到最多19条边的简单路径。因此19可以作为找可行路线的足够限制。它不是说原图每条路线最多19步，更不自动保证找到成本最低路线。
p.51的小树逐步走（p.51）
图（p.51）：根S，第一层A/B；A下为C/D，B下为I/J，J是目标；C/D/I下面还有第三层节点。 看什么：虚线表示回退/转向，第三层真实存在，但限制2时不进入。
下表约定左孩子优先，frontier左端先取，括号里记深度。边界节点仍入表并作目标检验，只是不展开它们。
| 取出 | 为什么停或继续 | 之后frontier |
|---|---|---|
| — | 起点 | [S(0)] |
| S(0) | 未到2，生成A/B | [A(1),B(1)] |
| A(1) | 未到2，生成C/D | [C(2),D(2),B(1)] |
| C(2) | 非目标，达到限制，截断 | [D(2),B(1)] |
| D(2) | 非目标，达到限制，截断 | [B(1)] |
| B(1) | 还有一层额度，生成I/J | [I(2),J(2)] |
| I(2) | 非目标，截断 | [J(2)] |
| J(2) | 先检验出目标，成功 | [] |
解是S→B→J。看到第三层H等节点没有被访问，不是漏算，而是限制规则在起作用。
p.51被截断的第三层也完整保留其结构：C的孩子为E/F，D的孩子为G，I的孩子为H，J为目标。限制2时这些E/F/G/H都不生成；若以后把限制改3，则它们才进入允许访问范围。注意这个图的G不是本题目标，本题明确目标为J，不能沿用其他课堂图的“G必是goal”。
截断、失败、成功是三种不同返回（补充）
递归DLS常需要三种结果。“成功”带回解路径；“截断”说明因为深度额度用完，尚不能判断下方有没有解；“失败”说明已允许检查的分支真的全部结束且无解，不只是被限制挡住。
例如限制0，起点不是目标但还有孩子，返回截断；如果起点不是目标且根本没有孩子，则可以判断失败。实现有时保守地把边界统一记截断，这也可作为继续加深的信号，但可能多做轮次。应看接口怎样定义，不能把一个布尔false同时当作两个数学结论。
调小限制会漏什么，调大限制会改变什么（p.52–53）
表示最浅目标深度。如果 ，目标在门外，本轮不可能找到，所以固定限制的DLS一般不完备。上例限制1，只检查S/A/B，J在深度2被挡住。
若限制大于最浅目标深度，又不保证最优。p.53用A→B→D→G（三步）和A→C→G（两步）说明：限制3允许DFS先沿左边找到三步G，就不会回来比较右边两步G。限制2反而先截断D下面的G，后来发现A→C→G。扩大搜索范围并不保证第一次返回的路线更好，因为内部还是DFS顺序。
即便限制恰为 ，只能保证返回某条最浅路线；成本不等时，同层路线也可以有不同费用。要最低成本仍需适当的成本搜索。
补充 · 深度恰好到上限时，先检查是否已经成功（通识讲解；演示数据不属于原题）。
若根节点深度为0，限制为2，深度2的节点仍在允许范围内。应先检查它是不是目标；只有它不是目标、又不能继续深入时，才按具体约定返回截断或确认无后继的失败。把“深度达到限制”写在目标检查之前并立即截断，会漏掉刚好在边界上的解。
用链 S→A→G 演示：根深度0，A为1，G为2。限制1时不能看见G；限制2时应在G处成功，而不是要求限制3。根从0还是从1计数是实现约定，但整张追踪表必须统一。自检时特意放一个边界目标，比只测试浅层目标更容易发现少走或多走一层的错误。
重复状态还要考虑剩余额度（补充）
不能把“同一状态曾来过”机械等同“此状态永远不用再看”。若第一次到X已经用了3步、限制3，没有额度展开；后来2步到X，还剩1步，可能正好能到目标。全局visited若把X永久锁死，就误删了有用路线。
路径防环只排除当前祖先链，易于保持DLS的深度语义。若要跨分支去重，必须连到达深度/剩余额度一起比较：更浅到达同一状态可能值得重新处理。这是实现补充，不是要求背复杂数据结构。
补充：把剩余额度错误真的追踪到漏解
自编图S的后继按A、X顺序；A→B，B→X，X→G，目标G。限制为3，根深度0。深度优先先走S→A→B→X，此时X深度3，非目标且额度0，不能展开到G。若将X放入永久visited，回退后由S直接到X时就会跳过它。
但第二条路线S→X只用了1步，尚有2步额度，完全可以再走一步到G，得到深度2的解。两次到X不是相同的剩余搜索任务。这里确实有解落在限制以内，永久去重却漏掉，不是限制本身太小。
可选择只用当前路径防环，让第二次X重新搜索；也可对无路径相关限制的标准图任务记录每个状态已充分搜索过的最大剩余额度，只有旧额度至少与新额度一样大时才考虑复用失败结论。若缓存的是尚未完成的搜索，或动作约束依赖当前祖先路径，还不能仅凭额度贸然复用。这些限定解释了为什么最简单可靠的教学DLS常从路径防环开始。
成本随限制怎样增长（p.54）
分支数 、深度限制 都是整数。满树最多 个节点， 时为 时间；当前路径和待试兄弟约 空间。
补充二叉树：限制2时至多1+2+4=7个，限制3变15个，限制4变31个。深度只加1，工作可能约翻倍。可见限制不是随便设得越大越好；不知道该选多少时，下一份迭代加深给出系统方法。
本讲核心考点
- 深度按边计，边界节点先验目标再截断（p.50–51，C级）。
- 截断只说没继续看，不能说下方无解（p.52及补充，C级）。
- 限制太小漏解，限制较大仍是DFS的首次成功路径（p.52–54，C级）。
附录
补充检查：p.51图若把目标改为第三层某节点，限制2返回“未找到”，能否宣布问题无解？
参考答案
不能。第三层从未被检查，结果只证明深度2以内未找到目标。应记为受限制截断，再决定是否提高限制。若目标恰在深度2而程序仍漏掉，应先查“深度等于上限”的判断是否写在目标检验之前。
来源与证据
- 原件：L09-Uninformed-Search-2025T1.pdf（本地课件），具体页码标在各节。原课件保留本地。
- 例子标为“补充”时是为帮助理解而选取，不是教师题目或2026T1要求。
- 考试证据：本轮只核对上述讲义，没有据此预测今年考题；练习与自检均为通识（C级）。