目搜索

盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。

我们将学习的宽度优先搜索和深度优先搜索，属于盲目搜索方法。

一、宽度优先搜索

回顾上一节的寻找寿命为X的人的例子，如果搜索时，从节点A开始，对他的三个儿子按从左至右搜索，然后对他的所有孙子按从左至右搜索，依此下去。这种搜索方式就是宽度优先搜索。

宽度优先搜索(breadth-first

search)的定义：如果搜索是以接近起始节点的 程度依次扩展节点的，那么

这种搜索就叫做 宽度优先搜索(breadth-first

search)，如图3-2-1所示。

图3-2-1 宽度优先搜索示意图

从图可见，这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。

宽度优先搜索算法如下：

(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。

(2) 如果OPEN是个空表，则没有解，失败退出；否则继续。

(3) 把第一个节点(节点

n)从OPEN表移出，并把它放入CLOSED扩展节点表中。

(4) 扩展节点n。如果没有后继节点，则转向上述第(2)步。

(5) 把n

的所有后继节点放到OPEN表的末端，并提供从这些后继节点回到n的指针。

(6) 如果n

的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。

算法见图3-2-2：

　

图3-2-2 宽度优先算法框图

宽度优先搜索方法分析：

宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第6步，这实际是将OPEN表作为“先进先出”的队列进行操作。

宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，我们就说该法

失败 退出；对于 无限图来说，则永远不会终止)。

例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：

宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有限图来说，我们就说该法

失败 退出；对于 无限图来说，则永远不会终止)。

例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如图3-2-3、所示的目标棋局问题：

１

２

×

８

３

４

７

６

５

图 3-2-3 八数码难题的初始棋局

图3-2-4

八数码难题的宽度优先搜索树(图3-2-3对应图)

搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序(按顺时针方向移动空格)。图中最后一个节点是目标节点。

二、深度优先搜索

另一种盲目(无信息)搜索叫做深度优先搜索(depth-first

search)。图3-2-5是一个深度优先搜索示意图。

图3-2-5 深度优先搜索的示意图

分析深度优先搜索示意图可看出，在深度优先搜索中，我们首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。

我们定义节点的深度如下：

(1) 起始节点(即根节点)的深度为0。

(2)任何其它节点的深度等于其父辈节点深度加上1。

首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。替代路径与前面已经试过的路径不同之处仅仅在于改变最后n步，而且保持n尽可能小。

对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度——深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使应用了深度界限的

规定，所求得的解答路径并不一定就是最短的路径。

含有深度界限的深度优先搜索算法如下：

(1)把起始节点Ｓ放到未扩展节点OPEN表中。如果此节点为一目标节点，则得到一个解。

(2) 如果OPEN为一空表，则失败退出。

(3)把第一个节点(节点n)从OPEN表移到CLOSED表。

(4)如果节点n的深度等于最大深度，则转向(2)。

(5) 扩展节点n

，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向(2)。

(6)如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向(2)。

算法如图3-2-6所示:

图3-2-6 有界深度优先搜索算法图

例：按深度优先搜索生成的八数码难题搜索树，我们设置深度界限为5。

图3-2-7

绘出了搜索树，粗线条的路径表明含有5条应用规则的一个解。从图可见，深度优先搜索过程是沿着一条路径进行下去，直到深度界限为止，然后再考虑只有最后一步有差别的相同深度或较浅深度可供选择的路径，接着再考虑最后两步有差别的那些路径，等等。

图3-2-7 八数码难题的深度优先搜索树

三、等代价搜索

有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性的解。搜索树中每条连接弧线上的有关代价以及随之而求得的具有最小代价的解答路径，与许多这样的广义准则相符合。宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。

有如下一些记号：

起始节点记为S；

从节点i到它的后继节点j的连接弧线代价记为c(i,j)；

从起始节点S到任一节点i的路径代价记为g(i)。在搜索树上，我们假设g(i)也是从起始节点S到节点i的最少代价路径上的代价，因为它是唯一的路径；

等代价搜索算法：

等代价搜索方法以g(i)的递增顺序扩展其节点，其算法如下：

(1)把起始节点Ｓ放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求得一个解；否则令g(S)=0。

(2) 如果OPEN是个空表，则没有解而失败退出。

(3) 从OPEN

表中选择一个节点i，使其g(i)为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点

i(要是有目标节点的话)；否则，就从中选一个作为节点i。把节点i从OPEN表移至扩展节点表CLOSED中。

(4) 如果节点i为目标节点，则求得一个解。

(5) 扩展节点i。如果没有后继节点，则转向第(2)步。

(6)对于节点i的每个后继节点j，计算g(j)=g(i)+c(i,j)，并把所有后继节点j放进OPEN表。提供回到节点i的指针。

(7) 转向第(2)步。

对应图3-2-8:

图 3-2-8 等代价搜索算法框图