目录

第3章 搜索问题求解

3.1 引言

3.2 搜索问题

3.1.1 智力游戏问题

3.1.2 现实世界问题

3.3 搜索问题的要素

3.3.1 状态表征

3.3.2 状态空间

3.3.3 形式化

3.3.4 求解的方法

3.4 搜索问题的实例化

3.4.1 八数码难题

3.4.2 八皇后难题

3.4.3 传教士和食人族问题

3.4.4 最短路径问题

3.5 搜索求解的方式

3.5.1 树搜索

3.5.2 图搜索

3.6 无信息搜索

3.6.1 宽度优先搜索

3.6.2 深度优先搜索

3.6.3 迭代深化搜索

 3.7 有信息搜索

3.7.1 统一代价搜索

3.7.2 贪婪最佳优先搜索

3.7.3 ​搜索

3.8 小结

---

第3章 搜索问题求解

3.1 引言

有这样一类问题：具有初始状态和目标状态，每个状态可以看作一个黑盒子，其状态空间能够表示为一棵树或一张图，这类问题的求解是通过搜索找到一个从初始状态到目标状态的最短路径，而无法用传统的数学方法进行求解。

这类问题称为搜索问题，其求解过程是搜索。

3.2 搜索问题

3.1.1 智力游戏问题

很多智力游戏问题被作为人工智能搜索问题求解的经典实例。

例3.1 八数码难题（8-puzzle）

例3.2 八皇后难题（eight queens puzzle）

例3.3 传教士和食人族（missionaries and cannibals）

3.1.2 现实世界问题

例3.4 最短路径问题（shortest path problem）

3.3 搜索问题的要素

搜索问题与状态和状态空间有关，搜索问题的求解需要对问题进行形式化，其中涉及状态如何表征。

3.3.1 状态表征

状态是问题在不同时期或不同条件下所表现出的形态。问题提出时的状态称为初始状态，问题达到预期结果时的状态为目标状态，其他为中间状态。搜索问题中状态的表征主要采用原子式表征。

3.3.2 状态空间

状态空间是问题在不同时期或不同条件下所表现出的所有状态的有机组成，通常可以抽象为一张图或一棵树。

3.3.3 形式化

一个问题，若可以将其表示成状态空间、并且在初始状态和目标状态之间可能存在多条路径的话，就称其为搜索问题。

智能主体搜索的目的是从初始节点至目标节点之间找到一条代价最低的路径。

一个搜索问题可以形式化为一个5元组，即：。

3.3.4 求解的方法

搜索问题的解是一个从初始状态到达目标状态的路径，搜索问题的求解就是智能主体寻找该路径的动作。

3.4 搜索问题的实例化

3.4.1 八数码难题

3.4.2 八皇后难题

3.4.3 传教士和食人族问题

3.4.4 最短路径问题

3.5 搜索求解的方式

3.5.1 树搜索

以下图为例，设起点是A，终点是M。下面讨论如何将搜索过程表示为一棵树并通过树搜索方式来求解。

 这里给出一个通用的树搜索算法，见算法3.2。

3.5.2 图搜索

3.6 无信息搜索

无信息搜索指的是搜索过程中除了问题本身之外没有任何其他信息，其过程只关心搜索的步骤，每搜索一步所做的只是生成后继并判断是否是目标节点。

无信息搜索也被称为盲目搜索、蛮力搜索或穷举搜索。

3.6.1 宽度优先搜索

宽度优先搜索也被翻译成广度优先搜索或先宽搜索。

宽度优先搜索是针对树结构或图结构的遍历搜索算法，其策略是扩展最浅的未扩展节点。所谓最浅，是相对于当前节点而言。

实现宽度优先搜索的方法是采用先进先出队列，即每次将扩展的后继节点放在队列的后面。

3.6.2 深度优先搜索

深度优先搜索是针对树结构或图结构的遍历搜索算法。其策略是扩展最深的未扩展节点。它与宽度优先搜索的不同之处在于，后者是扩展最浅的未扩展节点。

对于树结构而言，深度优先搜索从根节点开始，沿着一个分支，一直搜索到叶节点，然后回溯。实现深度优先搜索的方法是采用后进先出队列，即每次将扩展的后继节点放在队列的前面，在数据结构中，LIFO队列被称为堆栈。

3.6.3 迭代深化搜索

对于深度优先搜索来说，如果遇到一颗深度无限的树，就会沿着某一侧的分支一直搜索下去。这个问题可以用预先设定的深度限制l加以解决，位于深度l的结点被视为叶节点。这种方法被称为深度受限搜索，也被称为深度受限深度优先搜索。

迭代深化搜索将深度优先和宽度优先的优势相结合，逐步增加深度限制l，直到找到目标为止。在每次迭代内部，它以深度优先搜索的顺序遍历搜索树的节点；但在迭代之间，其顺序相当于宽度优先。迭代深化搜索也被称为迭代深化深度优先搜索。

 3.7 有信息搜索

有信息搜索，是在搜索过程中依据问题提供的特有信息或动态生成的有用信息，用以引导其搜索策略沿着有希望的搜索路径尽快找到目标。

与无信息搜索不同，有信息搜索生成一个评价函数，用于搜索的代价估计，具有最低代价的节点被优先扩展。

有信息搜索可以分为如下三种情况：

    

有信息搜索可以看做是最佳优先搜索，就是说，这类搜索算法依据所得到的的信息，按既定的“最佳优先”策略进行搜索。

3.7.1 统一代价搜索

统一代价搜索是一种树搜索算法，它在扩展节点时根据问题提供的每段路径代价，寻找一条从起始节点至目标的代价最低的路径。

3.7.2 贪婪最佳优先搜索

贪婪最佳优先搜索的策略是试图扩展最接近目标的节点，这也是贪婪名称的由来。

3.7.3 搜索

搜索的策略是路径代价与启发式函数这两者兼顾的搜索，可以看作是统一代价优先和贪婪最佳优先搜索这两者结合的产物。

3.8 小结

本章在介绍几种智力游戏问题和现实世界的问题之后，论述了搜索问题的要素及其形式化方法。

搜索空间可以表示为树或图的结构，与其对应的搜索求解方式就是树搜索和图搜索。

根据搜索过程总是否具有问题提供的特定信息来生成评价函数，又分为无信息搜索和有信息搜索。

无信息搜索也被称为盲目搜索、蛮力搜索或穷举搜索。代表性的搜索策略包括宽度优先、深度优先以及迭代深化搜索。

有信息搜索可看做是最佳优先搜索，包括统一代价搜索、贪婪搜索、搜索以及迭代深化搜索等。