[科普中国]-盲目搜索

宽度优先搜索

宽度优先搜索又称广度优先搜索。其基本思想是：从初始节点S0开始进行节点扩展，考察S0的第1个子节点是否为目标节点，若不是目标节点，则对该节点进行扩展；再考察S0的第2个子节点是否为目标节点，若不是目标节点，则对其进行扩展；对S0的所有子节点全部考察并扩展以后，再分别对S0的所有子节点的子节点进行考察并扩展，如此向下搜索，直到发现目标状态Sg为止。因此，宽度优先搜索在对第n层的节点没有全部考察并扩展之前，不对第n+1层的节点进行考察和扩展。

以九宫问题为例，对初始节点S0进行扩展，有四种操作有效，产生四个子节点S1、S2、S3、S4。对节点S1考察发现它不是目标节点，应对其扩展。节点S1有三种有效操作，但其中空格右移得到的状态是其父节点的状态，因此此状态无效，即S1节点仅有2个子节点S5、S6；对节点S2考察，同样只能生成2个子节点S7、S8；依次类推，可产生如右图的搜索树。

宽度优先搜索的盲目性较大，当目标节点离初始节点较远时，将会产生许多无用节点，搜索效率低，这是它的缺点。但是，只要问题有解，用宽度优先搜索总可以得到解，而且得到的解是路径最短的，这是它的优点。所以，宽度优先搜索是完备的搜索。

深度优先搜索深度优先搜索的基本思想是：从初始节点S0开始进行节点扩展，考察S0扩展的最后1个子节点是否为目标节点，若不是目标节点，则对该节点进行扩展；然后再对其扩展节点中的最后1个子节点进行考察，若又不是目标节点，则对其进行扩展，一直如此向下扩展。当发现节点本身不能扩展时，对其1个兄弟节点进行扩展；如果所有的兄弟节点都不能够扩展时，则寻找到它们的父节点，对父节点的兄弟节点进行扩展；依次类推，直到发现目标状态Sg为止。因此，深度优先搜索法存在搜索和回溯交替出现的现象。

同样，以九宫问题为例，对初始节点S0进行扩展，有四种操作有效，产生S1、S2、S3、S4四个节点。先对节点S4考察发现它不是目标节点，应对其进行扩展，但其中空格上移得到的状态是其父节点的状态，因此此状态无效，即S4节点仅有2个子节点S5、S6；对节点S6进行考察发现不是目标节点，则进行扩展，得到S6的子节点S7；依次类推，可产生如右图的搜索树。

在深度优先搜索中，搜索一旦进入某个分支，就将沿着该分支一直向下搜索。如果目标节点恰好在此分支上，则可较快地得到问题解。但若目标节点不在该分支上，且该分支又是一个无穷分支，就不可能得到解。所以，深度优先搜索是不完备的搜索。

迭代加深搜索为克服深度优先搜索陷入无穷分支死循环的问题，提出了有界深度优先搜索方法。有界深度搜索的基本思想是：预先设定搜索深度的界限，当搜索深度到达了深度界限而尚未出现目标节点时，就换一个分支进行搜索。

在有界深度搜索策略中，深度限制d是一个很重要的参数。当问题有解，且解的路径长度小于或等于d时，则搜索过程一定能找到解。但是，这不能保证最先找到的是最优解，此时深度搜索是完备而非最优的。如d取得太小，解的路径长度大于d，则在搜索过程中就找不到解，此时搜索过程不完备。但是，深度限制d不能太大，否则会产生过多的无用节点。为了解决深度限制d的设置，可以采用这样的方法：先任意给定一个较小的深度限制，然后按有界深度搜索，如在此深度找到解，则结束；否则，增大深度限制，继续搜索。此种搜索方法称为迭代加深搜索。2