← COMP5511 全部讲次
L02b-1 · 第 2 周

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

为什么盲目搜索不够用、启发式拿什么换速度;用井字棋的对称性和 most wins 打分讲清启发函数,再一步步跑爬山法,看它卡在哪三种地形上。

一句话版

启发式搜索给每个状态估一个「离目标还有多远」或者「这一步有多好」的分数,按分数挑方向走,比盲目地一个个扫快得多。代价是不再保证一定成功。

爬山法是最省事的启发式搜索:每一步只看眼前的孩子,挑分数最高的那个走过去,别的全丢。盲目搜索见 L02a-1 到 L02a-3。

先认识这几个词

词 全称 / 读法 一句人话
启发式 heuristic 帮你挑方向的经验估计,不保证对
启发函数 heuristic function 给每个状态打分的那个公式
对称 symmetry 转一转、翻一翻能重合的两个局面算同一个
爬山法 Hill Climbing 每步只往眼前最好的孩子走,不记路
局部最大 local maximum 周围都比它低,但它不是全局最高的地方
高原 / 山脊 plateau / ridge 一片分数全一样的平地 / 斜着往上、单步走不上去的窄梁

一个类比:大雾里爬山

山上起了大雾,你只看得清脚下一步远。想爬到最高点,最省事的办法是:每一步往周围最高的方向迈。

这样走很快,不用地图,也不用记路。但你可能爬上一座小山包就停了:四周都比脚下低,你以为到顶了,真正的主峰在雾的另一边。

课件的说法是一个又急躁又瞎的登山者。急躁是因为每步只挑最好的,瞎是因为只看得见一步。

类比在哪里失效:

  • 真山上你还能往回走。爬山法不记来路,丢掉的方向就再也回不去了。
  • 山的高度是现成的。搜索问题里的「高度」要自己设计一个打分函数,设计得好不好,决定了爬得准不准。

从零讲起

1. 为什么要用启发式

它解决什么问题

盲目搜索只会判断「到了没有」,只能按固定顺序扫。真实问题的状态多到扫不完,比如井字棋光是落子顺序就有 9! 种。启发式搜索用一个估计告诉你先往哪边走,把要扫的东西砍掉一大半。

直觉

找东西时,有人告诉你「大概在客厅」,你就不会先去翻厨房。这句话可能是错的,但大多数时候能省很多工夫。

启发式就是这句「大概在客厅」。它让平均情况快很多,但不保证每次都对。

一步一步看

目标:对照盲目搜索和启发式搜索手上的信号,看多一个估计分数换来了速度,也丢掉了保证。

  1. 盲目搜索手上只有一个信号:当前状态是不是目标。
  2. 启发式搜索多了一个信号:每个状态的分数,比如离目标还有多远。
  3. 有了分数,就能先展开看起来更好的节点,后展开看起来差的。
  4. 分数是估计出来的,估错了就会先走错方向。所以启发式要付出代价:
盲目搜索 启发式搜索
用到的信息 只判断是不是目标 再加一个离目标多远的估计
平均速度 慢,按固定顺序扫 估计好时快很多
完备、最优 BFS 这类可以保证 一般不保证,success is NOT guaranteed

怎么判断

问一个找法值不值得用启发式:问题规模能不能硬扫完?扫不完,就要启发式。

意思是:启发式是一笔明码标价的交易,用完备性和最优性去换速度。后面的 A* 会在满足一个条件时把最优性换回来。

课件给了两条要用启发式的理由。一是现实问题常常本身就模糊,比如医疗诊断,同样的症状可能对应几种病。二是盲目搜索在真实规模上代价太高。

常见误解

以为启发式搜索一定比盲目搜索好

它最坏情况没变好,只是估计好的时候平均快很多。估计差的时候,它可能走错方向,还丢掉最优性。

试一下

在一个很小的迷宫里找出口,只有十几个格子。值得设计启发函数吗?

不太值得。状态少到 BFS 一下就扫完,还保证最短。启发式的价值在状态多到扫不完的时候才显出来。

2. 对称性:启发式也可以是「这几个其实是同一个」

它解决什么问题

启发式不一定是一个距离。只要能少扫一些状态,就算启发式。井字棋里很多局面转一转、翻一翻就重合了,它们本质上是同一个局面,只需要算一次。

直觉

一张正方形的纸,在角上画个叉。把纸转四分之一圈,叉就到了另一个角上。对下棋来说,这两个局面没有区别。

所以空棋盘下第一子有 9 格,按对称归并后只剩三类下法:下角、下边、下中心。

一步一步看

目标:用 8 种对称把井字棋第一层的 9 个落点并成 3 类,看合并等价局面能砍掉多少状态。

  1. 正方形棋盘可以转 0°、90°、180°、270°,每种转法还可以再镜像翻一次,一共 8 种对称。

  2. 四个角互相转得到,算一类;四条边的中点也算一类;中心只有一个。

  3. 所以第一层只剩 3 个状态。

    三个井字棋盘并排:X 下在左上角、下在上边中点、下在中心,X 用青绿标出;下方注明四个角等价算一个,四条边中点等价算一个,中心只有一个

  4. 第二层也用同样的办法去掉等价的局面,课件给出只剩 12 个状态。

  5. 后面 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:一格能参与几条获胜连线,分数就是几。

  1. 整个棋盘有 8 条获胜连线:3 横、3 竖、2 对角。

  2. 角在 1 横、1 竖、1 对角上,得 3 分;边只在 1 横、1 竖上,得 2 分;中心在 1 横、1 竖、2 对角上,得 4 分。

    左边九宫格写着每格的分数:四个角 3、四条边 2、中心 4,中心描成青绿;右边画出经过中心的一横、一竖和两条对角线,旁注 1 横加 1 竖加 2 对角等于 4,角 3、边 2

  3. 爬山法第一步选分数最高的中心。

再看一棵小树,分数越高越好,看爬山法怎么走、在哪停:

  1. 起点 S 1 分,孩子 A 5 分、B 3 分。选 A,丢掉 B。

  2. A 的孩子 C 4 分、D 2 分,都比 A 的 5 分低,停在 A。

    一棵小树:起点 S 1 分,孩子 A 5 分、B 3 分;S 到 A 的边描成青绿,B 和它下面 9 分的 G 画成浅灰虚线表示被丢掉;A 的孩子 C 4 分、D 2 分都比 A 低,爬山法停在 A,这就是局部最大

  3. 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* 在修补什么。

直觉

三种地形的共同点:站在那里往四周看一步,看不出该往哪走。

局部最大是四周都比脚下低;高原是四周和脚下一样高;山脊是往上的方向斜着,你每一步只能横着或竖着迈,迈哪步都是下坡。

一步一步看

目标:逐个看局部最大、高原、山脊三种地形,看爬山法卡住的根因都是只看一步又不记历史。

  1. 局部最大:一个小山包,四周都比它低,可它不是最高的那座。爬山法爬上来就停了。

  2. 高原:一大片分数完全一样的平地,打分函数给不出方向,爬山法不知道往哪走。

  3. 山脊:一道斜着往上的窄梁,允许的单步方向和上升方向不一致,每一步都在往下走。

    三格剖面示意:左边局部最大,曲线上一个非全局的小峰标着卡在这;中间高原,一段水平平台标着卡在这;右边山脊,斜向上升的路线和允许的水平、垂直单步方向不一致;底部写着根因只有一个:只看一步、只留最好的一个孩子、不记历史

  4. 三种失败的根因是同一个:只看一步,又不记历史,卡住了也没有别的分支可以退。

怎么判断

碰到「爬山法为什么失败」,按三步答:说出三种地形的名字,各用一句话描述,最后点出根因。

意思是:局部最大是比周围高但不是最高,高原是周围一样高,山脊是上升方向走不上去。根因是只看局部、不留历史。

课件说补救办法不在这一讲范围内。常见的补救有两种:随机重启,从不同起点多爬几次;模拟退火,允许偶尔往下走一步,好跳出小山包。出处: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! 比;最后画出三种失败地形的小草图,各写一句话,再写根因。

必背

  1. 启发式搜索用到目标的距离估计指导方向,拿完备性和最优性换速度,课件原话 success is NOT guaranteed
  2. 启发式也可以是等价判断:井字棋有 8 种对称,第一层只剩 3 个状态、第二层 12 个,空间至多 12 × 7! = 60,480
  3. 爬山法只看一步、只留最好的一个孩子、不记历史,走错了就回不来
  4. 井字棋 most wins 给每格打分:角 3、中心 4、边 2,所以第一步下中心;启发函数的价值在于粗糙但便宜
  5. 爬山法三种典型失败地形:局部最大、高原、山脊,根因是只看局部、不留历史

课件例题

例 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 条线。爬山法第一步选哪一格?往下一层怎么选?

约定:分数越高越好;爬山法每层只留分数最高的一个。

解法:

  1. 列出 8 条连线:3 横、3 竖、2 对角。
  2. 角:在 1 横、1 竖、1 对角上,得 3 分。
  3. 中心:在 1 横、1 竖、2 对角上,得 4 分。
  4. 边:只在 1 横、1 竖上,得 2 分。
  5. 第一层按对称只有角、边、中心三类,分数 3、2、4。爬山法选最高分,第一步下中心。
  6. 对手落子后,X 的每个选择重新打分:这一格加上已有的己方棋子,一共还能凑出几条不含对手棋子的连线。
  7. 比如 X 占中心后再占一个角,两者共用一条对角线,去掉被对手堵死的线,剩 5 条,得 5 分。课件图上被选中的分支就是 5 分。
  8. 每层只留最高分的一个,其余全丢。

要点: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。

下一讲 →
L02b-2 L02b-2 最佳优先与 A*:把丢掉的路记回来,再把走过的路算进去

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