T03a Tutorial 3:爬山法、四皇后与 A* 手算,眼前最好不等于最后最好
四皇后怎么交换、贪心路线为什么只拿到 19、A* 发现终点后为什么还要继续,以及已关闭的节点为什么会被重新打开。
一句话版
这份习题课用三组练习把局部搜索和 A* 落到手算上。四皇后用爬山法两步到解。数字树和逐词生成说明贪心会错过最优。A* 在一张 8 节点图上把 Open/Close 表一步步填完,途中有已关闭的节点被重新打开。
先认识这几个词
读之前最好先懂 BFS、DFS 和 A* 的基本思路,见 L02a-2 BFS、L02a-3 DFS 和 L02b-2 A*。
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 局部搜索 | local search | 手里只拿一个解,每次在它附近找个更好的换掉 |
| 爬山法 | hill climbing | 局部搜索最简单的一种:哪个邻居更好就往哪走 |
| 局部极大 | local maximum | 一个小山顶:附近都比它差,但远处还有更高的山 |
| 贪心 | greedy | 每一步只挑眼前最好的,不回头 |
| beam search | 束搜索 | 每一步留得分最高的 K 条候选,而不是只留 1 条 |
| g、h | 已走代价、启发值(heuristic) | g 是从起点到这里实际花了多少,h 是估计到终点还要多少 |
| f = g + h | 读「f 等于 g 加 h」 | 经过这个点的整条路大概多长,A* 每次挑 f 最小的 |
| Open / Close | 待办表 / 已办表 | Open 放发现了还没展开的点,Close 放展开过的点 |
题目地图
讲义前面先讲爬山法的伪代码和缺点,后面是三组练习。课件署名 LIANG Ziran(助教),封面没有日期,周次未注明。
| 顺序 | 题目 | 考什么 | 主要失分点 |
|---|---|---|---|
| 1 | 爬山法伪代码与三个缺点 | 接受条件、局部极大、平台、山脊 | 把三个缺点混成一个原因 |
| 2 | 四皇后,初态 (3,1,2,0) | 状态、邻居、目标函数、同分规则 | 按最大化方向选;同分时没按下标选 |
| 3 | 数字树求最大序列和 | 贪心与全局最优的差别 | 沿位置猜连线,没按图上的边走 |
| 4 | 逐词生成与 beam search | 序列空间大小、贪心解码 | 把 5⁴ 写成 5! |
| 5 | 一群点同时爬山 | 单峰与多峰的区别 | 把单峰图上的结论推广到多峰 |
| 6 | A* 求 S 到 G 的最短路 | Open/Close 表、终止条件、重开节点 | 按书写顺序取节点;发现 G 就停;不会重开 |
A* 那张图的数据要先抄成表再开算。启发值 h:S 17、A 10、B 13、C 4、D 2、E 4、F 1、G 0。边代价:S–A 6,S–B 5,S–C 10,A–E 6,B–E 6,B–D 7,C–D 6,E–F 4,D–F 6,F–G 3。边没有画箭头,按无向图处理(两个方向都能走)。
概念卡
1. 爬山法(Hill Climbing)
人话定义:问题的可能解太多、没法一一比较时,爬山法用「只看身边」来省力。它从一个解出发看邻居,有更好的(或一样好的)就走过去,重复到迭代次数用完。
例子:课件的伪代码每轮取一个随机邻居,满足 F(Current) ≤ F(Candidate) 就接受。F 是给解打分的函数,这条式子意思是候选不比当前差就接受。比较号是 ≤,分数相同也会移动。文字说明里写的是「沿最陡方向」,四皇后题则把六个交换全算一遍再取最好的。这三处是爬山法的不同变体。
常见误解
以为爬山法的三个缺点是同一回事。局部极大是附近没有更好的点。平台是附近分数都一样,不知道往哪走。山脊是上升方向斜着,每步只能沿一个坐标轴走,只好走之字形。
2. 四皇后的建模(4-Queens Formulation)
人话定义:要让爬山法能跑,先得说清「一个解长什么样、邻居是谁、怎么打分」。四皇后里,状态 (x₀, x₁, x₂, x₃) 的 xᵢ 是第 i 列皇后的行号;邻居是交换两列的行号;分数是互相攻击的皇后对数,越少越好,0 就是解。
例子:图示状态 (2,0,3,1) 冲突数为 0。两列 i、j 冲突的条件是同行,或 |xᵢ − xⱼ| = |i − j|。意思是行差等于列差,两个皇后就在同一条斜线上。(0,1,2,3) 四个皇后在同一条对角线上,任意两个都冲突,冲突数为 6。
常见误解
把伪代码里的「最大化 F」直接套过来 → 冲突数要最小化,方向相反。答题时写「取冲突最少的邻居」,或者把冲突数取负再最大化。
3. 贪心解码与 Beam Search
人话定义:逐词生成句子时,可能的句子多到没法穷举,于是需要一种只看局部的取舍办法。每一步只留得分最高的那个词叫贪心解码,它就是爬山法;beam search 每一步保留得分最高的 K 条部分序列。
例子:四步、每步 5 个词,共 5⁴ = 625 个序列。词表 10,000、长度 20 就是 10⁸⁰ 个,穷举不可能。贪心路线 w₄ → w₃ → w₂ → w₄ 第一步就偏离了最优路线 w₃ → w₁ → w₂ → w₁。每步框住 3 个候选时,最优路线被保住了。
常见误解
以为 beam search 保证找到最优 → K 有限时,仍可能在早期剪掉最优序列的前缀。K = 1 时它就是贪心。
4. A* 的两张表与重开(A* Open / Close List)
人话定义:A* 要找最短路,又不想把所有路都试一遍,两张表帮它记住进度。Open 存已发现、待展开的节点,Close 存已展开的节点。每次从 Open 取 f 最小的展开;邻居的新 f 比旧的小就更新,在 Close 里的要移回 Open(叫「重开」)。
例子:展开 S 后 Open 写作 [A(16), B(18), C(14)],括号里是 f。下一步取 C,因为 14 最小。展开 B 时,经 B 到 D 的 f = 14、到 E 的 f = 15,都比旧值小,D、E 从 Close 移回 Open。
常见误解
以为 G 一进 Open 就找到答案 → G 刚进 Open 时 f = 19,Open 里还有两个 f = 18 的节点。伪代码规定终点从 Open 被取出时才返回,后面 G 降到了 18。
回讲义:L02b-2 最佳优先与 A*:把丢掉的路记回来,再把走过的路算进去
逐题拆解
爬山法回顾
伪代码和三个缺点没有计算,要点见概念卡 1:比较号是 ≤,局部极大、平台、山脊是三种不同的卡法。
四皇后
初态 (3,1,2,0) 有两对冲突。列 (0,3) 行差 3、列差 3;列 (1,2) 行差 1、列差 1。所以成本 2。六个交换里 (0,1)、(0,2)、(1,3)、(2,3) 成本都是 1。(0,3) 和 (1,2) 把四个皇后排上同一条对角线,成本 6。同分取下标最小的 (0,1),得 (1,3,2,0)。第二轮只剩列 (1,2) 冲突,六个交换的成本依次是 2、2、4、4、2、0。交换 (2,3) 得 (1,3,0,2),成本 0,课件标 Final Answer。补充一个复算结果:在「交换两列」这个邻居定义下,24 种排列里凡是冲突数大于 0 的,总有一个交换能严格变好。所以四皇后用这种爬山法不会卡在非解的局部极小。
一步一步看
目标:从初态开始每步挑冲突最少的交换,看爬山怎样两步把四皇后的冲突降到 0。
棋盘上行号从上往下数 0 到 3,黑点是皇后,右边列出六种交换各自的冲突数。
-
初态 (3,1,2,0):列 0 和列 3 在同一条斜线上,列 1 和列 2 也是,成本 2。六种交换里最少是 1,有四个并列,按下标取 (0,1)。
-
换完得 (1,3,2,0),只剩列 1 和列 2 冲突,成本 1。再把六种交换算一遍,(2,3) 能一步降到 0。
-
换完得 (1,3,0,2),没有任何一对互相攻击,成本 0,结束。
数字树
每一步选最大的子节点。根 2 的子节点 4、8、5 里选 8。8 下面只有 3 和 1,选 3。这个 3 下面是 6 和 3,选 6,和为 19。按图上的连线共有 20 条路径,最大的是 2 → 4 → 9 → 8,和为 23。第二是 22,贪心的 19 只排第三。第一步的 8 比 4 大,但 4 下面有 9。
一步一步看
目标:让贪心每步挑最大的孩子走到叶子,再和全部路径的最大和比,看贪心在哪一步走错了岔口。
图按课件的连线画,有些节点被几个父节点共用。黑圈是这一步拿来比较的孩子,青绿是选中的那个。
-
站在根 2,孩子是 4、8、5,挑最大的 8,和变成 10。
-
站在 8,它只连着 3 和 1,挑 3,和变成 13。
-
站在这个 3,下面是 6 和 3,挑 6,走到叶子,和为 19。
-
把 20 条路径都加一遍再回头看:2 → 4 → 9 → 8 是 23。贪心在第一步就因为 8 比 4 大走错了岔口,之后不会回头。
逐词生成
序列数用乘法原理:每一步都能从 5 个词里任选,可以重复,所以是 5⁴,不是 5!(5 的阶乘,只适用于不重复的排列)。贪心第一步选了 w₄,最优路线从 w₃ 开始,之后就回不去了。beam search 每步留 3 条,最优路线的每一步都在框里。同一页还有两问。词表 10,000、长度 20 时序列数是 10000²⁰ = 10⁸⁰,穷举不可能。找合理解最简单的办法,课件答 Hill Climbing,也就是每步只取当前得分最高的词。
一步一步看
目标:对比贪心和 K = 3 的 beam search 走过的路线,看最优路线为什么只在 beam search 里保住。
课件没给每个词的分数,下面两帧只照课件的图把两条路线和框画出来。
-
贪心每步只留 1 个词。第一步留下 w₄,最优路线要从 w₃ 出发,这条岔口一过就回不去,后面三步只能在 w₄ 开头的序列里挑。
-
beam search 取 K = 3,每步框住得分前三的候选:第一步 w₃ 到 w₅,第二步 w₁ 到 w₃,第三步 w₂ 到 w₄,第四步 w₁ 到 w₃。最优路线 w₃ → w₁ → w₂ → w₁ 每一步都落在框里,被保住了。课件按单个词画框,算法实际保留的是 3 条部分序列(到这一步为止的整串词)。
一群点同时爬山
课件先画单峰曲面 f(x, y) = e^(−(x² + y²)),再撒一群点(种群,population)。每个点在周围生成新点,和原来的点比,留下更好的,重复 N 次。课件把这个流程标为 Greedy search,问有没有办法找到全局最优。单峰时答案是能:x² + y² ≥ 0,所以 f ≤ 1,最高点在 (0, 0),任何起点都爬得上去。最后一页换成多峰曲面,问怎么缓解局部最优,课件没给答案。常见思路是随机重启(多个随机起点各爬一次,留最好的)和允许暂时变差(如模拟退火按概率接受差解)。两者都只是增加探索,不保证找到全局最优。
A* 求最短路
十次展开的顺序是 S、C、A、E、F、D、B、D、E、F,最后取出 G。前五次都是正常推进:C 的 f = 14 最先,然后 A、E、F 各为 16、16、17。第五次展开 F 时 G 进 Open,f = 19。第六次 B 和 D 同为 18,课件取了 D。题目没给同分规则,「同分取 h 小的」能得到课件的选择。第七次展开 B 是转折点。B 的 g 只有 5,经 B 到 D 的 g = 12、到 E 的 g = 11,都比原来经 C、经 A 的路线便宜,于是 D、E 被重开。之后 E 把 F 的 g 降到 15、f 降到 16,F 再把 G 的 f 降到 18。
一步一步看
目标:按 f 最小逐步取节点展开 A*,看更便宜的路怎样把节点从 Close 重开,终点为什么要出队才停。
边上的数字是边代价,节点下方是 h。表里括号中是 f,Close 记的是节点被取出那一刻的 f。青绿圈是这一步取出展开的节点。
-
Open 里只有 S,取出展开。A、B、C 第一次出现,f 分别是 6 + 10 = 16、5 + 13 = 18、10 + 4 = 14。
-
C 的 14 最小,取出 C(g = 10)。D 第一次出现,g = 16,f = 18;回到 S 的路更贵,拒。
-
A 的 16 最小,取出 A(g = 6)。E 第一次出现,g = 12,f = 16。
-
取出 E(g = 12)。F 进 Open,g = 16,f = 17。经 E 到 B 的 g 是 18,比 B 现有的 5 大,拒。
-
取出 F(g = 16)。G 进 Open,f = 19。终点只是进了 Open,Open 里还有两个 18,不能停。
-
B、D 都是 18,按「同分取 h 小的」取出 D(g = 16)。经 D 到 B、C、F 都更贵,全拒。
-
取出 B(g = 5)。经 B 到 E 的 g = 11、f = 15,比 16 小;到 D 的 g = 12、f = 14,比 18 小。D、E 都已在 Close,于是从 Close 移回 Open,这就是重开。
-
D 的 14 最小,取出 D(g = 12)。邻居没有一个变得更便宜。
-
取出 E(g = 11)。经 E 到 F 的 g = 15、f = 16,比 17 小,F 也从 Close 重开。
-
取出 F(g = 15)。经 F 到 G 的 g = 18,比 19 小,G 更新为 18。
-
G 被取出,这时才结束。顺着父节点回读:G 来自 F,F 来自 E,E 来自 B,B 来自 S,路径 S → B → E → F → G,代价 5 + 6 + 4 + 3 = 18。
课件里的坑
- [⚠️ 课件有误] p.34 上下两处 Close 都写成 [S(17), C(14), A(16), B(18), D(14), E(15)],漏了当前节点 F。按伪代码第 9 行,F 被取出后立即进 Close,应写成 [S(17), C(14), A(16), B(18), D(14), E(15), F(16)]。前面各页都加了,只有这页漏了;不影响 G 更新为 18(p.34)。
- [读图提醒] p.17 的答案印的是 5⁴,用文字抽取工具复制时上标会丢,可能变成「5!」。5! = 120 是每个词只能用一次的排列数,和本题不符(p.17)。
- [读图提醒] p.15 的图不是严格的树,第三层的 1 同时连着 4、8、5,第四层的 3 同时连着 9、3、1。按连线走,不按位置猜(p.15)。
- [补充] p.24 的伪代码只存 f,没有记父节点,却在第 6 行「return path」。手算时要给每个节点记下「从谁来」,更新 f 时一起改,否则最后回溯不出路径(p.24)。
- [补充] 课件没有解释为什么会重开节点。用 Dijkstra(一种从一点出发逐个确定最短距离的经典算法)从 G 反算真实距离,S 18、A 13、B 13、C 15、D 9、E 7、F 3、G 0,每个 h 都不超过它,h 是可采纳的,所以结果 18 是最优解;但 B–E 边上 13 > 6 + 4、B–D 边上 13 > 7 + 2,h 不一致,B 被拖到很晚才展开,前面关掉的 D、E 只好重开(p.34)。
- [补充] p.30 的同分选择没有规则依据。复算发现若先取 B,只需展开 9 次,比课件少一次,最终路径和代价不变(p.30)。
课后 10 分钟:考点复习
这 10 分钟怎么用:先花 3 分钟默写四皇后的四个要素和 A* 伪代码的三个关键行(取 f 最小、取出时判终点、更新时移出 Close);再用 4 分钟对着完整例题把 A* 的表从头抄一遍;最后 3 分钟做变式题,重点检查同分规则和「会不会重开」。
必背
- 爬山法每次只看当前状态的邻居、往更好的方向走,可能停在局部极大、在平台上迷路、在山脊上走之字形
- 四皇后建模:状态是每列皇后的行号,邻居是交换两列,目标是互相攻击的皇后对数,要最小化;两列冲突当且仅当同行或行差等于列差
- 初态 (3,1,2,0) 成本 2,交换 (0,1) 得 (1,3,2,0) 成本 1,再交换 (2,3) 得 (1,3,0,2) 成本 0;同分时选下标最小的交换对
- 每步选最大的子节点只得到 2 → 8 → 3 → 6 共 19,全局最大是 2 → 4 → 9 → 8 共 23;贪心解码就是爬山法,beam search 每步保留 Top K 条候选来缓解
- A* 每次从 Open 取 f = g + h 最小的节点展开,Open 的书写顺序不是取出顺序;终点被取出时才结束,刚进 Open 时不结束
- 邻居的新 f 小于旧 f 就更新,若它已在 Close 里要移回 Open;本题 B 让 D、E 重开,改进传到 F、G,G 从 19 降到 18
- 本题最优路径 S → B → E → F → G,代价 18;h 可采纳但不一致(B–E 边上 13 > 6 + 4),所以会出现重开
完整例题
题面:在 p.23 的图上执行 p.24 的 A* 伪代码,从 S 到 G,写出每一步取出的节点、邻居的更新和两张表。
解法:括号里是 f。「拒」表示新 f 不小于旧 f,不更新。
| 步 | 取出(g) | 邻居处理 | 之后的 Open | 之后的 Close |
|---|---|---|---|---|
| 1 | S(0) | A 16、B 18、C 14 新加入 | A(16), B(18), C(14) | S |
| 2 | C(10) | D 16 + 2 = 18 新加入;S 拒 | A(16), B(18), D(18) | S, C |
| 3 | A(6) | E 12 + 4 = 16 新加入;S 拒 | B(18), D(18), E(16) | S, C, A |
| 4 | E(12) | F 16 + 1 = 17 新加入;B 31 拒;A 拒 | B(18), D(18), F(17) | S, C, A, E |
| 5 | F(16) | G 19 新加入;D 24 拒;E 拒 | B(18), D(18), G(19) | S, C, A, E, F |
| 6 | D(16) | B 36、C 26、F 23 全拒 | B(18), G(19) | S, C, A, E, F, D |
| 7 | B(5) | E 11 + 4 = 15 < 16,重开;D 12 + 2 = 14 < 18,重开 | G(19), E(15), D(14) | S, C, A, F, B |
| 8 | D(12) | C 22、F 19、B 拒 | G(19), E(15) | S, C, A, F, B, D |
| 9 | E(11) | F 15 + 1 = 16 < 17,重开;A 27 拒 | G(19), F(16) | S, C, A, B, D, E |
| 10 | F(15) | G 18 + 0 = 18 < 19,更新;D 23 拒 | G(18) | S, C, A, B, D, E, F |
| 11 | G(18) | 是终点,返回路径 | — | — |
要点:第 5 步 G 已进 Open,Open 里还有两个 18,不能停。第 7 步是全题关键,B 的 g = 5 带来更便宜的 D、E。第 11 步按父节点回溯得 S → B → E → F → G,代价 5 + 6 + 4 + 3 = 18。
答题格式:每一步写「取出谁、它的 g」,邻居逐个写新 g、新 f 和旧 f 的比较,最后写两张表。重开的节点要明确写「从 Close 移出」。
变式题(先自己做)
改编自课件 p.12 与 p.23。
(a) 四皇后,初态改为 (0,1,2,3),规则同 p.12(交换两列、冲突最少、同分取下标最小的交换对)。写出每一步的交换和成本,直到终止。
(b) 同一张 A* 图,只把 h(B) 从 13 改成 7,其余不变;f 相同时取 h 小的。写出展开顺序、最终路径和代价,并回答:这次有没有节点被重新打开?
提示
(a) 初态四个皇后在同一条对角线上,成本 6;第一轮有四个交换并列最好。(b) 展开 S 后 B 的 f 变成 5 + 7 = 12,最先被展开;先检查 B–E、B–D 两条边上 h 是否还违反一致性。
判分点与答案(非官方评分标准)
判分点:① 成本逐个算对;② 同分规则用对;③ A* 每步取 f 最小并按规则破同分;④ 能说出是否重开及原因。
(a) (0,1,2,3) 成本 6。六个交换成本依次为 2、4、2、2、4、2,取 (0,1) 得 (1,0,2,3),成本 2。下一轮成本依次为 6、1、1、1、1、4,取 (0,2) 得 (2,0,1,3),成本 1。再下一轮依次为 2、2、4、4、2、0,取 (2,3) 得 (2,0,3,1),成本 0,停止。轨迹 6 → 2 → 1 → 0,终点是另一个解。
(b) 展开顺序 S、B、D、C、E、F、A,然后取出 G。展开 S 得 A(16)、B(12)、C(14);展开 B 得 E(15)、D(14);D 与 C 同为 14,取 h 小的 D,加入 F(19);再展开 C,经 C 到 D 的 f = 18 不更新;展开 E,F 降到 16(F 还在 Open 里,只是更新);F 与 A 同为 16,取 F,加入 G(18);展开 A,无更新;取出 G。路径 S → B → E → F → G,代价 18。没有节点被重开:B 最先展开,D、E 第一次被取出时 g 就已经最小。B–E 边上 7 ≤ 6 + 4,B–D 边上 7 ≤ 7 + 2,都满足一致性。
闪卡自测
1. p.5 的爬山法在新邻居分数相同时会移动吗?
会。接受条件是 F(Current) ≤ F(Candidate),允许横着走(p.5)。
2. 平台和山脊有什么区别?
平台是附近分数都一样,不知道往哪走;山脊是有更好的方向,但它斜着,每步只能沿坐标轴走,只好走之字形(p.8–9)。
3. (3,1,2,0) 的两对冲突是哪两对列?
(0,3) 和 (1,2),两者都是行差等于列差,在同一条对角线上(p.13)。
4. 第一轮四个候选都是成本 1,为什么选 (0,1)?
同分时选被交换的那对皇后下标最小的,(0,1) 最小(p.12–13)。
5. 数字树上贪心第一步选 8 为什么吃亏?
8 下面只有 3 和 1,4 下面有 9。贪心得 19,最大是 23(p.15)。
6. 词表 10,000、长度 20 的序列有多少个?
10000²⁰ = 10⁸⁰ 个,所以只能用贪心或 beam search 这类近似方法(p.17)。
7. 展开 S 后为什么下一步取 C 而不是 A?
A、B、C 的 f 分别是 16、18、14,取 f 最小的 C;Open 的书写顺序不是取出顺序(p.25)。
8. G 第一次进 Open 时 f 是多少?为什么不停?
19。Open 里还有 f = 18 的 B 和 D,终点要被取出时才结束(p.29)。
9. B 被展开时哪两个节点被重开?新 f 各是多少?
D 从 18 降到 14,E 从 16 降到 15,两者都从 Close 移回 Open(p.31)。
10. 本题为什么会出现重开节点?
h 可采纳但不一致:B–E 边上 h(B) = 13 大于 6 + h(E) = 10。h(B) 偏大,B 被拖到很晚才展开(p.34)。
下一步
先回到讲搜索的那一讲,把局部搜索和 A* 两节对照着重看一遍,再把完整例题的表遮住,自己从第 1 步填到第 11 步。填完后用变式题 (b) 检验:改一个 h 值,重开会不会消失。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。