[科普中国]-搜索策略

状态空间的—般搜索过程

问题求解过程实际上是一个搜索过程。为了进行搜索，首先必须把问题用某种形式表示出来，其表示是否适当，将直接影响搜索效率。对一个确定的问题来说，与解题有关的状态空间往往只是整个状态空间的一部分。只要能生成并存储这部分状态空间，就可求得问题的解。在人工智能中通过运用搜索技术解决此问题的基本思想是：首先把问题的初始状态（即初始节点）作为当前状态，选择适用的算符对其进行操作，生成一组子状态（或后继状态、后继节点、子节点），然后检查目标状态是否在其中出现。若出现，则搜索成功，找到了问题的解；若不出现，则按某种搜索策略从已生成的状态中再选一个状态作为当前状态。重复上述过程，直到目标状态出现或者不再有可供操作的状态及算符时为止。

在搜索过程中，要建立两个数据结构：OPEN表和 CLOSED表， OPEN表用于存放刚生成的节点，对不同的策略，节点在此表中的排列顺序是不同的。例如对宽度优先搜索，是将扩展节点n的子节点放入到OPEN表的尾部，而深度优先搜索是把节点的子节点放入到OPEN表的首部。CLOSED表用于存放将要扩展或已扩展的节点（节点n的子节点）。所谓对一个节点进行扩展，是指用合适的算符对该节点进行操作，生成一组子节点。一个节点经一个算符操作后一般只生成一个子节点，但对一个可适用的算符可能有多个，故此时会生成一组子节点。需要注意的是：在这些子节点中，可能有些是当前扩展节点（即节点n）的父节点、祖父节点等，此时不能把这些先辈节点作为当前扩展节点的子节点。

搜索的一般过程如下：

（1）把初始节点S0放入OPEN表中，并建立目前只包含S0的搜索图G。

（2）检查OPEN表是否为空，若为空则问题无解，退出；否则进行下一步。

（3）把OPEN表的第一个节点取出放入CLODED表中，并记该节点为节点n。

（4）考虑节点n是否为目标节点，若是，则求得了问题的解，退出，此解可从目标节点开始直到初始节点的返回指针中得到；否则，继续下一步。

（5）扩展节点n，若没有后继节点，则立即转步骤（2）；否则生成一组子节点。把其中不是节点n先辈的那些子节点记作集合M={mi}，并把这些子节点mi作为节点n的子节点加入G中。

（6）针对M中子节点mi的不同情况，分别进行如下处理：对于那些未曾在G中出现过的mi设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表中。对于那些先前已在G中出现过的mi，确定是否需要修改它指向父节点的指针。对于那些先前已在G中出现并且已经扩展了的mi，确定是否需要修改其后继节点指向父节点的指针。

（7）按某种搜索策略对OPEN表中的节点进行排序。

（8）返回至第（2）步。

宽度优先搜索策略宽度优先搜索的基本思想是：从初始节点S0开始，逐层地对节点进行扩展并考察它是否为目标节点，在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。OPEN表中的节点总是按进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。其搜索过程如下。

（1）把初始节点S0放入OPEN表中。

（2）若OPEN表为空，则问题无解，退出。

（3）把OPEN表的第一个节点（记为节点n）取出放入CLOSED表中。

（4）考察节点n是否为目标节点，若是，则问题解求得，退出。

（5）若节点n不可扩展，则转步骤（2）。

（6）扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点配置指向父节点的指针，然后转步骤（2）。

深度优先搜索策略深度优先搜索的基本思想是：从初始节点S0开始扩展，若没有得到目标节点，则选择最后产生的子节点进行扩展，若还是不能到达目标节点，则再对刚才最后产生的子节点进行扩展，一直如此向下搜索。当到达某个子节点，且该子节点既不是目标节点又不能继续扩展时，才选择其兄弟节点进行考察。其搜索过程如下：

（1）初始节点S0放入OPEN表中。

（2）若OPEN表为空，则问题无解，退出。

（3）把OPEN表的第一个节点（记为节点n）取出放入CLOSED表中。

（4）考察节点n是否为目标节点，若是，则问题解求得，退出。

（5）若节点n不可扩展，则转步骤（2）。

（6）扩展节点n，将其子节点放入OPEN表的首部，并为其配置指向父节点的指针，然后转步骤（2）。

该过程与宽度优先搜索的惟一区别是：宽度优先搜索时将节点n的子节点放入到OPEN表的尾部，而深度优先搜索时把节点n的子节点放入到OPEN表的首部。仅此一点不同，就使得搜索的路线完全不一样。1

启发式搜索策略上述各种搜索策略的一个共同特点是它们的搜索路线是事先决定好的，没有利用被求解问题的任何特征信息，在决定要被扩展的节点时，没有考虑该节点到底是否可能出现在解的路径上，也没有考虑它是否有利于问题的求解以及所求的解是否为最优解，因而这样的搜索策略都具有较大的盲目性。盲目搜索所需扩展的节点数目很大，产生的无用节点肯定就很多，效率就会较低。启发式搜索法的基本思想是在搜索路径的控制信息中增加关于被解问题的某些特征，用于指导搜索向最有希望到达目标结点的方向前进。它一般只要知道问题的部分状态空间就可以求解该问题，搜索效率较高。2