文档介绍：组合爆炸问题
对那些结构性能较好,理论上有算法可依的问题,如果问题或算法的复杂性较高(如按指数形式增长),由于受计算机在时间和空间上的限制,也无法付诸实用。
例如,64阶梵塔问题有3,433,683,820,292,512,484,657,849,089,281状态,仅从空间上来看,这是一个任何计算机都无法存储的问题。可见,理论上有算法的问题实际上不一定可解。像这类问题,也需要采用搜索的方法来进行求解。
信息工程学院 2009年4月10日
状态空间的盲目搜索
状态空间的搜索策略可分为盲目搜索和启发式搜索两大类。尽管盲目搜索的性能不如启发式搜索,但由于启发式搜索需要抽取与问题本身有关的特征信息,而这种特征信息的抽取往往又比较困难,因此盲目搜索仍不失为一种有用的搜索策略。
一般图搜索过程
当用状态空间法解决问题时,有以下两个方面的因素需要考虑:一方面,对大问题计算机无法保存其全部状态空间;另一方面,对具体问题与解有关的状态空间一般仅是全部状态空间的一部分。解决这一问题的方法是采用状态空间搜索技术。
信息工程学院 2009年4月10日
广度优先搜索
广度优先搜索也称为宽度优先搜索,它是一种先生成的节点先扩展的策略。这种搜索策略的搜索过程是:从初始节点S0开始逐层向下扩展,在第n层节点还没有全部搜索完之前,不进入第n+1层节点的搜索。Open表中的节点总是按进入的先后排序,先进入Open表的节点排在前面,后进入Open表的节点排在后面。
广度优先搜索算法如下:(用QUEUE)
(1) 把初始节点S0放入Open表中;
(2) 如果Open表为空,则问题无解,失败退出;
(3) 把Open表的第一个节点取出放入Closed表,并记该节点为n;
(4) 考察节点n是否为目标节点。若是,则得到问题的解,成功退出;
(5) 若节点n不可扩展,则转第(2)步;
(6) 扩展节点n,将其子节点放入Open表的尾部,并为每一个子节点设置指向父节点的指针,然后转第(2)步。
信息工程学院 2009年4月10日
应用实例
八数码难题。在3×3的方格棋盘上,分别放置了标有数字1、2、3、4、5、6、7、8的八张牌,初始状态S0,目标状态Sg,如图5-11所示。可以使用的操作有:空格左移,空格上移,空格右移,空格下移。即只允许把位于空格左、上、右、下方的牌移入空格。要求应用广度优先搜索策略寻找从初始状态到目标状态的解路径。
(定义距离函数,评价每张与目标的距离)
信息工程学院 2009年4月10日
解:应用广度优先搜索策略,可以在第四级得到解,其搜索树如图5-12所示。
由图5-12可以看出,解的路径是
S0→3→8→16→26
优点:广度优先搜索是一种完备策略,即只要问题有解,它就一定可以找到解。并且,广度优先搜索找到的解,还一定是路径最短的解。
缺点:主要缺点是盲目性较大,尤其是当目标节点距初始节点较远时,将产生许多无用的节点,因此其搜索效率较低。
信息工程学院 2009年4月10日
信息工程学院 2009年4月10日
深度优先搜索(用STACK)
深度优先搜索是一种后生成的节点先扩展的策略。这种搜索策略的搜索过程是:从初始节点S0开始,在其子节点中选择一个最新生成的节点进行考察,如果该子节点不是目标节点且可以扩展,则扩展该子节点,然后再在此子节点的子节点中选择一个最新生成的节点进行考察,依此向下搜索,直到某个子节点既不是目标节点,又不能继续扩展时,才选择其兄弟节点进行考察。Open表是一种栈结构,最先进入的节点排在最后面(压在最下面),最后进入的节点排在最前面。
深度优先搜索算法如下:
(1) 把初始节点S0放入Open表中;
(2) 如果Open表为空,则问题无解,失败退出;
(3) 把Open表的第一个节点取出放入Closed表,并记该节点为n;(栈顶元素)
信息工程学院 2009年4月10日
(4) 考察节点n是否为目标节点。若是,则得到问题的解,成功退出;
(5) 若节点n不可扩展,则转第(2)步;
(6) 扩展节点n,将其子节点放入Open表的首部,并为每一个子节点设置指向父节点的指针,然后转第(2)步。
从以上过程可以看出,深度优先搜索和广度优先搜索的唯一区别是节点在Open表中的排列顺序不同。广度优先搜索是把最新生成的节点放在Open表的尾部(用队列实现),而深度优先搜索则是把最新生成的节点放在Open表的首部(用堆栈实现)。
信息工程学院 2009年4月10日
八数码难题。要求用深度优先搜索策略寻找从初始状态到目标状态的解路径。
解:应用广度优先搜索策略,其部分搜索树如图5-14所示。在图5-14