盲目搜索算法在状态空间中的应用

盲目搜索有时也称为非启发式搜索，不需要考虑与问题相关的信息，按照预定的方案采取类似穷举的方式进行蛮力搜索。由于它需要搜索所有可能的状态，当问题较复杂时，搜索的状态空间规模会非常巨大。比如，香农在1950年发表的论文Programming a Computer for Playing Chess中估计国际象棋的棋局搜索空间为10120，如果1μs搜索一步，则需要超过1090年才能搜索完，即便是用今天的计算机来计算，也是不现实的。书后参考文献9中给出了中国象棋状态总数的计算方法，得到的结论为1039.88，这也是一个非常庞大的数字。因此，盲目搜索一般只适用于比较简单的问题求解。

常用的两种盲目搜索方法是宽度优先搜索（BFS，breadth first search）和深度优先搜索（DFS，depth first search），这也是数据结构中图的遍历的两种基本算法。

宽度优先搜索也称为广度优先搜索或横向优先搜索，它从初始状态节点开始，逐层推进地搜索状态空间。例如，对图3.2所示的状态空间采用宽度优先搜索，从初始状态节点S开始，搜索到目标状态节点G，搜索的过程为：S，首先扩展出的是离S最近的第一层d，e，p，接着是从第一层扩展出来的第二层（分别是由d扩展出来的b，c，e，由e扩展出来的h，r和由p扩展出来的q），优先搜索兄弟节点，逐层推进，如图3.3所示。

图3.2　状态空间示例

(www.xing528.com)

图3.3　宽度优先搜索示例

深度优先搜索也称为纵向优先搜索，它从初始状态节点出发，向着节点纵深方向走到底，如果走到底还没搜索到目标状态节点，则回退到上一层，看看还有没有其他路径也就是兄弟节点，有则沿其他路径继续深入下去，否则继续回退，直到找到目标状态节点或者搜索完状态空间。如果对图3.2所示的状态空间进行深度优先搜索，则搜索过程为：S，S的第一个孩子节点d，d还有孩子节点，因此继续搜索d的孩子节点b、b的孩子节点a，搜索到a发现到底了，即a为叶子节点，于是回退到b，看看a是否还有兄弟节点，没有兄弟节点，于是继续回退到d，搜索b的兄弟节点c、c的孩子节点a，又回退，接下来将依次搜索e，h，p，q，q，r，f，c，a，G，如图3.4所示。

图3.4　深度优先搜索示例

下面将按图3.1所示流程图具体分析这两种搜索算法的实现过程并对两种算法的各自特点进行简要分析。