← COMP5511 全部讲次
T03a

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 是给解打分的函数,这条式子意思是候选不比当前差就接受。比较号是 ≤,分数相同也会移动。文字说明里写的是「沿最陡方向」,四皇后题则把六个交换全算一遍再取最好的。这三处是爬山法的不同变体。

常见误解

以为爬山法的三个缺点是同一回事。局部极大是附近没有更好的点。平台是附近分数都一样,不知道往哪走。山脊是上升方向斜着,每步只能沿一个坐标轴走,只好走之字形。

回讲义:L02b-1 启发式与爬山法:雾里只看脚下往高处走

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」直接套过来 → 冲突数要最小化,方向相反。答题时写「取冲突最少的邻居」,或者把冲突数取负再最大化。

回讲义:L02a-1 搜索问题:先把题目翻译成机器能找的路

人话定义:逐词生成句子时,可能的句子多到没法穷举,于是需要一种只看局部的取舍办法。每一步只留得分最高的那个词叫贪心解码,它就是爬山法;beam search 每一步保留得分最高的 K 条部分序列。

例子:四步、每步 5 个词,共 5⁴ = 625 个序列。词表 10,000、长度 20 就是 10⁸⁰ 个,穷举不可能。贪心路线 w₄ → w₃ → w₂ → w₄ 第一步就偏离了最优路线 w₃ → w₁ → w₂ → w₁。每步框住 3 个候选时,最优路线被保住了。

常见误解

以为 beam search 保证找到最优 → K 有限时,仍可能在早期剪掉最优序列的前缀。K = 1 时它就是贪心。

回讲义:L02b-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,黑点是皇后,右边列出六种交换各自的冲突数。

  1. 初态 (3,1,2,0):列 0 和列 3 在同一条斜线上,列 1 和列 2 也是,成本 2。六种交换里最少是 1,有四个并列,按下标取 (0,1)。

    四皇后第 1 步:初态 (3,1,2,0) 两对冲突,六种交换成本 1、1、6、6、1、1,选交换 (0,1)

  2. 换完得 (1,3,2,0),只剩列 1 和列 2 冲突,成本 1。再把六种交换算一遍,(2,3) 能一步降到 0。

    四皇后第 2 步:状态 (1,3,2,0) 只剩一对冲突,六种交换成本 2、2、4、4、2、0,选交换 (2,3)

  3. 换完得 (1,3,0,2),没有任何一对互相攻击,成本 0,结束。

    四皇后第 3 步:状态 (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。

一步一步看

目标:让贪心每步挑最大的孩子走到叶子,再和全部路径的最大和比,看贪心在哪一步走错了岔口。

图按课件的连线画,有些节点被几个父节点共用。黑圈是这一步拿来比较的孩子,青绿是选中的那个。

  1. 站在根 2,孩子是 4、8、5,挑最大的 8,和变成 10。

    数字树第 1 步:根节点 2 的孩子 4、8、5 中贪心选最大的 8,目前和为 10

  2. 站在 8,它只连着 3 和 1,挑 3,和变成 13。

    数字树第 2 步:从 8 往下只连着 3 和 1,贪心选 3,目前和为 13

  3. 站在这个 3,下面是 6 和 3,挑 6,走到叶子,和为 19。

    数字树第 3 步:从第三层的 3 往下选 6,走到叶子,贪心路线的和为 19

  4. 把 20 条路径都加一遍再回头看:2 → 4 → 9 → 8 是 23。贪心在第一步就因为 8 比 4 大走错了岔口,之后不会回头。

    数字树第 4 步:贪心路线 2、8、3、6 和 19 画成黑虚线,全局最大路线 2、4、9、8 和 23 描成青绿

逐词生成

序列数用乘法原理:每一步都能从 5 个词里任选,可以重复,所以是 5⁴,不是 5!(5 的阶乘,只适用于不重复的排列)。贪心第一步选了 w₄,最优路线从 w₃ 开始,之后就回不去了。beam search 每步留 3 条,最优路线的每一步都在框里。同一页还有两问。词表 10,000、长度 20 时序列数是 10000²⁰ = 10⁸⁰,穷举不可能。找合理解最简单的办法,课件答 Hill Climbing,也就是每步只取当前得分最高的词。

一步一步看

目标:对比贪心和 K = 3 的 beam search 走过的路线,看最优路线为什么只在 beam search 里保住。

课件没给每个词的分数,下面两帧只照课件的图把两条路线和框画出来。

  1. 贪心每步只留 1 个词。第一步留下 w₄,最优路线要从 w₃ 出发,这条岔口一过就回不去,后面三步只能在 w₄ 开头的序列里挑。

    逐词生成第 1 帧:贪心解码路线 w4、w3、w2、w4,第一步选中的 w4 描成青绿

  2. beam search 取 K = 3,每步框住得分前三的候选:第一步 w₃ 到 w₅,第二步 w₁ 到 w₃,第三步 w₂ 到 w₄,第四步 w₁ 到 w₃。最优路线 w₃ → w₁ → w₂ → w₁ 每一步都落在框里,被保住了。课件按单个词画框,算法实际保留的是 3 条部分序列(到这一步为止的整串词)。

    逐词生成第 2 帧:beam search 每步框住三个候选,最优路线 w3、w1、w2、w1 描成青绿,贪心路线为灰虚线

一群点同时爬山

课件先画单峰曲面 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。青绿圈是这一步取出展开的节点。

  1. Open 里只有 S,取出展开。A、B、C 第一次出现,f 分别是 6 + 10 = 16、5 + 13 = 18、10 + 4 = 14。

    A* 第 1 步:取出 S 展开,A、B、C 进入 Open,f 分别为 16、18、14

  2. C 的 14 最小,取出 C(g = 10)。D 第一次出现,g = 16,f = 18;回到 S 的路更贵,拒。

    A* 第 2 步:取出 C,D 以 f 等于 18 进入 Open,Close 为 S、C

  3. A 的 16 最小,取出 A(g = 6)。E 第一次出现,g = 12,f = 16。

    A* 第 3 步:取出 A,E 以 f 等于 16 进入 Open,Close 为 S、C、A

  4. 取出 E(g = 12)。F 进 Open,g = 16,f = 17。经 E 到 B 的 g 是 18,比 B 现有的 5 大,拒。

    A* 第 4 步:取出 E,F 以 f 等于 17 进入 Open,经 E 到 B 更贵被拒

  5. 取出 F(g = 16)。G 进 Open,f = 19。终点只是进了 Open,Open 里还有两个 18,不能停。

    A* 第 5 步:取出 F,G 以 f 等于 19 进入 Open,Open 里 B 与 D 仍为 18 所以不停

  6. B、D 都是 18,按「同分取 h 小的」取出 D(g = 16)。经 D 到 B、C、F 都更贵,全拒。

    A* 第 6 步:B 与 D 同为 18,取 h 较小的 D 展开,邻居全部被拒

  7. 取出 B(g = 5)。经 B 到 E 的 g = 11、f = 15,比 16 小;到 D 的 g = 12、f = 14,比 18 小。D、E 都已在 Close,于是从 Close 移回 Open,这就是重开。

    A* 第 7 步:取出 B,经 B 到 E、D 更便宜,D 与 E 从 Close 移回 Open

  8. D 的 14 最小,取出 D(g = 12)。邻居没有一个变得更便宜。

    A* 第 8 步:取出 D,g 为 12,邻居全部被拒,Open 剩 G 与 E

  9. 取出 E(g = 11)。经 E 到 F 的 g = 15、f = 16,比 17 小,F 也从 Close 重开。

    A* 第 9 步:取出 E,F 的 f 从 17 降到 16,F 从 Close 移回 Open

  10. 取出 F(g = 15)。经 F 到 G 的 g = 18,比 19 小,G 更新为 18。

    A* 第 10 步:取出 F,G 的 f 从 19 更新为 18,Open 只剩 G

  11. G 被取出,这时才结束。顺着父节点回读:G 来自 F,F 来自 E,E 来自 B,B 来自 S,路径 S → B → E → F → G,代价 5 + 6 + 4 + 3 = 18。

    A* 第 11 步:取出终点 G 结束,最优路径 S、B、E、F、G 描成青绿,代价 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 分钟做变式题,重点检查同分规则和「会不会重开」。

必背

  1. 爬山法每次只看当前状态的邻居、往更好的方向走,可能停在局部极大、在平台上迷路、在山脊上走之字形
  2. 四皇后建模:状态是每列皇后的行号,邻居是交换两列,目标是互相攻击的皇后对数,要最小化;两列冲突当且仅当同行或行差等于列差
  3. 初态 (3,1,2,0) 成本 2,交换 (0,1) 得 (1,3,2,0) 成本 1,再交换 (2,3) 得 (1,3,0,2) 成本 0;同分时选下标最小的交换对
  4. 每步选最大的子节点只得到 2 → 8 → 3 → 6 共 19,全局最大是 2 → 4 → 9 → 8 共 23;贪心解码就是爬山法,beam search 每步保留 Top K 条候选来缓解
  5. A* 每次从 Open 取 f = g + h 最小的节点展开,Open 的书写顺序不是取出顺序;终点被取出时才结束,刚进 Open 时不结束
  6. 邻居的新 f 小于旧 f 就更新,若它已在 Close 里要移回 Open;本题 B 让 D、E 重开,改进传到 F、G,G 从 19 降到 18
  7. 本题最优路径 S → B → E → F → G,代价 18;h 可采纳但不一致(B–E 边上 13 > 6 + 4),所以会出现重开

完整例题

题面:在 p.23 的图上执行 p.24 的 A* 伪代码,从 S 到 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
图片来源:COMP5511 Tutorial 3.pdf, p.23

解法:括号里是 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 值,重开会不会消失。

下一讲 →
L03b-1 L03b-1 命题逻辑的语法与语义:把一句话写成符号,再用真值表一行一行算

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。