L02b-1 启发式与爬山法:雾里只看脚下往高处走
为什么盲目搜索不够用、启发式拿什么换速度;用井字棋的对称性和 most wins 打分讲清启发函数,再一步步跑爬山法,看它卡在哪三种地形上。
一句话版
启发式搜索给每个状态估一个「离目标还有多远」或者「这一步有多好」的分数,按分数挑方向走,比盲目地一个个扫快得多。代价是不再保证一定成功。
爬山法是最省事的启发式搜索:每一步只看眼前的孩子,挑分数最高的那个走过去,别的全丢。盲目搜索见 L02a-1 到 L02a-3。
先认识这几个词
| 词 | 全称 / 读法 | 一句人话 |
|---|---|---|
| 启发式 | heuristic | 帮你挑方向的经验估计,不保证对 |
| 启发函数 | heuristic function | 给每个状态打分的那个公式 |
| 对称 | symmetry | 转一转、翻一翻能重合的两个局面算同一个 |
| 爬山法 | Hill Climbing | 每步只往眼前最好的孩子走,不记路 |
| 局部最大 | local maximum | 周围都比它低,但它不是全局最高的地方 |
| 高原 / 山脊 | plateau / ridge | 一片分数全一样的平地 / 斜着往上、单步走不上去的窄梁 |
一个类比:大雾里爬山
山上起了大雾,你只看得清脚下一步远。想爬到最高点,最省事的办法是:每一步往周围最高的方向迈。
这样走很快,不用地图,也不用记路。但你可能爬上一座小山包就停了:四周都比脚下低,你以为到顶了,真正的主峰在雾的另一边。
课件的说法是一个又急躁又瞎的登山者。急躁是因为每步只挑最好的,瞎是因为只看得见一步。
类比在哪里失效:
- 真山上你还能往回走。爬山法不记来路,丢掉的方向就再也回不去了。
- 山的高度是现成的。搜索问题里的「高度」要自己设计一个打分函数,设计得好不好,决定了爬得准不准。
从零讲起
1. 为什么要用启发式
它解决什么问题
盲目搜索只会判断「到了没有」,只能按固定顺序扫。真实问题的状态多到扫不完,比如井字棋光是落子顺序就有 9! 种。启发式搜索用一个估计告诉你先往哪边走,把要扫的东西砍掉一大半。
直觉
找东西时,有人告诉你「大概在客厅」,你就不会先去翻厨房。这句话可能是错的,但大多数时候能省很多工夫。
启发式就是这句「大概在客厅」。它让平均情况快很多,但不保证每次都对。
一步一步看
目标:对照盲目搜索和启发式搜索手上的信号,看多一个估计分数换来了速度,也丢掉了保证。
- 盲目搜索手上只有一个信号:当前状态是不是目标。
- 启发式搜索多了一个信号:每个状态的分数,比如离目标还有多远。
- 有了分数,就能先展开看起来更好的节点,后展开看起来差的。
- 分数是估计出来的,估错了就会先走错方向。所以启发式要付出代价:
| 盲目搜索 | 启发式搜索 | |
|---|---|---|
| 用到的信息 | 只判断是不是目标 | 再加一个离目标多远的估计 |
| 平均速度 | 慢,按固定顺序扫 | 估计好时快很多 |
| 完备、最优 | BFS 这类可以保证 | 一般不保证,success is NOT guaranteed |
怎么判断
问一个找法值不值得用启发式:问题规模能不能硬扫完?扫不完,就要启发式。
意思是:启发式是一笔明码标价的交易,用完备性和最优性去换速度。后面的 A* 会在满足一个条件时把最优性换回来。
课件给了两条要用启发式的理由。一是现实问题常常本身就模糊,比如医疗诊断,同样的症状可能对应几种病。二是盲目搜索在真实规模上代价太高。
常见误解
以为启发式搜索一定比盲目搜索好
它最坏情况没变好,只是估计好的时候平均快很多。估计差的时候,它可能走错方向,还丢掉最优性。
试一下
在一个很小的迷宫里找出口,只有十几个格子。值得设计启发函数吗?
不太值得。状态少到 BFS 一下就扫完,还保证最短。启发式的价值在状态多到扫不完的时候才显出来。
2. 对称性:启发式也可以是「这几个其实是同一个」
它解决什么问题
启发式不一定是一个距离。只要能少扫一些状态,就算启发式。井字棋里很多局面转一转、翻一翻就重合了,它们本质上是同一个局面,只需要算一次。
直觉
一张正方形的纸,在角上画个叉。把纸转四分之一圈,叉就到了另一个角上。对下棋来说,这两个局面没有区别。
所以空棋盘下第一子有 9 格,按对称归并后只剩三类下法:下角、下边、下中心。
一步一步看
目标:用 8 种对称把井字棋第一层的 9 个落点并成 3 类,看合并等价局面能砍掉多少状态。
-
正方形棋盘可以转 0°、90°、180°、270°,每种转法还可以再镜像翻一次,一共 8 种对称。
-
四个角互相转得到,算一类;四条边的中点也算一类;中心只有一个。
-
所以第一层只剩 3 个状态。
-
第二层也用同样的办法去掉等价的局面,课件给出只剩 12 个状态。
-
后面 7 个格子的顺序不再去重,按全排列算。
怎么算
去重之后,搜索空间至多 12 × 7!。
意思是:前两步只剩 12 种本质不同的局面,每种后面还有 7 个空格按顺序落子,共 7! 种。
代进数字:7! = 5040,12 × 5040 = 60,480。和全枚举的 9! = 362,880 比,少了大约 83%。
常见误解
以为启发式一定是「离目标多远」
对称性就不是距离,它判断的是哪些状态其实是同一个。能让搜索少做无用功的经验规则,都算启发式。
试一下
空棋盘上 X 下在右下角,和 X 下在左上角,算同一类吗?X 下在右边中点呢?
右下角和左上角都是角,把棋盘转 180° 就重合,算同一类。右边中点属于「边」那一类,和角不是一类。
3. 爬山法怎么走
它解决什么问题
有了打分函数,最便宜的用法就是每一步挑分数最高的孩子走。不用存 Open 表,不用记来路,算得极快。这就是爬山法。
直觉
站在当前节点上,看一眼它的所有孩子,挑分数最高的那个走过去,其余的扔掉。再从新位置重复。
如果所有孩子都不比自己高,就停下,认为到顶了。
一步一步看
目标:先按 most wins 给井字棋每格打分,再在一棵小树上跑爬山法,看它停在 A、错过 9 分的 G。
先看井字棋的打分函数 most wins:一格能参与几条获胜连线,分数就是几。
-
整个棋盘有 8 条获胜连线:3 横、3 竖、2 对角。
-
角在 1 横、1 竖、1 对角上,得 3 分;边只在 1 横、1 竖上,得 2 分;中心在 1 横、1 竖、2 对角上,得 4 分。
-
爬山法第一步选分数最高的中心。
再看一棵小树,分数越高越好,看爬山法怎么走、在哪停:
-
起点 S 1 分,孩子 A 5 分、B 3 分。选 A,丢掉 B。
-
A 的孩子 C 4 分、D 2 分,都比 A 的 5 分低,停在 A。
-
B 下面其实有 9 分的 G。爬山法丢掉 B 时就看不到它了,也退不回去。
怎么判断
爬山法每一步只做一件事:在当前节点的孩子里挑分数最高的。
意思是:它只比较孩子,不比较以前丢掉的节点;孩子都不如自己,就停。所以它的走法是一条线,不是一棵树。
打分函数的要求是算得快。most wins 只是数连线,很粗糙,但几乎不花时间。太贵的打分函数还不如直接搜。
常见误解
以为爬山法停下来的地方就是最好的
它停下只说明周围的孩子都不比自己好。更好的状态可能在早先丢掉的分支里,比如上面那棵树里的 G。
试一下
上面那棵树里,如果 A 的孩子 C 改成 6 分,爬山法会怎么走?停在哪?
S 选 A(5 分),A 的孩子 C 6 分比 A 高,走到 C。C 没有孩子,停在 C。路径 S-A-C,仍然碰不到 9 分的 G。
4. 爬山法的三种失败
它解决什么问题
爬山法便宜,但容易卡住。课件列出三种会困住它的地形,考试常问。知道卡在哪,才知道后面的最佳优先和 A* 在修补什么。
直觉
三种地形的共同点:站在那里往四周看一步,看不出该往哪走。
局部最大是四周都比脚下低;高原是四周和脚下一样高;山脊是往上的方向斜着,你每一步只能横着或竖着迈,迈哪步都是下坡。
一步一步看
目标:逐个看局部最大、高原、山脊三种地形,看爬山法卡住的根因都是只看一步又不记历史。
-
局部最大:一个小山包,四周都比它低,可它不是最高的那座。爬山法爬上来就停了。
-
高原:一大片分数完全一样的平地,打分函数给不出方向,爬山法不知道往哪走。
-
山脊:一道斜着往上的窄梁,允许的单步方向和上升方向不一致,每一步都在往下走。
-
三种失败的根因是同一个:只看一步,又不记历史,卡住了也没有别的分支可以退。
怎么判断
碰到「爬山法为什么失败」,按三步答:说出三种地形的名字,各用一句话描述,最后点出根因。
意思是:局部最大是比周围高但不是最高,高原是周围一样高,山脊是上升方向走不上去。根因是只看局部、不留历史。
课件说补救办法不在这一讲范围内。常见的补救有两种:随机重启,从不同起点多爬几次;模拟退火,允许偶尔往下走一步,好跳出小山包。出处:Wikipedia: Hill climbing
常见误解
把高原和山脊混成一个
高原是一片区域分数全一样,打分函数给不出方向。山脊是有上升方向,但允许的单步方向和它不一致,单步走不上去。
试一下
一个打分函数给八数码的每个盘面打分,结果走了几步以后,所有孩子的分数都和当前盘面一样。爬山法遇到的是哪种地形?
高原。周围分数全一样,打分函数给不出方向,爬山法不知道往哪走。
把它们串起来
盲目搜索只能按固定顺序扫,规模一大就扫不完。启发式搜索多知道一样东西:每个状态的分数。用它挑方向,平均快很多,代价是不再保证成功。
启发式不一定是距离。井字棋用对称性把等价的局面合并,第一层只剩 3 个状态,空间至多 12 × 7!,这也是启发式。
有了分数,最便宜的用法是爬山法:每步只在孩子里挑最高分,其余全丢,不记来路。井字棋的 most wins 给角 3 分、边 2 分、中心 4 分,所以爬山法第一步下中心。
爬山法便宜,也最容易卡住:局部最大、高原、山脊,三种地形都让它看不出下一步。根因是只看一步、不留历史。下一页的最佳优先把 Open 表加回来,A* 再加上已走的代价,一步步把丢掉的保证找回来。
课件里的坑
- [拼写] 课件把井字棋写成 Tic-Tac-Toc,指的就是 Tic-Tac-Toe(p.43、p.48)
- [只是演示] p.49 第二层的得分 3、4、4、5 和 5、4、4、4 只是演示,不用背具体数字,理解「每层只留最高分的一个」就够(p.49)
- [术语] 课件把第三种失败写成 shoulder / ridge,准确说是山脊 ridge:单步方向不能沿山脊前进(p.50)
- [范围] 随机重启、模拟退火这些补救办法课件明说不在本讲范围,考试只要求说出三种失败和根因(p.50)
课后 10 分钟:考点复习
这 10 分钟怎么用:合上页面,先默写「拿完备性和最优性换速度」这句话;再在纸上画九宫格,写出 most wins 的九个分数;然后算一遍 12 × 7!,和 9! 比;最后画出三种失败地形的小草图,各写一句话,再写根因。
必背
- 启发式搜索用到目标的距离估计指导方向,拿完备性和最优性换速度,课件原话 success is NOT guaranteed
- 启发式也可以是等价判断:井字棋有 8 种对称,第一层只剩 3 个状态、第二层 12 个,空间至多 12 × 7! = 60,480
- 爬山法只看一步、只留最好的一个孩子、不记历史,走错了就回不来
- 井字棋 most wins 给每格打分:角 3、中心 4、边 2,所以第一步下中心;启发函数的价值在于粗糙但便宜
- 爬山法三种典型失败地形:局部最大、高原、山脊,根因是只看局部、不留历史
课件例题
例 1(课件 p.43–44):井字棋用对称性能把搜索空间砍到多少?
题面:井字棋全枚举有 9! = 362,880 种落子顺序。棋盘转 90°、180°、270° 或镜像翻过来,局面本质不变。利用这种对称,第一层、第二层各剩几个状态?搜索空间最多还剩多少?
提示
先数空棋盘下第一子有几类本质不同的位置,再用课件给的第二层个数,乘上剩下格子的全排列。
解答
棋盘有 8 种对称(4 个旋转乘镜像)。空盘落第一子看似有 9 格,去掉等价的只剩 3 类:角、边、中心。所以第一层只剩 3 个状态,第二层只剩 12 个。
搜索空间最多 12 × 7! = 12 × 5040 = 60,480,比 362,880 少了大约 83%。这道题说明启发式也可以是「哪些状态其实是同一个」的等价判断。
例 2(课件 p.48–49):井字棋爬山法第一步下哪里?
见下方完整例题。
完整例题
题面(课件 p.48–49):启发函数 most wins 给每一格打分,分数是这一格能参与多少条获胜连线。整盘有 3 横、3 竖、2 对角共 8 条线。爬山法第一步选哪一格?往下一层怎么选?
约定:分数越高越好;爬山法每层只留分数最高的一个。
解法:
- 列出 8 条连线:3 横、3 竖、2 对角。
- 角:在 1 横、1 竖、1 对角上,得 3 分。
- 中心:在 1 横、1 竖、2 对角上,得 4 分。
- 边:只在 1 横、1 竖上,得 2 分。
- 第一层按对称只有角、边、中心三类,分数 3、2、4。爬山法选最高分,第一步下中心。
- 对手落子后,X 的每个选择重新打分:这一格加上已有的己方棋子,一共还能凑出几条不含对手棋子的连线。
- 比如 X 占中心后再占一个角,两者共用一条对角线,去掉被对手堵死的线,剩 5 条,得 5 分。课件图上被选中的分支就是 5 分。
- 每层只留最高分的一个,其余全丢。
要点:most wins 很粗糙,但只要数连线,几乎不花时间。启发函数要的就是粗糙但便宜。
答题格式:先写打分规则,再列角、边、中心三类的分数和算法,最后写爬山法的选择。
变式题(先自己做)
(1) 改编自课件 p.48:把棋盘换成 4×4,获胜要连成一整行、一整列或一条主对角线(共 4 横、4 竖、2 对角)。角、边上非角的格、中间四格各得几分? (2) 改编自课件 p.44:如果只用旋转、不用镜像,棋盘有几种对称?空棋盘下第一子还是 3 类吗? (3) 自编情境:一个爬山法从 S 出发,S 0 分;孩子 P 6 分、Q 4 分;P 的孩子 6 分和 5 分;Q 的孩子有一个 10 分。爬山法停在哪?最终拿到几分?碰到的是哪种地形?
提示
(1) 数一格同时在几条线上,主对角线只有两条。(2) 旋转有 4 种。(3) 爬山法只在孩子里挑比自己高的。
判分点与答案(非官方评分标准)
判分点:① (1) 三类格子都要给分数和算法;② (3) 要写出停下的理由和地形名称。
(1) 角:1 横 + 1 竖 + 1 对角 = 3 分。边上非角的格:1 横 + 1 竖 = 2 分。中间四格:每格都在一条主对角线上,1 横 + 1 竖 + 1 对角 = 3 分。
(2) 4 种(转 0°、90°、180°、270°)。第一子仍是 3 类:四个角能互相转到,四条边中点能互相转到,中心一个。镜像在这一层不改变分类。
(3) S 选 P(6 分)。P 的孩子 6 分不比 P 高,5 分更低,停在 P,得 6 分。这是局部最大,也带一点高原的味道(有一个孩子同分);10 分在丢掉的 Q 那支里。
闪卡自测
1. 课件给了哪两条需要启发式搜索的理由?
现实问题本身常常模糊,比如医疗诊断;盲目搜索在真实规模上代价高到不可接受(p.41)。
2. 启发式搜索拿什么换速度?课件原话是什么?
拿完备性和最优性换速度,success is NOT guaranteed(p.42)。
3. 井字棋用对称性之后,搜索空间从 9! 降到多少?写出算式。
8 种对称,第一层只剩 3 个状态,第二层 12 个,空间至多 12 × 7! = 12 × 5040 = 60,480,相比 9! = 362,880 少了大约 83%(p.13、p.44)。
4. 本讲的三种启发式方法是什么?它们是什么关系?
爬山法、最佳优先、A*。递进关系:爬山法只看一步只留一个;最佳优先看整个 Open 但只看 h;A* 看整个 Open,h 和 g 一起看(p.45)。
5. 爬山法的两条技术限制是什么?
只保留最好的那个孩子,其余全丢;不保存历史,没有 Open 表可以退回(p.47)。
6. most wins 怎么打分?角、边、中心各几分?
一格能参与几条获胜连线就得几分。角 3、中心 4、边 2,第一步下中心(p.48、p.49)。
7. 爬山法的三种失败模式各是什么?根因是什么?
局部最大(周围都比自己低但不是全局最高点)、高原(一片区域得分全一样)、山脊(上升方向与允许的单步方向不一致)。根因:只看局部、不留历史(p.50)。
下一讲
把爬山法丢掉的 Open 表加回来,就是最佳优先;再把已经走过的代价算进去,就是 A*。见 L02b-2。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。