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

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

从八数码讲起,把一个问题拆成状态、动作、代价和解,画成状态图和搜索树,再认识最笨的生成测试、Open / Close 循环,以及衡量搜索算法的四把尺子。

一句话版

搜索就是在一大堆可能的「样子」之间找一条路:从现在的样子走到想要的样子,每一步只能做规定好的动作。动手找之前,要先把题目翻译成状态、动作、代价,交出去的答案是那条路。

这一页只讲怎么把问题摆好,以及拿什么尺子去量一个找法好不好。具体的找法从下一页 L02a-2 的 BFS 开始。

先认识这几个词

词 全称 / 读法 一句人话
状态 state 问题在某一刻的样子,比如一个棋盘局面
动作 action 从一个状态变到另一个状态的一步操作
解 solution 从起始状态走到目标状态的一串动作,也就是一条路径
状态图 / 搜索树 state graph / search tree 把状态画成点、动作画成线;从起点展开成树就是搜索树
展开 expand 把一个节点能走到的下一步(孩子)全部生成出来
Open / Close 表 待展开表 / 已展开表 Open 放等着展开的节点,Close 放已经展开过的
盲目 / 启发式搜索 uninformed / informed search 不知道往哪走更近 / 有一个「离目标还有多远」的估计

一个类比:用导航软件之前,先得告诉它几件事

打开导航,你得先填起点和终点,还得选走路、开车还是坐地铁。导航不会问你「终点长什么样」,终点你早就知道了。它交给你的是一条路线:先往哪拐,再往哪拐。

搜索问题也是这样。起始状态和目标状态是题目给的,动作是规定好的几种,每一步可能有代价。算法交出来的是一串动作。

导航怎么比较两条路线?看能不能到、是不是最快、算得慢不慢、占不占手机内存。评价搜索算法用的也是这四件事。

类比在哪里失效:

  • 导航手里有整张地图,算距离很方便。盲目搜索连「离终点多远」都不知道,只会判断「到了没有」。
  • 地图上的路口数量有限。很多搜索问题的状态多到列不完,这正是要研究找法的原因。

从零讲起

1. 搜索问题的五要素和「解」

它解决什么问题

计算机不会读题。你得把一个问题拆成它能处理的几样东西:现在在哪、要去哪、能怎么走、每走一步花多少,以及最后交什么。拆不清楚,后面任何算法都用不上。

从哪来(补充)

课件从头用到尾的八数码,是更大的 15 数码的缩小版。15 数码由美国人 Noyes Palmer Chapman 发明,约 1874 年给朋友看过雏形,1880 年在美国流行成一股风潮。

后来它成了研究搜索和启发式算法的经典题目。八数码最难的盘面,最少也要 31 步才能解开。

出处:Wikipedia: 15 puzzle

直觉

八数码是一个 3×3 的滑块拼图,八个数字块加一个空格。每次只能把空格旁边的一块推进空格。

换个角度看,等于是空格在上下左右地动。这样一来,动作只剩四种:空格上、下、左、右,用不着去管是哪个数字在动。

一步一步看

目标:把八数码拆成当前状态、目标、动作、代价和解五样,看一道题怎样变成机器能处理的形式。

  1. 当前状态:起始盘面,第一行 1 2 3,第二行「空格 4 6」,第三行 7 5 8。

  2. 目标状态:第一行 1 2 3,第二行 4 5 6,第三行「7 8 空格」。这是题目直接给的。

  3. 动作:空格上、下、左、右移一格。空格在左边中间,只能往上、往下、往右。

  4. 代价:每移一步算 1。

  5. 解:空格右移、下移、再右移,三步到目标。下图把这三步画了出来。

    四个八数码盘面从左到右排开:起始盘面 1 2 3、空格 4 6、7 5 8,经过空格右移、空格下移、空格右移三步,变成目标盘面 1 2 3、4 5 6、7 8 空格;每个盘面里的空格用青绿框标出

怎么判断

拿到一个问题,按五行填表:当前状态、目标状态、动作、代价、解。

意思是:前四行是题目给你的条件,第五行才是要你找的东西。最后一行一定要写成一串动作,比如「右、下、右」。只写一个盘面不算解。

常见误解

把「解」答成目标状态

目标盘面一开始就写在题面上,不用找。要找的是怎么走过去,所以解是一条路径。这是这一讲最容易丢分的地方。

以为八数码里每次是数字块在挑方向走

站在数字块的角度,每块能不能动、往哪动都要单独判断,很麻烦。站在空格的角度,动作永远只有上下左右四种。课件的写法是空格在动。

试一下

把「走迷宫」写成五要素:一个格子迷宫,从入口走到出口,每次走一格。

当前状态:人站在入口那一格。目标状态:人站在出口那一格。动作:往上下左右没有墙的格子走一格。代价:每走一格算 1。解:从入口到出口的一串走法,比如「右、右、下、右」。

2. 状态图和搜索树

它解决什么问题

五要素填好以后,要有一张图把所有状态和它们之间的走法摆出来,算法才知道在什么上面找。这张图就是状态图。算法从起点出发一层层展开,画出来的是搜索树。

直觉

状态图像一张地铁线路图:每个站是一个状态,两站之间的线是一步动作。一个站只画一次,不管有几条线经过它。

搜索树像你把「从这一站出发能到哪」一层层写在纸上。同一个站从不同方向都能到,于是它会在纸上出现好几次。

一步一步看

目标:从状态图的起点 A 一层层展开成搜索树,看同一个状态怎样在树里重复出现。

  1. 状态图里,一个节点就是一个状态,一条边就是一次状态转移。

  2. 从起点 A 出发,把 A 能走到的 B、C 画成它的孩子。

  3. 再展开 B:B 在图里连着 A 和 C,A 是父节点不算,孩子是 C。

  4. 展开 C:C 连着 A、B、G,去掉父节点 A,孩子是 B 和 G。

  5. 这时 B 和 C 都在树里出现了第二次。下图左边是状态图,右边是展开出来的搜索树,青绿圈是重复出现的状态。

    左边是有 A、B、C、G 四个状态的状态图,边是 A-B、A-C、B-C、C-G;右边从 A 展开成搜索树,A 的孩子 B、C,B 下面又出现 C,C 下面又出现 B 和 G,重复出现的 C 和 B 用青绿圈标出

  6. 课件还画了两种节点。一个节点的几条边之间如果有一道弧线连着,叫 And 节点,几条子路要全部完成;没有弧线的叫 Or 节点,走通任何一条就行。

    两个小图并排:左边 Or 节点,一个父节点连三个孩子,边之间没有弧线,任选一条走通即可;右边 And 节点,三条边被一道青绿弧线连起来,几条子路必须全部完成

怎么判断

看到图,先问两件事。第一,节点是什么、边是什么。第二,某个节点的边之间有没有弧线。

意思是:有弧线就是 And,要把每条子路都走通;没有弧线就是 Or,选一条就够。这一讲后面所有算法都在 Or 图上找路,And 只要求认得那道弧线。

常见误解

以为状态图和搜索树是同一个东西

状态图里每个状态只出现一次;搜索树是从起点展开的记录,同一个状态可以出现很多次。树里的重复,正是后面要用 Close 表去挡的东西。

试一下

一张状态图只有三个状态 P、Q、R,边是 P-Q、Q-R、R-P。从 P 展开两层(不算父节点),搜索树长什么样?

第 1 层:P 的孩子是 Q、R。第 2 层:Q 的孩子是 R(去掉父节点 P);R 的孩子是 Q(去掉父节点 P)。三个状态的图,展开两层就有 5 个节点,Q 和 R 各出现两次。

3. 生成测试:最笨的办法

它解决什么问题

有了状态图,最直接的找法是把所有可能都列出来,再一个个检查是不是解。这叫生成测试(Generate and Test)。它的用处是给后面所有算法立一个对照组:能比它少试一些,就算进步。

直觉

忘了三位数密码锁的密码,你可以从全是零开始,一个数一个数往上试。一定能打开,但要试很多次。位数一多,试的次数会涨得非常快。

一步一步看

目标:把井字棋的落子顺序一子一子乘起来,看生成测试要列的可能多到 362,880 种。

拿井字棋算一笔账:9 个格子,把落子的先后顺序全部列出来。

  1. 第一子有 9 个格子可选。
  2. 第二子还剩 8 个。
  3. 第三子还剩 7 个,依此类推,最后一子只剩 1 个。
  4. 把每一步的选择数乘起来,就是全部顺序的个数:
第几子 可选格数 累计乘积
1 9 9
2 8 9 × 8 = 72
3 7 72 × 7 = 504
4 到 9 6、5、4、3、2、1 504 × 720 = 362,880

怎么算

9! = 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 362,880。

意思是:每多一个格子,总数就要再乘一个更大的数,这种增长叫阶乘。课件给这个数的批注是 High Complexity。

旅行商问题更夸张:n 个城市,每个城市去一次再回到起点,不同环路有 (n−1)!/2 条。意思是:除以 2,是因为同一个环正着走和反着走算一条。

常见误解

以为生成测试太笨,所以没用

状态少的时候它简单可靠,一定找得到。它的问题只在规模:阶乘涨得太快,状态一多就试不完。后面讲的算法,都是想办法少试一些。

试一下

旅行商问题有 5 个城市,不同环路有多少条?6 个城市呢?

5 个城市:(5−1)!/2 = 24/2 = 12 条。6 个城市:(6−1)!/2 = 120/2 = 60 条。多一个城市,环路数就乘了 5。

4. 盲目搜索、启发式搜索和 Open / Close 循环

它解决什么问题

生成测试一次把所有可能都列出来。更聪明的办法是边走边展开,只生成需要的部分。这时要回答两个问题:手上有什么信息可以帮你挑方向,以及怎么记住哪些节点等着展开、哪些已经展开过。

直觉

搜索方法分成两大类。盲目搜索只会做一件事:判断当前状态是不是目标,别的一概不知道。启发式搜索多知道一样东西:离目标大概还有多远。

两类都用同一套记账法:Open 表放「生成了、还没展开」的节点,Close 表放「已经展开过」的节点。

一步一步看

目标:把 Open / Close 循环走一遍,看「从 Open 取哪一个」怎样分出 BFS、DFS 和几种启发式算法。

  1. 把起点放进 Open。

  2. 从 Open 里取一个节点出来。

  3. 它是目标,就结束。

  4. 它不是目标,就展开它,把孩子放进 Open。

  5. 把它放进 Close,回到第 2 步。下图上半是这个循环,下半是 Open 换两种容器分别得到 BFS 和 DFS。

    三步循环:从 Open 取一个节点、是目标就结束否则展开孩子入 Open、把它移进 Close 表;下半是同一个 Open 表换两种容器,队列右进左出得到 BFS,栈右进右出得到 DFS

  6. 第 2 步「取哪一个」由什么决定,就分出了不同算法:

类别 算法 第 2 步取哪一个
盲目 BFS 最早放进去的那个(队列)
盲目 DFS 最晚放进去的那个(栈)
启发式 爬山法 只看当前节点的孩子,取估计最好的
启发式 最佳优先 整个 Open 里估计离目标最近的
启发式 A* 整个 Open 里「已走代价 + 估计剩余」最小的

怎么判断

看一个算法属于哪一类,只问一句:它挑下一个节点时,有没有用到离目标还有多远的估计?

意思是:有用到就是启发式,没用到就是盲目。BFS 和 DFS 是盲目搜索,爬山法、最佳优先、A* 是启发式搜索。

常见误解

以为 Close 表只是用来记录走过哪里

它的主要作用是防止重复展开。已经在 Close 里的状态再出现就跳过,否则碰上环就会一直绕圈。上一节搜索树里重复出现的 B、C,就是靠它挡掉的。

试一下

一个算法每次从 Open 里挑「已经走了最少步数」的节点展开,没用任何关于目标的信息。它是盲目搜索还是启发式搜索?

盲目搜索。「已经走了几步」是从起点算过来的,和目标在哪无关。判断标准只看有没有用离目标还有多远的估计。

5. 四把尺子:完备性、最优性、时间、空间

它解决什么问题

找法有很多种,得有统一的标准去比。课件给了四条,后面每个算法都要回来对照一遍。复杂度公式里还要用到三个字母 d、b、m,这里一起定下来。

直觉

四把尺子各问一个问题。完备性:只要有解,一定找得到吗?最优性:找到的是最好的那条吗?时间:要展开多少节点?空间:同一时刻要在内存里存多少节点?

一步一步看

目标:在一棵搜索树上数出 b、d、m,看后面的时间和空间量级要用到哪几个字母。

  1. 先把搜索树画出来,数每个节点有几个孩子,平均值就是分支因子 b。
  2. 数整棵树有多深,记作 d。
  3. 找到离起点最近的那个解,它在第几层,记作 m。
  4. 时间和空间都用这三个字母写成量级,量级用大 O 记号,只看增长速度。
符号 课件原文 含义
d depth of the search tree 搜索树的深度,整棵树能有多深
b (average) branching factor 分支因子,每个节点平均几个孩子
m depth of the shallowest solution 最浅那个解在第几层

怎么判断

比较两个算法时,四条逐一写:完备吗、最优吗、时间多少、空间多少。

意思是:别只说「这个快、那个省内存」,要点名是哪一把尺子。BFS 和 DFS 的对比见 L02a-3 最后一节。

d 和 m 是两个东西:d 是整棵树的深度,m 是最浅解的深度,d 可以远大于 m。

常见误解

把 d 和 m 记反

很多教材里这两个字母的意思正好相反。考试按本课件来:d 是树深,m 是最浅解的深度。

以为「完备」和「最优」是一回事

完备只管找不找得到;最优还要求找到的是最好的那条。一个算法可以完备但不最优,比如找得到路,但不一定是最短的。

试一下

一棵树每个节点 3 个孩子,最深到第 20 层,离起点最近的解在第 4 层。b、d、m 各是多少?

b = 3,d = 20,m = 4。d 远大于 m,这种树上「会不会一直往深处钻」就成了要紧的问题,见 DFS 那一页。

把它们串起来

这一页做的是找路之前的准备。

先把题目翻译成五要素,交出去的解是一条路径。再把所有状态和走法画成状态图,从起点展开就得到搜索树。树里会有重复的状态,所以要有 Close 表挡住它们。

最笨的找法是生成测试,把可能全列出来。井字棋就有 9! 种顺序,阶乘涨得太快,实际问题列不完。于是改成边走边展开,用 Open 和 Close 两张表记账。每一轮从 Open 里取一个节点,取哪一个,就决定了是哪个算法。

取的时候不用任何关于目标的信息,叫盲目搜索;用上「离目标还有多远」的估计,叫启发式搜索。最后,拿完备性、最优性、时间、空间四把尺子去量每一个算法。

课件里的坑

  • [口径差异] 课件定义 d 是搜索树深度、m 是最浅解的深度;很多教材这两个字母正好相反,考试按本课件这套记(p.15)
  • [只提一句] And / Or 节点只在 p.8 出现,后面所有算法讲的都是 Or 图;认得那道弧线就够,不用会解 And-Or 图(p.8)
  • [题设区别] p.9 的八数码目标盘面空格在右下角;后面讲启发式时 p.53 换了一个空格在中心的目标盘面,两题别混(p.9、p.53)
  • [引子不考解法] 旅行商问题只拿来说明「状态多到不能穷举」,课件不要求解它(p.10)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写五要素,最后一行写「解是一条路径」;再画一个四个状态的小状态图,从起点展开两层,圈出重复的节点;然后过一遍三道课件例题;最后把 d、b、m 三个字母的意思写一遍,确认没记反。

必背

  1. 搜索问题五要素:当前状态 / 目标状态 / 动作 / 代价 / 解;解是一条路径,不是一个状态
  2. 状态图里节点是状态、边是状态转移;And 节点的几条边被弧线连起来、要全部完成,Or 节点任选一条走通
  3. 生成测试把所有可能列出来逐个检查,井字棋要试 9! = 362,880 种,是后面所有算法的对照组
  4. 盲目搜索只会判断当前状态是不是目标;启发式搜索多用一样东西:离目标还有多远的估计
  5. Open 是待展开、Close 是已展开;循环三步:从 Open 取一个,是目标就停,否则孩子进 Open、它自己进 Close
  6. 评价一个搜索算法只看四条:完备性、最优性、时间、空间;本课件 d = 搜索树深度,b = 分支因子,m = 最浅解的深度,且 d 可以远大于 m

课件例题

例 1(课件 p.9):八数码怎么写成搜索问题?

见下方完整例题。

例 2(课件 p.10):旅行商问题能不能穷举?

题面:一张地图上有 n 个城市,推销员要每个城市去一次再回到出发地,求最短的环路。

提示

先想不同的环路有多少条,再想这个数随 n 怎么长。

解答

不同环路的条数是 (n−1)!/2。阶乘长得极快,城市一多就没法一条条试。这是「状态多到不能穷举」的标准例子,课件只拿它当引子,不要求解。

例 3(课件 p.13):井字棋生成测试要试多少种?

题面:生成测试法把所有可能列出来,再一个个检查是不是解。井字棋有 9 个格子,把落子顺序全部列出来有多少种?

提示

第一子有几格可选,第二子还剩几格?把每一步的选择数乘起来。

解答

9 个格子的全排列是 9! = 9×8×7×6×5×4×3×2×1 = 362,880 种。课件的批注是 High Complexity。这个数是后面所有算法的对照组,能比它少展开一些节点就算有进步。

完整例题

题面(课件 p.9):3×3 的盘面上有 1 到 8 八个方块和一个空格。起始盘面第一行 1 2 3,第二行「空格 4 6」,第三行 7 5 8。目标盘面第一行 1 2 3,第二行 4 5 6,第三行「7 8 空格」。允许的动作是 Up、Down、Left、Right。写出这个问题的状态、动作、代价和解。

约定:动作指空格的移动方向;每移一步代价 1。

解法:

  1. 状态:一个盘面,也就是九个格子各放了什么。
  2. 当前状态和目标状态:题面给的两个盘面。
  3. 动作:空格往上、下、左、右移一格,动的是空格。起始盘面的空格在左边中间,属于边,只有 3 个动作:上、下、右。
  4. 代价:每步 1。
  5. 找解:比较两个盘面,第二行要变成 4 5 6,第三行要变成 7 8 空格。空格右移,第二行变成「4 空格 6」;空格下移,5 上到第二行,第三行变成「7 空格 8」;空格右移,8 左移一格,到达目标。
  6. 答案:解是「右、下、右」这三步,代价 3。

要点:答题时目标盘面只是条件,交出去的是动作序列。

答题格式:按五要素各写一行,最后一行写成一串动作,并注明总代价。

变式题(先自己做)

(1) 改编自课件 p.9:起始盘面不变,目标盘面改成第一行 1 2 3,第二行 4 5 6,第三行「7 空格 8」。解是什么? (2) 改编自课件 p.10:旅行商问题有 7 个城市,不同环路有多少条? (3) 自编情境:一个算法每次从 Open 里挑「到目标的直线距离最短」的节点。它属于盲目搜索还是启发式搜索?为什么?

提示

(1) 这个目标盘面就在原来那三步的中途。(2) 代进 (n−1)!/2。(3) 回到分类的那一句判断标准。

判分点与答案(非官方评分标准)

判分点:① (1) 要写成动作序列,不能只画盘面;② (3) 要说出判断依据,不能只给类别。

(1) 「右、下」两步,代价 2。原来解的前两步走完,盘面正好是这个目标。

(2) (7−1)!/2 = 720/2 = 360 条。

(3) 启发式搜索。「到目标的直线距离」是一个离目标还有多远的估计,用了它挑节点就是启发式。

闪卡自测

1. 搜索问题的五要素是什么?「解」为什么不是目标状态?

当前状态、目标状态、动作、代价、解。目标状态通常一开始就给定了,要找的是怎么走过去,所以解是一条路径(p.4)。

2. 八数码的动作为什么写成空格在动?

这样每个状态最多只有上下左右 4 个动作,不用分别判断每个数字块怎么动(p.9)。

3. 状态图里的节点和边各代表什么?And 节点和 Or 节点怎么区分?

节点是状态,边是状态转移。几条边之间有弧线相连的是 And 节点,子路要全部完成;没有弧线的是 Or 节点,任选一条(p.8)。

4. 井字棋的生成测试要试多少种?算式是什么?

9! = 9×8×7×6×5×4×3×2×1 = 362,880 种(p.13)。

5. 盲目搜索和启发式搜索的分界线是什么?各举两个算法。

有没有用到离目标还有多远的估计。盲目:BFS、DFS;启发式:爬山法、最佳优先、A*(p.11、p.14)。

6. Open 表和 Close 表各存什么?

Open 存已经生成、还没展开的节点;Close 存已经展开过的节点,用来防止重复展开(p.18)。

7. 评价搜索算法的四个维度是什么?

完备性(有解一定找得到吗)、最优性(找到的是不是最好的)、时间(展开多少节点)、空间(同时存多少节点)(p.7)。

8. 本课件里 d、b、m 各代表什么?

d 是搜索树深度,b 是分支因子,m 是最浅解的深度,d 可以远大于 m(p.15)。

下一讲

问题摆好了,第一个找法是最规矩的 BFS:一层一层往外扫。见 L02a-2。

下一讲 →
L02a-2 L02a-2 BFS:像水波一样一圈一圈往外找

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