下载文档原格式
状态空间的搜索策略图1 状态空间的搜索策略一般说来，搜索策略讨论对于具有树状结构图的问题状态空间更加方便。
因此，对于非树状结构图的问题，例如网状结构等，往往需要化为树状结构图，以便更好地应用搜索策略进行讨论。
（1）广度优先搜索——先进先出，生成的节点插入OPEN表的后面。
基本方法：从根节点S0开始，向下逐层逐个地对节点进行扩展与穷尽搜索，并逐层逐个地考察所搜索节点是否满足目标节点Sg的条件。
若到达目标节点Sg，则搜索成功，搜索过程可以终止。
注意：在广度优先搜索法的过程中，同一层的节点搜索次序可以任意；但在第n层的节点没有全部扩展并考察之前，不应对第n+1层的节点进行扩展和考察。
特点：显然，宽度优先搜索法是一种遵循规则的盲目性搜索，它遍访了目标节点前的每一层次每一个节点，即检查了目标节点前的全部的状态空间点，只要问题有解，它就能最终找到解，且最先得到的将是最小深度的解。
可见，宽度优先搜索法很可靠。
但是，当目标节点距离初始节点较远时将会产生许多无用的中间节点。
因此，速度慢，效率低，尤其对于庞大的状态空间实用价值差。
（2）深度优先搜索——后进先出，生成的节点插入OPEN表的前面。
基本方法：从根节点S0开始，始终沿着纵深方向搜索，总是在其后继子节点中选择一节点来考察。
若到达目标节点Sg，则搜索成功；若不是目标节点，则再在该节点的后继子节点中选一考察，一直如此向下搜索，直到搜索找到目标节点才停下来。
若到达某个子节点时，发现该节点既不是目标节点又不能继续扩展，就选择其兄弟节点再进行考察。
依此类推，直到找到目标节点或全部节点考察完毕，搜索过程才可以终止或结束。
特点：方式灵活，规则易于实现，对于有限状态空间并有解时，必能找到解。
例如，当搜索到某个分支时，若目标节点恰好在此分支上，则可较快地得到解。
故在一定条件下，可实现较高求解效率。
但是，在深度优先搜索中，一旦搜索进入某个分支，就将沿着该分支一直向下搜索。
这时，如果目标节点不在此分支上，而该分支又是一个无穷分支，则就不可能得到解。
