L02b-2 最佳优先与 A*:把丢掉的路记回来,再把走过的路算进去
最佳优先把 Open 表加回爬山法,按 h 挑节点;八数码两个启发函数比准不准;f = g + h 和不高估条件让 A* 保证最短,最后手算一道带权最短路径题。
一句话版
最佳优先在爬山法上加回 Open 表:每次从所有待展开的节点里挑估计离目标最近的那个,走错了还能跳回去。
A* 再把已经走过的代价也算进去,按 f = g + h 挑节点;只要估计 h 从不高估,它保证找到最短路。爬山法见 L02b-1。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 最佳优先 | Best-first / Greedy Search | 在所有候选里挑估计离终点最近的那个 |
| 启发函数 h(n) | 读「h of n」 | 对「从 n 到终点还要多少代价」的估计 |
| g(n) | 读「g of n」 | 从起点走到 n 已经实际花掉的代价 |
| f(n) | f = g + h | 经过 n 的整条路总代价的估计 |
| 可采纳 | admissible | 形容算法:有解就一定找到代价最小的那条 |
| A* | 读「A star」 | 用 f = g + h 挑节点、且 h 从不高估的最佳优先 |
一个类比:开车找路,看地图上的直线距离
你在陌生城市开车去一个地方,手机没信号,只有一张地图。每到一个路口,你可以量一量各条路的终点离目的地的直线距离。
最佳优先就是每次挑直线距离最短的那个路口去,而且把以前没去的路口都记在本子上。发现走进死胡同,就翻本子换一个。
A* 多算一样东西:油表上已经开了多远。两个路口离目的地一样近,它挑一路开过来更省的那个。直线距离永远不会比真实路程长,这正是 A* 要的「不高估」。
类比在哪里失效:
- 地图上的直线距离是现成的。搜索问题里的 h 要自己设计,设计得越接近真实值越好,但也越难算。
- 开车时你只能在一个地方。搜索算法可以在本子上任意一个路口「瞬移」过去接着展开。
从零讲起
1. 最佳优先:把 Open 表加回来
它解决什么问题
爬山法只在当前节点的孩子里挑,其余全丢,走进死胡同就回不来。最佳优先把所有待展开的节点都留在 Open 表里,每次从整张表里挑 h 最小的那个,所以能跳回早先放弃的分支。
从哪来(补充)
最佳优先搜索按某个规则扩展「最有希望」的节点。Judea Pearl 在《Heuristics》(1984)里把它描述为用启发式评价函数估计节点的前景。只看启发值的版本叫贪心最佳优先,通常用优先队列实现。出处:Wikipedia: Best-first search
直觉
Open 表变成一个按 h 排好队的队伍,h 越小越靠前。每轮从队头取一个展开,它的孩子按 h 插进队伍里合适的位置。
和 BFS 比,只是排队规则换了:BFS 按进来的先后排,最佳优先按 h 排。
一步一步看
目标:在一棵标了 h 的树上跟着 Open 表走,看最佳优先怎样跳回早先放下的 B,而爬山法停在 A。
下面这棵树里,每个节点旁边写着 h,h 越小越好,G 是目标。
-
起点 S 放进 Open。
-
取 S 展开,孩子 A(h=3)、B(h=5)按 h 排进 Open:[A, B]。
-
取 A 展开,孩子 C(h=4)、D(h=6)插进去:[C, B, D]。
-
取 C 展开,孩子 E(h=7)排到最后:[B, D, E]。
-
Open 里最小的是 B(h=5),跳回右边那支。展开 B,孩子 G(h=0)排到最前:[G, D, E]。
-
取 G,是目标,结束。路径 S-B-G。
同一棵树上的爬山法会停在 A:A 的孩子 C、D 的 h 都比 A 大,它不记得 B,退不回去。
怎么判断
每轮只做一件事:从 Open 里取 h 最小的节点;是目标就停,不是就把孩子按 h 插进 Open。
意思是:比较的范围是整张 Open 表,不只是当前节点的孩子。这一条就是它和爬山法的全部区别。
课件给的性质有四条:不检查重复状态时可能陷入无限循环;不最优;不完备;时间和空间最坏都是 O(b^d)。启发函数好的话,实际花费能大幅下降。
常见误解
以为最佳优先有了 Open 表就能保证最优
它只看 h,不看已经走了多远。h 小的节点可能是绕了远路才到的,所以仍然不完备、不最优。
试一下
上面那棵树里,如果 B 的 h 改成 8,最佳优先第 4 步会取谁?
第 3 步后 Open 是 D(6)、E(7)、B(8),按 h 排序后先取 D。B 被推到了最后,要等 D 和 E 都展开完才轮到它。
2. 八数码的两个启发函数
它解决什么问题
最佳优先的好坏全看 h。同一个八数码,可以设计两个不同的 h。要会算它们,还要说出哪个更好、为什么。
从哪来(补充)
「距离之和」用的是曼哈顿距离,又叫出租车距离:横向差几格加纵向差几格,名字来自街道呈网格的曼哈顿岛。出处:Wikipedia: Taxicab geometry
直觉
第一个函数只数有几块不在目标位置上。差一格和差三格都只算 1,很粗。
第二个函数把每块到目标位置的横竖格数加起来。它分得出差多远,所以更接近真正还要走的步数。
一步一步看
目标:给空格的三种移法各用两个启发函数打一次分,看两个 h 各怎么算,最后都挑中空格上移。
-
起始盘面第一行 2 8 3,第二行 1 6 4,第三行「7 空格 5」。
-
这一节用的目标盘面:第一行 1 2 3,第二行「8 空格 4」,第三行 7 6 5。
-
空格可以左移、上移、右移,得到三个盘面。
-
每个盘面用两个函数各打一次分:
-
两个函数都选空格上移,它的分最小。
怎么算
距离之和 = 每块方块横向差几格 + 纵向差几格,再把所有方块加起来。
意思是:空格不算方块,不计入。以空格上移那个盘面为例,不在位的只有 2、8、1:2 差 1 格,8 差 2 格,1 差 1 格,加起来是 4。
课件的结论是距离之和更准,因为它能分辨差一格和差三格。好的启发函数要不高估、接近真实值、算起来便宜,三条互相拉扯,所以课件说设计好的启发函数靠经验,很难。
常见误解
把空格也算进不在位的方块里
两个函数都只数 1 到 8 这八块方块。空格算进去会让估计偏大,可能高估。
试一下
空格左移得到的盘面里,哪五块不在位?
盘面是第一行 2 8 3、第二行 1 6 4、第三行「空格 7 5」。和目标比,不在位的是 2、8、1、6、7,共 5 块。
3. f = g + h 与 admissible
它解决什么问题
最佳优先只看前面还剩多远,不看后面已经走了多远,所以会挑中绕远路的节点。把已走的代价加进去,比较的就是整条路的总代价估计。
直觉
两条路的终点离目标一样近,一条开过来 10 公里,另一条开过来 3 公里,当然选后一条。
g 记的就是已经开了多远,h 估还剩多远,f 是两者之和。
一步一步看
目标:把 g、h、f 三个量套到八数码的三个盘面上,看第一步 g 都相同时 f 的排序和 h 一样。
- g(n):从起点走到 n 已经付出的实际代价。
- h(n):从 n 到目标的估计代价。
- f(n) = g(n) + h(n):经过 n 的整条路总代价的估计。
- 把它套在上一节八数码的三个盘面上,h 用不在位的方块数:
| 盘面 | g | h | f |
|---|---|---|---|
| 空格左移 | 1 | 5 | 6 |
| 空格上移 | 1 | 3 | 4 |
| 空格右移 | 1 | 5 | 6 |
- 三个盘面都是从起点走了一步,g 都是 1,f 的排序和 h 一样。
怎么判断
g 只有在比较不同深度的节点时才起作用。
意思是:同一层的节点 g 相同,按 f 排和按 h 排结果一样;一个浅、一个深时,深的那个 g 大,f 会把它往后推。
再看 admissible。它形容一个算法:只要解存在,就保证找到一条代价最小的解路径。课件的例子是 BFS 是 admissible 的,但常常太低效,保证最优和跑得动是两回事。
常见误解
以为 f 越小的节点一定离目标越近
f 是整条路的估计,小可能是因为 g 小(离起点近),不一定是 h 小。
试一下
一个节点 g=4、h=2,另一个 g=1、h=4。按最佳优先先取谁?按 f 先取谁?
最佳优先只看 h,先取第一个(h=2)。按 f,第一个是 6,第二个是 5,先取第二个。
4. A*:给 h 加一个不高估的条件
它解决什么问题
f = g + h 还不够保证最短。如果 h 估得太大,真正便宜的路可能一直排在后面。A* 给 h 加一个条件,换回最优性。
从哪来(补充)
A* 由 Stanford Research Institute 的 Peter Hart、Nils Nilsson、Bertram Raphael 于 1968 年首次发表,是 Shakey 机器人路径规划项目的一部分。h 恒为 0 时,A* 退化为 Dijkstra 算法。出处:Wikipedia: A* search algorithm
直觉
h 不高估,意思是它说的「还剩多远」只会比真实的少或相等,像地图上的直线距离。
这样一来,一条真正最短的路,它的 f 永远不会被估得比别的路大,迟早会排到队头。
一步一步看
目标:从理想的 f* 退到「h 不高估」这个条件,看 A* 和爬山法、最佳优先差在哪,为什么只有它保证最优。
- 理想评价函数是 f*(n) = g(n) + h*(n),h*(n) 是从 n 到目标的真实最小代价。
- h* 一般算不出来,但常常能找到一个 h 满足 h(n) ≤ h*(n)。
- 用 f = g + h 排序的最佳优先叫 Algorithm A;如果 h 满足这个条件,就叫 A*。
- 课件用方框圈出的定理:All A* algorithms are admissible,即所有 A* 都能找到最优解。
- 三个算法的区别列成表:
| 比较范围 | 排序依据 | 保证最优 | |
|---|---|---|---|
| 爬山法 | 当前节点的孩子 | 分数 | 否 |
| 最佳优先 | 整张 Open 表 | h | 否 |
| A* | 整张 Open 表 | f = g + h,且 h 不高估 | 是 |
- 手算时,生成了目标节点不能马上停。要等它从 Open 里被选出来展开,才算结束。
怎么判断
判断一个 h 能不能用于 A*:问它会不会比真实剩余代价大。
意思是:只要对每个节点都有 h(n) ≤ h*(n),就能用。h 恒为 0 一定满足,因为真实剩余代价不会是负数。课件的定理针对的是树搜索;图搜索还需要一致启发式,或者允许重新打开节点。
常见误解
问「A* 和最佳优先有什么区别」只答一条
要两条都答:A* 用 f = g + h 排序,最佳优先只用 h;A* 要求 h(n) ≤ h*(n)。另外 admissible 形容算法时指保证找到最优解,和形容 h 的不高估是两层意思。
试一下
八数码的两个启发函数,能不能用于 A*?
能。每块不在位的方块至少要挪一步,所以不在位方块数不高估;每块至少要走它的曼哈顿距离那么多步,所以距离之和也不高估。
把它们串起来
爬山法只在孩子里挑,丢掉的分支回不去。最佳优先把 Open 表加回来,每次从所有待展开的节点里挑 h 最小的,能跳回去,但只看前面不看后面,所以不完备、不最优。
h 的好坏决定最佳优先跑得多快。八数码里距离之和比不在位方块数准,因为它分得出差多远。
把已走的代价 g 加进来,按 f = g + h 排序,比较的就是整条路。再要求 h 不高估,算法就叫 A*,课件定理说所有 A* 都是 admissible 的。手算时记住最后一条:生成目标不停,取出目标才停。
课件里的坑
- [题设区别] p.53 的八数码目标盘面空格在中心,和 p.9 那个空格在右下角的目标盘面不一样,最佳优先这一节从头到尾用的是 p.53 那个(p.53)
- [读图提醒] p.67 页面上标的「= 8」是节点 L 的 f 值,不是这道题的答案;答案是 I 的 7(p.67)
- [同分规则] A* 例题里 E 和 I 的 f 都是 7,课件选 I 是同分时的取法,I 并不更小(p.67)
- [两层意思] admissible 形容算法是保证找到最优解,形容 h 是不高估,课件两处都用这个词(p.58、p.60)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写 f(n) = g(n) + h(n) 和 h(n) ≤ h*(n);再说出 A* 比最佳优先多的两个条件;然后把八数码三个盘面的两种分数算一遍;最后把下面的 A* 完整例题自己画出 Open 表,对答案时重点看第 4 步为什么不停。
必背
- 最佳优先保留 Open 表,从所有待展开节点里挑 h 最小的,能跳回被放弃的分支;但不完备、不最优
- 八数码两个启发函数:距离之和比不在位方块数更准;设计好的启发函数靠经验、很难
- f(n) = g(n) + h(n):g 是从起点已付出的实际代价,h 是到目标的估计
- admissible 形容算法时指只要解存在就保证找到代价最小的解;BFS 是 admissible 的,但常常太低效
- h(n) ≤ h*(n) 不高估是 A* 的定义条件,课件定理:All A* algorithms are admissible
- A* 手算时碰到目标不能立刻停,要等它被选出来展开才算结束
课件例题
例 1(课件 p.53–54):两个八数码启发函数哪个更好?
题面:起始盘面第一行 2 8 3,第二行 1 6 4,第三行「7 空格 5」。目标盘面第一行 1 2 3,第二行「8 空格 4」,第三行 7 6 5。空格可以左移、上移、右移,得到三个状态。分别用「不在位的方块数」和「距离之和」打分,哪个启发函数更好?
提示
先把三个新盘面写出来,再逐块和目标盘面比;距离之和是横向差几格加纵向差几格,空格不算。
解答
空格左移:不在位的是 2、8、1、6、7,共 5 块;距离之和是 6。
空格上移:盘面变成第二行「1 空格 4」、第三行 7 6 5。不在位的只有 2、8、1,共 3 块。2 差 1 步,8 差 2 步,1 差 1 步,距离之和是 4。
空格右移:不在位的是 2、8、1、6、5,共 5 块;距离之和是 6。
两个函数都选空格上移。课件的结论是距离之和更准,因为它能分辨差一格和差三格,排序更细、更接近真实剩余步数。
例 2(课件 p.56):把 f = g + h 套在这三个状态上
题面:还是例 1 那三个状态,h 用不在位的方块数。三个状态各自的 g、h、f 是多少?选哪个?
提示
三个状态离起点都只走了一步。
解答
三个状态都是从起点走了一步,所以 g = 1。h 分别是 5、3、5,f 分别是 6、4、6。选 f 最小的空格上移那个。
g 都相同时,f 的排序和 h 一样。g 只有在比较不同深度的节点时才起作用。
例 3(课件 p.61–67):用 A* 求带权有向图上 S 到 T 的最短路径
见下方完整例题。
完整例题
题面(课件 p.61–67):起点 S、终点 T,中间顶点 V1–V5,十一条带权有向边,求 S 到 T 权重之和最小的那条路径。
约定:搜索树上的节点按走过的那条边命名(走了边 a 就得到节点 A),不按图上的顶点命名。h 取「当前所在顶点的所有出边里最小的那个权重」,到了 T 就是 0。真实剩余路径至少要走一条出边,所以它不高估,满足 A* 的条件(p.61、p.62)。
- 展开 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。
- 展开 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)。
- 展开 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。
- 展开 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,不能停。
- 展开 B(在 V3,g=4)。J:b,g 到 V5,g=4+2=6,h=5,f=11。这条分支到此为止。
- 展开 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 贵。
- 此时 E 与 I 都是 f=7;沿用课件同分时优先取 I 的约定,选择 I(f=7)。把它选出来展开,它就是目标,搜索结束。
- 答案:最短路径 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 的目标时才停 → 按父节点回溯路径。本例是可采纳启发式的树搜索;图搜索还需一致性或允许重开节点。
变式题(先自己做)
改编自课件 p.61–67:同一张图、同一个起点终点,只改一个条件,把所有 h 全部取 0。
(1) 这时 A* 退化成按什么排序的搜索?它还满足 admissible 吗? (2) 最终找到的路径和总代价会不会变? (3) 展开的节点数会变多还是变少?说出机制。
提示
先把 f = g + h 里的 h 换成 0 看 f 变成什么。再回到不高估的定义式 h(n) ≤ h*(n),代 0 进去检查它成不成立,这一步决定了第 (2) 问的答案。
判分点与答案(非官方评分标准)
判分点:① 必须点明 h ≡ 0 仍然满足不高估,所以最优性不丢;② 必须把「路径不变」和「展开数变多」分开答,混成一句「效率变差所以结果变差」是这题的主要失分方式。
(1) f = g + 0 = g,变成只按已付出代价排序的搜索(即 Dijkstra 那种按已付代价排的找法)。不高估的条件是 h(n) ≤ h*(n),真实剩余代价永远非负,所以 0 恒满足,仍然 admissible(p.58、p.60)。
(2) 不变,仍是 S→V1→V4→T,总代价 7。admissible 保证的就是最优解本身,h 只影响到达它的效率。
(3) 在本例中变多。h 的作用是把「还剩多远」提前计入排序,让通往目标的分支更早浮上来。h ≡ 0 等于丢掉这个信息,那些 g 小但离目标远的节点会被先展开,原题里一直没轮到的 E、G、H 这类节点会有一部分被提前展开。
闪卡自测
1. 最佳优先搜索和爬山法的关键差别是什么?
爬山法只在当前节点的孩子里选、其余全丢;最佳优先保留 Open 表,从所有待展开节点里挑 h 最小的,所以能跳回早先被暂时放弃的分支(p.52)。
2. 最佳优先搜索有哪几条性质?
不检查重复状态时可能陷入无限循环;不最优;不完备;时间和空间最坏都是 O(b^d)。启发函数好的话,实际复杂度能大幅下降(p.57)。
3. 两个八数码启发函数哪个更好?为什么?
距离之和比不在位的方块数更准。后者只区分在不在位,差一格和差三格都算 1;前者能分辨差多远,排序更细、更接近真实剩余代价(p.53、p.54)。
4. admissible 形容一个搜索算法时是什么意思?BFS 算不算?
只要解存在,算法就保证找到一条代价最小的解路径。BFS 是 admissible 的,但常常太低效(p.58)。
5. 写出 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)。A* 多了一条 h(n) ≤ h*(n)(p.55、p.58、p.60)。
6. A* 找到目标节点时为什么不能立刻停?
Open 表里还可能有 f 更小的节点,它们可能通向更便宜的解。p.65 找到 I(f=7)时课件写的是「找到了一条路,但还不确定是不是最短的」;必须等目标被选出来展开才算结束(p.65、p.67)。
下一讲
下一讲拆掉「世界是确定的」这个假设,改用概率处理观测有噪声、信息不全时的推理。见 L03a-1。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。