搜索算法 - Be Happy Every Day

概述#

这一讲讨论的是搜索。它在人工智能里非常基础，因为很多问题并没有现成的直接求解公式，往往只能把问题表示成一个状态空间，再通过某种策略在空间中寻找从初始状态到目标状态的路径。

先通过 TSP、八数码、AlphaGo 等例子说明：为什么人工智能需要搜索；
再回答搜索的几个基本问题：能不能找到解、找到的是不是最优解、代价多大、会不会陷入死循环；
然后引入这一讲最核心的表示框架：状态、操作算子、状态空间、状态空间图；
接着区分两大类搜索：
- 盲目搜索
- 启发式搜索
最后落到几种代表性方法：
- 回溯
- 宽度优先搜索
- 深度优先搜索
- A / A* 搜索

搜索 = 在状态空间中，按照某种策略选择下一个要扩展的状态。

搜索算法的应用#

为什么搜索重要?

可以抽象成同一个问题：

当前处于某个状态；
允许执行若干操作；
每执行一个操作，状态发生变化；
最终希望从初始状态到达目标状态。

也就是说，很多 AI 问题本质上都可以落到 在大量可能状态中找一条合适路径 。

Traveling Salesman Problem（TSP）#

给定若干城市和城市间距离；
要求从起点出发，经过所有城市各一次，再回到起点；
目标是使总路程最短。

它是一个经典的组合优化问题。

因为城市数增加后，可能路径数会以指数级 / 阶乘级增长，暴力枚举会迅速不可行。

TSP 的意义在于：它很好地展示了 搜索空间极大，无法穷举 这一现实。

八数码问题（Eight Puzzle）#

问题形式：

棋盘为 $3 \times 3$ ；
放有 8 个数字块和 1 个空格；
每次只能移动空格相邻的一个数字块；
目标是把初始局面变成目标局面。

它非常适合拿来说明：

什么是状态；
什么是操作算子；
什么是状态空间；
不同搜索策略会得到怎样不同的搜索树。

八数码也是后面讲 启发函数（heuristic function） 时的核心例子。

AlphaGo#

AlphaGo 说明了搜索在复杂问题中的真正价值。

围棋的棋盘是 $19 \times 19$ ，局面数量极其夸张

围棋可能局面数约为 $10^{170}$
宇宙原子数约为 $10^{80}$

这意味着：

即使最快的超级计算机；
也不可能靠穷举搜索所有局面。

因此，围棋程序若想变强，不能只靠多搜，而必须做到：

减少需要考虑的选择
优先考虑更有希望的选择

这就是 启发式搜索 的思想。

AlphaGo 的做法可以概括成：

用策略网络 预测下一步概率；
用价值网络 估计当前局面胜率；
再结合 MCTS（Monte Carlo Tree Search，蒙特卡洛树搜索） 做决策。

蒙特卡洛方法（Monte Carlo Method）#

它的核心思想是：

通过随机采样去估计一个不确定事件的可能结果。

价值：

不必把所有路径都系统展开完；
而是通过模拟、采样、统计来近似估计哪条路更有希望。

这类方法特别适合：

状态空间巨大；
无法完全穷举；
但允许做概率近似估计的问题。

AlphaGo 中的 MCTS 就是这一思想的代表。

搜索的基本概念#

搜索的定义#

求解一个问题，通常至少涉及两个方面：

表示
- 问题如何形式化表示；
- 如果表示不清楚，搜索就无从谈起。
求解方法
- 在这个表示基础上，用什么策略寻找解。

AI 中的常见问题求解方法包括：

搜索法
归约法
归结法
推理法
产生式系统

其中搜索之所以重要，是因为：

很多人工智能问题并没有现成的直接求解方法，而搜索是一种通用的问题求解框架。

搜索要解决的四个基本问题#

是否一定能找到一个解？
- 如果有解，能否保证最终找到？
- 还是可能一直兜圈子，甚至错过解？
找到的解是否是最佳解？
- 找到一个解，不代表就是最短路径或最小代价解；
- 有的算法只能保证找到某个解。
时间和空间复杂度如何？
- 要扩展多少节点？
- 要保存多少中间状态？
- 搜索空间会不会爆炸？
是否会终止，是否会陷入死循环？
- 会不会在图中反复绕；
- 会不会在有环状态空间里永远出不来。

这四个问题后面几乎可以用来评价所有搜索算法。

搜索的一般过程#

一个典型搜索过程可以写成：

从初始状态或目标状态出发，把它作为当前状态；
扫描操作算子集，找出当前状态下可用的操作；
将可用操作作用在当前状态上，生成新状态；
为新状态记录指向其父节点的指针；
检查这些新状态中是否有目标状态；
若有，则沿父指针反向回溯得到解路径；
若无，则继续从某个新状态出发进行搜索。

搜索的分类#

按搜索方向分

正向搜索
- 从初始状态出发；
- 顺着操作不断向前推。
逆向搜索
- 从目标状态出发；
- 反过来问：什么状态经过什么操作可以到达这里？
双向搜索
- 从初始状态和目标状态同时搜索；
- 当两边在中间相遇时得到解。

按是否使用额外信息分

盲目搜索
- 不利用具体问题领域知识；
- 只按固定规则扩展节点。
启发式搜索
- 利用问题领域中的经验或知识；
- 优先扩展更有希望的节点。

状态空间表示#

状态#

状态就是对系统当前情形的一种表示。

例如：

八数码中，一个状态就是 9 个格子的摆法；
TSP 中，一个状态可以表示当前已经访问了哪些城市、目前停在哪个城市。

操作算子#

操作算子表示：

从一个状态到另一个状态的合法变换。

例如在八数码中，空格的移动就是操作算子：

Up
Down
Left
Right

在积木世界中，操作算子可能是：

MOVE(X, Y)：把积木 X 搬到 Y 上面

操作算子本身通常带有先决条件，不是任何状态下都可执行。

状态空间（State Space）#

状态空间是一个四元组：

(S, O, S_0, G)

$S$ ：状态集合
$O$ ：操作算子集合
$S_0$ ：初始状态集合
$G$ ：目标状态描述

目标状态可以明确，也可以不那么明确
- 有时目标就是某个确定局面；
- 有时只要求满足某些性质。
状态空间是问题知识的表示方式
- 真正的搜索算法，是在这个表示之上运行的；
- 所以表示与求解必须分开看。

解路径#

从初始状态到目标状态的一条路径，称为求解路径。

一个解是一个有限的操作序列

o_1, o_2, \dots, o_k

使得初始状态经过这些操作后到达目标状态。

因此一个搜索问题的输出，通常不是一个数字答案，而是：

一串操作；
或者一条状态路径。

状态空间图#

状态空间通常可以画成一个有向图：

节点表示状态；
边表示操作算子导致的状态转移。

这是一种极其重要的理解方式，因为后面所有搜索算法，实际上都可以视为：

在状态空间图上以某种规则遍历节点。

八数码状态空间图

一个状态可以扩展出多个后继状态；
每条边对应一种空格移动。

TSP 状态空间图

根节点表示起点；
下一层表示选择第一站；
再下一层表示在剩余未访问城市中继续选择；
最后叶子结点对应一条完整回路。

盲目搜索策略#

盲目搜索不依赖问题领域知识，只依赖固定的节点扩展规则。

优点：

通用；
简洁；
理论分析清楚。

缺点：

在大状态空间中容易低效。

回溯策略#

回溯可以理解为一种 试错 + 撤销 策略。

它的工作方式是：

从初始状态开始，逐步构造解；
如果发现当前路径不符合条件，或无法继续走到目标；
就退回到最近的父节点；
再尝试另一条分支。

优点:

避免无脑穷举所有完整路径；
特别适合约束满足类问题。

局限:

本质上仍可能遍历大量无效分支；
若搜索树很深，代价仍然很高。

宽度优先搜索#

定义#

BFS 按照节点距离起始节点的深度，逐层扩展。

BFS 的重要性质#

完备性
- 如果存在解，BFS 一般能找到。
最短路径性质
- 如果每一步代价相同，则 BFS 找到的第一个解就是最短路径解。
- 这是 BFS 最关键的优点。
代价高
- BFS 要维护整层节点，因此：
  - 时间开销大
  - 空间开销也大

是一种 高价搜索 。

BFS 的积木例子#

初始状态：A 在 B 上，C 单独放在桌面；
目标状态：A、B、C 三块积木堆成一摞。

操作算子：

MOVE(X, Y)

表示把积木 $X$ 搬到 $Y$ 上面，其中 $Y$ 可以是积木，也可以是桌面。

先决条件：

被搬动积木 $X$ 顶部必须为空；
若 $Y$ 是积木，则 $Y$ 顶部也必须为空；
同一状态下，运用操作算子的次数不得多于一次。

深度优先搜索#

定义#

DFS 总是优先扩展最新产生的节点，也就是先沿一条路径一直往深处走。

优点:

所需存储通常较少；
不必像 BFS 一样保存整层所有节点。

局限:

不保证最短路径
- 第一次找到的解，不一定是最优解。
可能陷入很深但无效的分支
- 特别是在有大量深层无解分支时。
可能因环而死循环
- 若不做去重或深度限制，会很危险。

深度限制#

为了避免 DFS 无限往下钻，常常会加入深度限制：

只允许搜索到某个最大深度 $L$ ；
超过这个深度就停止。

这样虽然能避免死循环，但会引入新问题：

如果解在更深层，就可能找不到；
即使有解，也不一定找到最优解。

卒子穿阵

卒子只能前进，不能进敌兵区域；
假定深度限制值为 5；
DFS 在限制下可以找到解，但即使存在更优解，也未必能找到。

启发式搜索策略#

如果盲目搜索只依靠固定规则，那么启发式搜索则会利用额外信息来减少搜索量。

启发信息#

启发信息就是：

与具体问题领域相关、能够帮助缩小搜索范围的信息。

例如：

下棋时优先考虑更可能获胜的走法；
路径规划时优先走更靠近终点的方向。

启发式搜索的特点#

启发式搜索的核心不是生成不同的状态，而是：

对将要探索的节点排序，优先扩展最有希望的节点。

也就是说，搜索树还是那个搜索树，但扩展顺序变了。

而扩展顺序一变：

搜索代价可能大幅下降；
甚至原本不可做的大问题，也变得工程上可做。

启发式搜索的场景#

问题本身没有确定解例如医疗诊断：
- 数据不完备；
- 描述有模糊性；
- 只能寻找更可能正确的答案。
问题虽然有确定解，但状态空间太大例如：
- 一字棋状态很多；
- 国际象棋状态空间更夸张；
- 完全穷举在工程上不现实。

所以启发式搜索的目标:

用更少代价；
更快接近目标。

估价函数#

在启发式搜索里，最核心的工具是估价函数：

f(n)

它表示节点 $n$ 的希望程度。

f(n) = g(n) + h(n)

其中：

$g(n)$ ：从初始节点到 $n$ 的实际代价
$h(n)$ ：从 $n$ 到目标节点的估计代价
所以 $f(n)$ ：从起点经由 $n$ 到终点的总代价估计

于是：

只看 $g(n)$ ：像均匀代价 / 广搜那样，更保守；
只看 $h(n)$ ：像贪心搜索那样，更激进；
同时看两者：更平衡。

h(n) 权重大小的影响#

$h(n)$ 比重大：搜索工作量小，但可能找不到最优解；
$h(n)$ 比重小：搜索工作量增大，极端情况下退化为盲目搜索，但更可能找到最优解.

所以启发式搜索的关键平衡是：

效率 vs 最优性保证

八数码的启发函数例子#

1
2 1 3      1 2 3
2
7 6 4 ---> 8   4
3
  8 5      7 6 5

启发函数 1：不在位数 计算当前棋局与目标棋局相比，有多少个数码位置不对。

例如：

h(S_0)=5

这是最简单、最常见的启发函数之一。

启发函数 2：各数码到目标位置的距离总和 也就是常说的 Manhattan distance（曼哈顿距离） 思想。

例如：

h(S_0)=6

通常它比不在位数更细致。

启发函数 3：逆转数加权 对每一对逆转数码乘以某个倍数。

例如乘 3 倍，则：

h(S_0)=3

启发函数 4：组合启发函数 把不在位数和逆转数加起来。

例如：

h(S_0)=8

启发函数并不是唯一的；
好的启发函数设计，本身就是搜索算法的重要部分。

A 搜索#

定义#

A 搜索是一种基于估价函数的最佳优先搜索（best-first search）。

它按：

f(n)=g(n)+h(n)

对待扩展节点排序，每次扩展 $f(n)$ 最小的节点。

A 搜索的直觉#

$g(n)$ 太小但 $h(n)$ 很大：说明目前走得不远，但前景不好；
$h(n)$ 很小但 $g(n)$ 太大：说明虽然离目标近，但已经绕远；
$f(n)=g(n)+h(n)$ 是一种折中。

综合考虑已经付出的代价和未来估计代价。

八数码上的 A 搜索例子#

1
2 8 3      1 2 3
2
1 6 4 ---> 8   4
3
  7 5      7 6 5

$g(n)$ 取节点深度；
$h(n)$ 取与目标棋局不相同的位数（包括空格）。

例如起点：

f(S_0)=0+5=5

然后每扩展一个节点，都重新计算其 $f$ 值，并选择最小者继续。

最终得到解路径：

S \rightarrow A \rightarrow D \rightarrow H \rightarrow I \rightarrow K

步数为 5。

A 搜索的局限#

A 搜索能不能保证找到最优解？

答案是：不一定。

原因在于：

$h(n)$ 只是估计；
如果估计设计得不好，可能让某些看起来很有希望的节点被过早扩展；
从而先找到一个非最优解。

所以 A 搜索的性能强依赖启发函数。

A* 搜索#

A* 可以看成 A 搜索的优化版，也就是通常说的 最优的 A 算法 。

它依然使用：

f(n)=g^*(n)+h^*(n)

其中：

$g^*(n)>0$
$h^*(n)<= 任意h(n)$

A* 的基本结论#

如果某问题有解，并且启发函数满足相应条件，则：

A* 一定能找到解；
而且找到的是最优解。

A* 搜索算法是可采纳的。

可采纳性#

定义#

如果某搜索算法在最短路径存在时，能保证找到最短路径，则称为可采纳的。

A* 的性质#

A* 是可采纳的。

当 $h(n)=0$ 时，
A* 就退化成宽度优先搜索。

单调性#

单调性是对启发函数提出的更强要求。

若启发函数 $h(n)$ 满足：

对任意祖先状态 $n_i$ 和其后裔 $n_j$ ，有

h(n_i)-h(n_j)\le cost(n_i,n_j)

目标状态启发值为 0

则称该启发函数是单调的。

单调性的意义#

如果启发函数单调，则：

A* 搜索中，节点估价沿路径不会突然反常；
从祖先到后裔可以更稳定地沿最佳路径推进；
减少反复比较和路径调整的开销。

所以单调性不是 A* 正确性的唯一来源，但它能显著减少实现复杂度和搜索代价。

信息性#

若有两个启发函数 $h_1$ 与 $h_2$ ，对任意状态 $n$ 都有：

h_1(n) \le h_2(n)

则称 $h_2$ 比 $h_1$ 更有信息性（more informative）。

$h_2$ 更接近真实代价；
所以能更有效地区分哪些节点更值得扩展；
往往能减少搜索节点数。

WARNING
更有信息性不等于一定更划算，因为：

更复杂的启发函数本身计算也要花时间；

若计算成本太高，可能抵消掉减少节点数带来的收益。

这说明启发函数设计实际上是一个工程平衡问题。