1.3　盲目搜索

搜索算法的基本思路是：为初始状态生产初始节点，并将该节点放到某种存储数据结构里，然后根据某种策略从存储结构中选择并移除一个节点，判读如果这个节点的状态是目标节点，返回成功，否则根据该节点的状态的动作集合，生产相应的后继节点集合并放入存储结构中。然后重复以上过程，直到成功或结束。不同的搜索算法可能使用不同的存储数据结构和节点选择策略。每个节点都包含相应的状态、父节点信息、以及从父节点状态到该节点状态的动作。注意，根据到达的路径不同，一个状态可能会生产不同的节点。本节将介绍盲目搜索策略（也称无信息搜索）。盲目搜索（blind search）是指在搜索中没有使用除了问题定义以外的额外信息。我们将以地图路径搜索问题为例，介绍两种盲目搜索的方式，深度优先搜索（depth-first search，DFS）和宽度优先搜索（breadth-first search，BFS）。

1.3.1　深度优先搜索

深度优先搜索是一种典型的盲目搜索，它每次优先对当前能够到达的最深的节点进行搜索。如果当前节点的所有边都已经被探索过，则算法不断向当前节点的父节点回溯，一直进行到发现目标节点或从源节点可达的所有节点为止；若此时还有未被搜索过的节点（意味着问题存在不连通的节点），则选择其中一个未被搜索的节点作为源节点并重复以上过程；重复整个过程直到发现目标节点或所有节点都被访问为止。

深度优先搜索算法的伪代码如下：

算法1：深度优先搜索算法

下面以图1.3中的地图搜索问题为例，具体说明深度优先算法的执行过程。在此问题中，假设初始节点为A，目标节点为T。图1.7给出了该算法执行过程中对应搜索的变化。

初始化时，栈为空Z={}，访问表为空V={}。算法执行过程如下：

（1）初始节点A放入栈Z，Z={A}。

（2）栈Z不为空，继续执行。弹出栈顶节点A，且A不是目标、不在访问表中。扩展A，其后继集合为N={X}。将A放入访问表V={A}。将N中的节点放入栈Z={X}。对应图1.7（1）。

（3）栈Z不为空，继续执行。弹出栈顶节点X，且X不是目标、不在访问表中。扩展X，其后继集合为N={C，B}。将X放入访问表V={A，X}。将N中的节点放入栈Z={B，C}。对应图1.7（2）。

（4）栈Z不为空，继续执行。弹出栈顶节点C，且C不是目标、不在访问表中。扩展C，其后继集合为N={L，W}。将C放入访问表V={A，X，C}。将N中的节点放入栈Z={B，W，L}。对应图1.7（3）。

（5）栈Z不为空，继续执行。弹出栈顶节点L，且L不是目标、不在访问表中。L无后继节点，将L放入访问表V={A，X，C，L}。栈Z={B，W}。对应图1.7（4）。

（6）栈Z不为空，继续执行。弹出栈顶节点W，且W不是目标、不在访问表中。扩展W，其后继集合为N={K，T，B}。将W放入访问表V={A，X，C，L，W}。将N中的节点放入栈Z={B，B，T，K}。对应图1.7（5）。

（7）栈Z不为空，继续执行。弹出栈顶节点K，且K不是目标、不在访问表中。K无后继节点，将K放入访问表V={A，X，C，L，W，K}。栈Z={B，B，T}。对应图1.7（6）。

（8）栈Z不为空，继续执行。弹出栈顶节点T，为目标节点，结束搜索。此时访问表为V={A，X，C，L，W，K，T}。对应图1.7（7）。

深度优先搜索是一种通用的且与问题无关的方法，深度对优先搜索的实现可以不使用访问表。虽然这样实现可能会重复展开某些状态，但是其优点在于节省内存，只需要存储从初始节点到当前节点的路径上的节点以及它们的后继节点；缺点是对于无限状态空间，如果进入了一条无限又无法到达目标节点的路径，深度优先搜索会进入死循环而失败。

1.3.2　宽度优先搜索

宽度优先搜索从根节点开始，按照层次由浅入深的方式逐层扩展节点进行搜索，直至找到目标节点。

宽度优先搜索的伪代码如下：

算法2：宽度优先搜索算法

这里仍以图1.3中的地图搜索为例，说明深度优先搜索的执行过程。假设初始节点为A，目标节点为S。图1.8给出了算法执行过程中搜索树的变化。

初始化时，队列为空Q={}，访问表为空V={}。算法执行过程如下：

（1）将初始节点A放入队列得到Q={A}。

（2）队列Q不为空，继续执行。弹出队首节点A，且A不是目标、不在访问表中。扩展A，其后继集合为N={X}。将A放入访问表得到V={A}。将N中的节点放入队列得到Q={C，B}。对应图1.8（1）。

（3）队列Q不为空，继续执行。弹出队首节点X，且X不是目标、不在访问表中。扩展X，其后继集合为N={C，B}。将X放入访问表得到V={A，X}。将N中的节点放入队列Q={C，B}。对应图1.8（2）。

（4）队列Q不为空，继续执行。弹出队首节点{C，B}（实际程序执行，每次只弹出一个，先弹出C再弹出B，此处为了表达简洁将同一父节点的节点同时弹出），且{C，B}不是目标、不在访问表中。依次扩展{C，B}，其后继集合为N={L，W，T，S}。将{C，B}放入访问表得到V={A，X，C，B}。将N中的节点放入队列得到Q={L，W，T，S}。对应图1.8（3）。

（5）队列Q不为空，继续执行。弹出队首节点{L，W}（L，W来自同一父节点C），且{L，W}不是目标、不在访问表中。依次扩展{L，W}，L无后继节点，W后继节点为{K，T，B}，从而后继集合为N={K，T，B}。将{L，W}放入访问表得到V={A，X，C，B，L，W}。将N中的节点放入队列得到Q={T，S，K，T，B}。对应图1.8（4）。

（6）队列Q不为空，继续执行。弹出队首节点{T，S}（T，S来自同一父节点B），S为目标节点，结束搜索。此时访问表V={A，X，C，B，L，W，S}。对应图1.8（5）。

可以看到当扩展到深度为4的节点时，便找到了从起点到终点的路径。与深度优先搜索类似，宽度优先搜索方法与问题无关，具有通用性。其优点是不存在死循环的问题，当问题有解的时候，一定能找到解。然而，在搜索过程中，宽度优先搜索需要将下一层的节点放到队列中待展开，而每层的节点个数随着层数成指数增长，所以它的缺点在于算法所需的存储量比较大。另外，深度优先搜索和宽度优先搜索均会构建搜索树，其不同之处在于扩展节点的顺序不同。