搜索策略

搜索是人工智能中的一个核心技术，是推理不可分割的一部分，它直接关系到智能系统的性能和运行效率。搜索问题中，主要的工作是找到正确的搜索策略。搜索策略反映了状态空间或问题空间扩展的方法，也决定了状态或问题的访问顺序。搜索策略的不同，人工智能中的搜索问题的命名也不同。

过程

状态空间的—般搜索过程

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

在搜索过程中，要建立两个数据结构：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）。

启发式搜索策略