L02 Search Techniques：在陌生大楼里找出口，从瞎推门到看着指南针走

一句话版

把问题写成”从起点找到终点”，然后比五种找法在完备性、最优性、时间、空间上的取值。

一个类比：在一栋陌生的大楼里找出口

你被放进一栋没见过的大楼，要找到出口。手上什么都没有，只能一扇一扇推门。

广度优先是把这一层所有的门都推开看一眼，再上下一层。只要出口存在就一定找得到，而且找到的是”经过门最少”的那条路；代价是你得记住这一整层打开过的每一扇门，层数一深，脑子就装不下（p.24–26）。

深度优先是随便挑一条走廊一路走到黑，撞墙了再退回最近的岔口换一条。只需要记住身后这条路和沿途没试过的岔口，省脑子；代价是可能一头扎进一条很深但根本没有出口的走廊，出不来（p.36–38）。这两种走法的代码差别只有一处：待处理的门是排队取（BFS）还是叠着取（DFS）（p.18、p.31）。

后面三种走法多了一样东西——离出口还有多远的估计。爬山法是只看眼前哪扇门透进来的光更亮就往那边走，从不记路，走错了退不回来（p.47）。最佳优先把见过的门全记下来，每次从全部候选里挑”看起来离出口最近”的那扇，所以它能跳回早先放弃的分支（p.52）。A* 再补一刀：挑门的时候把”已经走了多远”也算进去，用 f = g + h 排序（p.55）。

类比在哪里失效：大楼里你迈出的每一步都能原路走回去，爬山法却是不可逆的一条线，走进局部最高点就卡死（p.50）。楼里的”光更亮”是现成的信号，真实搜索问题里好的启发函数得自己设计，课件原话是 Designing good heuristics is empirical and difficult（p.54）。大楼层数有限，搜索树可以无限深，DFS 在无限深的空间里加了 Close 表也救不回来（p.36）。最后一条最要紧——大楼里你要的是”站到出口那个位置”，搜索问题要的是那条路怎么走，终点通常一开始就知道（p.4）。

概念卡

1. 搜索问题的五要素与”解”（Search Problem）

人话定义：当前状态、目标状态、动作、代价，四样定完就能搜；搜出来的解是一条路径。

例子：八数码（p.9）。起始盘面和目标盘面都给定，动作是 Up / Down / Left / Right，注意动的是空格不是数字块，所以每个状态最多 4 个后继。空格在角上 2 个动作，在边上 3 个，在中心 4 个——这个数在 p.23 直接决定分支数。

常见误解

把”解”答成目标状态 → 目标状态通常一开始就给定了（八数码的目标盘面写在题面上），要找的是怎么走过去。p.4 那一行是最容易丢分的地方。

2. Open 表、Close 表与两个算法的唯一差别

人话定义：Open 存已生成还没展开的节点，Close 存已经展开过的。循环只有三步：从 Open 取一个 → 是目标就结束，否则展开它、孩子入 Open → 把它移进 Close。

例子：Open 用队列（FIFO）就是 BFS，用栈（LIFO）就是 DFS（p.18、p.22、p.31）。

p.32–33 那棵 21 个节点的树按栈展开，访问顺序是 A B E K S L T F M C G N H O P U D I Q J R——检查自己算得对不对最快的办法是看 Close 表顺序，它就是答案。

常见误解

以为 Close 表是用来记账的 → 它的作用是防止重复访问。已经在 Close 里的状态不再展开，否则遇到环就死循环（p.18、p.36）。

3. 四个评价维度与复杂度公式

人话定义：完备性（有解就一定找得到吗）、最优性（找到的是不是最好的）、时间（要展开多少节点）、空间（同时要存多少节点）（p.7）。

例子：本课件的符号是 d = 搜索树深度、b = 分支因子、m = 最浅解的深度（p.15）。两个算法的空间差别画出来就是「一整层」对「一条路」：

四个维度并排看（p.25、p.26、p.37、p.38）：

	BFS	DFS
完备性	有解一定找得到	无限深或有环时会陷进去
最优性	一定是边数最少的路径	不保证
时间	O(b^(m+1))，只到解那一层	最坏 O(b^d)，得扫完整棵树
空间	O(b^(m+1))，这才是它的死穴	O(d·b)，路径长 d、每层最多 b 个兄弟

常见误解

答”BFS 慢、DFS 省内存”就完事 → 要点名维度。BFS 的死穴是空间不是时间：b=10、m=10 时是 10¹¹ 个节点，任何机器都装不下（p.26）。DFS 的时间通常更差，因为它可能一头扎进没有解的深分支（p.37）。

4. 爬山法的三种失败（Hill Climbing）

人话定义：一个又急躁又瞎的登山者——每步只看脚下周围哪个方向更高，只保留最好的那个孩子，不保存历史。三种地形能困住他：

例子：井字棋的启发函数是 most wins，即这一格能参与多少条获胜连线。整盘 8 条连线（3 横 + 3 竖 + 2 对角），角 3 条、中心 4 条、边 2 条，所以第一步下中心（p.48）。这个函数的价值在于粗糙但便宜——太贵的启发函数还不如直接搜。

常见误解

把高原和山脊混成一个 → 高原是一片区域得分全一样、启发函数给不出方向；山脊是狭窄的上升方向与允许的单步方向不一致，局部单步选择难以前进。加上局部最大共三种，根因都是只看局部、不留历史（p.50）。

5. f = g + h 与 A* 的那个条件

人话定义：g(n) 是从起点走到 n 已经付出的实际代价，h(n) 是从 n 到目标的估计，f(n) = g(n) + h(n) 是这条路总代价的估计（p.55）。

例子：定义理想评价函数 f*(n) = g(n) + h*(n)，其中 h*(n) 是从 n 到目标的真实最小代价（p.58）。h* 算不出来，但常常能找到一个 h 满足 h(n) ≤ h*(n)，即永远不高估。用 f = g + h 排序的最佳优先，如果它的 h 满足这个条件，就叫 A*；课件用方框圈出的定理是 All A* algorithms are admissible（p.60）。

常见误解

问”A* 和最佳优先有什么区别”只答一条 → 要两条都答：①A* 用 f = g + h 排序而不是只用 h ②A* 要求 h(n) ≤ h*(n)。另外 admissible 在 p.58 形容的是算法保证找到最优解，和形容 h 的”不高估”是两层意思，别混（p.58、p.60）。

把它们串起来

整讲只有一条主线：从盲目走到有信息（p.2–3）。

起点是把问题翻译成状态图，解是路径不是状态（p.4）。有了这个框架，第一批算法只有一个能力——判断当前状态是不是目标，别的什么都不知道（p.14）。在这个能力下能做的只有按固定顺序扫一遍，于是 BFS 和 DFS 成了同一段代码的两个版本，差别只在 Open 表用队列还是用栈（p.18）。它们各自的完备性、最优性、时间、空间，全部是从这一处推出来的（p.39）。

转折发生在 p.42：启发式搜索用”离目标还有多远”的估计指导方向，课件那句黑体是 success is NOT guaranteed——这是一笔明码标价的交易，拿完备性和最优性换速度。爬山法把这笔交易做到极端（只留一个孩子、不记历史），最佳优先把 Open 表加回来收回一半，A* 再加上 g 和”不高估”这个条件，把最优性换了回来（p.47、p.52、p.60）。

课件里的坑

• [口径差异] 课件 p.15 定义 d 是搜索树深度、m 是最浅解的深度 → 很多教材（包括 AIMA）这两个字母正好相反，考试按本课件这套记（p.15）
• [页码提醒] p.32–33 是同一页动画的两帧，页脚都印着「31」；那棵树里有个节点就叫 S，但起点是 A，别被字母混淆（p.32–33）
• [题设区别] p.53 的八数码目标盘面空格在中心，和 p.9 那个空格在右下角的目标盘面不一样 → 最佳优先这一节从头到尾用的是 p.53 那个（p.53）
• [读图提醒] p.67 页面上标的「= 8」是节点 L 的 f 值，不是这道题的答案；答案是 I 的 7（p.67）

课后 10 分钟：考点复习

这 10 分钟怎么用：合上页面，先默写三条——搜索五要素里「解是一条路径」、Open 换容器就换算法、f(n) = g(n) + h(n) 与 h 不高估；再把下面的「变式题」做一遍；最后回查两个最容易错的地方——把「解」答成目标状态、答 BFS 慢却说不出它的死穴在空间。三步做完再往下看答案。

必背

1. 搜索问题五要素：当前状态 / 目标状态 / 动作 / 代价 / 解；解是一条路径，不是一个状态。
2. 评价一个搜索算法只看四条：完备性、最优性、时间、空间。
3. 本课件符号：d = 搜索树深度，b = 分支因子，m = 最浅解的深度，且 d 可以远大于 m。
4. Open 是待展开、Close 是已展开；Open 用队列（FIFO）就是 BFS，用栈（LIFO）就是 DFS，两个算法只差这一处。
5. 有限分支、有有限深解时 BFS 完备且找到边数最少的路径，时间与空间同为 O(b^(m+1))；不保存全局 Close 表的树式 DFS 空间为 O(d·b)，但不完备、不最优，最坏时间 O(b^d)。
6. 爬山法只看一步、只留最好的一个孩子、不记历史，三种典型失败地形是局部最大、高原、山脊。
7. f(n) = g(n) + h(n)：g 是从起点已付出的实际代价，h 是到目标的估计。
8. h(n) ≤ h*(n) 不高估是 A* 的定义条件，按课件定理的前提 A* 能保证最优；图搜索还需一致启发式或允许重新打开节点；手算时碰到目标不能立刻停，要等它被选出来展开。

完整例题

课件 p.61–67 那道最短路径题是我押的考卷题型（我的判断，课件没标重点），完整走一遍。

题面：起点 S、终点 T，中间顶点 V1–V5，十一条带权有向边，求 S 到 T 权重之和最小的那条路径。

约定：搜索树上的节点按走过的那条边命名（走了边 a 就得到节点 A），不是按图上的顶点命名。h 取”当前所在顶点的所有出边里最小的那个权重”，到了 T 就是 0——真实剩余路径至少要走一条出边，所以它不高估，满足 A* 的条件（p.61、p.62）。

1. 展开 S。A：走 a 到 V1，g=2，h=min(d=2, e=3)=2，f=4；C：走 c 到 V2，g=3，h=min(k=2, f=2)=2，f=5；B：走 b 到 V3，g=4，h=2，f=6。取 f 最小的 A。
2. 展开 A（在 V1）。D：a,d 到 V4，g=2+2=4，h=min(h=1, i=3)=1，f=5；E：a,e 到 V2，g=2+3=5，h=2，f=7。Open 现在是 D(5)、C(5)、B(6)、E(7)。
3. 展开 C（在 V2）。F：c,k 到 V4，g=3+2=5，h=1，f=6；G：c,f 到 V5，g=3+2=5，h=5，f=10。G 一下子跳到 10，因为 V5 到 T 那条边权重是 5。
4. 展开 D（在 V4，g=4）。H：a,d,h 到 V5，g=4+1=5，h=5，f=10；I：a,d,i 到 T，g=4+3=7，h=0，f=7。I 已经到达目标，但课件在这里写的是 A path but not sure whether it is the shortest path——不能停。
5. 展开 B（在 V3，g=4）。J：b,g 到 V5，g=4+2=6，h=5，f=11。这条分支到此为止。
6. 展开 F（在 V4，g=5）。K：c,k,h 到 V5，g=5+1=6，h=5，f=11；L：c,k,i 到 T，g=5+3=8，h=0，f=8。L 也到了目标，但 8 比 I 的 7 贵。
7. 此时 E 与 I 都是 f=7；沿用课件同分时优先取 I 的约定，选择 I（f=7），把它选出来展开，它就是目标，搜索结束。
8. 答案：最短路径 S→V1→V4→T（边 a, d, i），总代价 2+2+3 = 7。 展开顺序是 A → C → D → B → F → I；始终没轮到的是 E(7)、G(10)、H(10)、J(11)、K(11)、L(8)。

整棵搜索树长这样，对着它复盘一遍比重算一遍快：

手算五步口诀：列边权并检查 h 的条件 → 生成节点时算 g、h、f → 每轮取 Open 中 f 最小的节点 → 生成目标时不立即停；取出最小 f 的目标时才停 → 按父节点回溯路径。本例是可采纳启发式的树搜索；图搜索还需一致性或允许重开节点。

变式题（先自己做）

同一张图、同一个起点终点，只改一个条件：把所有 h 全部取 0。

(1) 这时 A* 退化成按什么排序的搜索？它还满足 admissible 吗？ (2) 最终找到的路径和总代价会不会变？ (3) 展开的节点数会变多还是变少？说出机制。

提示

先把 f = g + h 里的 h 换成 0 看 f 变成什么。再回到 admissible 的定义式 h(n) ≤ h*(n)，代 0 进去检查它成不成立——这一步决定了第 (2) 问的答案。

参考答案与自检（非官方评分标准）

自检要点：① 必须点明 h ≡ 0 仍然满足不高估，所以最优性不丢；② 必须把「路径不变」和「展开数变多」分开答，混成一句「效率变差所以结果变差」是这题的主要失分方式。

(1) f = g + 0 = g，变成只按已付出代价排序的最佳优先。admissible 的条件是 h(n) ≤ h*(n)，真实剩余代价永远非负，所以 0 恒满足，仍然 admissible（p.58、p.60）。

(2) 不变，仍是 S→V1→V4→T，总代价 7。admissible 保证的就是最优解本身，h 只影响到达它的效率。

(3) 在本例中变多。h 的作用是把「还剩多远」提前计入排序，让通往目标的分支更早浮上来。h ≡ 0 等于丢掉这个信息，那些 g 小但离目标远的节点会被先展开——原题里一直没轮到的 E(7)、G(10)、H(10) 这类节点，会有一部分被提前展开。

闪卡自测

1. 搜索问题的"解"是什么？为什么说不是目标状态？

解是一条路径。目标状态通常一开始就知道（八数码的目标盘面是给定的），要找的是怎么走过去（p.4）。

2. Open 表和 Close 表各存什么？把 BFS 改成 DFS 只需要改哪一处？

Open 存已生成还没展开的节点，Close 存已经展开过的节点。只需把 Open 的数据结构从队列换成栈，其余代码几乎一模一样（p.18、p.22、p.31）。

3. 本课件里 d、b、m 各代表什么？为什么 BFS 的时间是 O(b^(m+1)) 而 DFS 是 O(b^d)？

d 是搜索树深度，b 是分支因子，m 是最浅解的深度。BFS 不会去碰比解更深的层，所以指数上是 m；DFS 最坏情况下唯一的目标在最右边那条分支上，得把整棵树扫完，所以是 d。课件特别加了一句：d 可以远大于 m（p.15、p.25、p.37）。

4. DFS 在什么情况下不完备？加了 Close 表之后能完备到什么程度？

在无限深的空间里、或者有环的空间里会失败。沿路径检查重复状态（Close 表）之后，只能保证在有限空间里完备，无限深的树照样陷进去（p.36）。

5. 八数码里空格在角 / 边 / 中心时各有几个后继？为什么 p.23 那个节点只展开出一个孩子？

角 2、边 3、心 4。p.23 那个节点空格在左下角，只有上、右两个动作，其中”右”正好把空格移回原位、该状态已在 Close 表里，2 减 1 就只剩 1 个新孩子（p.9、p.23）。

6. 井字棋用对称性之后，搜索空间从 9! 降到多少？写出算式。

棋盘有 8 种对称（4 个旋转乘镜像），第一层只剩 3 个状态（角、边、心），第二层 12 个，空间缩到至多 12 × 7! = 12 × 5040 = 60,480，相比 9! = 362,880 少了大约 83%（p.13、p.44）。

7. 爬山法的三种失败模式各是什么？根因是什么？

局部最大（周围都比自己低但不是全局最高点）、高原（一片区域得分全一样，启发函数给不出方向）、山脊（上升方向与允许的单步方向不一致）。根因只有一个：只看局部、不留历史（p.50）。

8. 最佳优先搜索和爬山法的关键差别是什么？

爬山法只在当前节点的孩子里选、其余全丢；最佳优先保留 Open 表，从所有待展开节点里挑 h 最小的，所以它能跳回早先被暂时放弃的分支（p.52）。

9. 两个八数码启发函数哪个更好？为什么？

距离之和（各方块到目标位置的曼哈顿距离之和）比不在位的方块数更准。后者只区分在不在位，差一格和差三格都算 1；前者能分辨差多远，排序更细、更接近真实剩余代价。课件原文是 Sum of distances is more accurate than the number of out-of-place tiles（p.53、p.54）。

10. 写出 f、g、h、h*、f* 的定义。A* 比 Algorithm A 多了什么条件？

g(n) 是起点到 n 已付出的实际代价，h(n) 是到目标的估计，f(n) = g(n) + h(n)；h*(n) 是到目标的真实最小代价，f*(n) = g(n) + h*(n)。Algorithm A 就是用 f = g + h 的最佳优先，A* 多了一条 h(n) ≤ h*(n)（不高估）（p.55、p.58、p.60）。

11. A* 找到目标节点时为什么不能立刻停？

Open 表里还可能有 f 更小的节点，它们有可能通向更便宜的解。p.65 找到 I（f=7）时课件写的是”找到了一条路，但还不确定是不是最短的”；必须等目标被选出来展开才算结束。BFS 可以一碰到就停，因为它每步代价相同（p.65、p.67）。

下一讲

下一讲拆掉”世界是确定的”这个假设，改用概率处理观测有噪声、信息不全时的推理。