目搜索
盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。
我们将学习的宽度优先搜索和深度优先搜索，属于盲目搜索方法。
一、宽度优先搜索
回顾上一节的寻找寿命为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尽可能小。
对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径（防止搜索过程沿着无益的路径扩展下去），往往给出一个节点扩展的最大深度——深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说
图 3-2-8 等代价搜索算法框图
