广度优先搜索能够保证找到步数最少的解,但是它可能需要评价规模相当大的移动序列。深度优先搜索试着在每次搜索时能够前进更多步,它可能能够快速得到一个解,但是它也可能在搜索树的某个部分浪费大量的时间,尽管看起来这个部分不可能得到解。
我们认为比较深度优先搜索,广度优先搜索和A*搜索是值得的。使用八数码问题作为样例,我们通过随机移动n个方块(n从2、4、8和16开始),注意同样的方块不会在一行中移动两次,因为这就等于什么也没做。当n≥32时,内存耗尽。对于每个棋面状态,我们执行BREADTH-FIRST SEARCH,DEPTH-FIRST SEARCH(n),DEPTH-FIRST SEARCH(2*n)和A*搜索。对于每个n:
·我们将计算开放集合和闭合集中的状态数目,从而可以看出算法得到解的效率如何。标记为#的列表示的是多次运行的平均值。
·一旦找到解,我们将会计算解的步数,这样能够看出得到的路径的质量。标有s的列表示的是多次运行的结果。括号中的数字技术的是在给定深度限制下,没有能够得到解的次数。
表7-4综合了1000次运行的结果,列出了两个统计值:(a)生成的搜索树的平均状态数目,(b)同样的结果的平均步数。
注意看随着n的增加,盲目搜索的搜索树的规模指数增长,但是A*搜索的搜索树规模还是可控的。更精确地说,这些盲目搜索的增长率如下:
广度优先搜索一直能够找到解的最短路径,但是注意即使A*搜索检查更少的棋面状态,但是得到的解质量也不错(由于GoodEvaluator启发函数)。在达到30步之后,搜索树的增长率达到O(n1.5147),虽然不是线性,但是相比起盲目搜索,这个规模已经相当小了。这些增长率函数的指数部分依赖于问题的分支因子。表7-4的图形化表示如图7-14所示。
图 7-14 随机位置的搜索树对比广度优先搜索能够找到最短路径,而A*搜索找到的路径也差不多是最短的。最后,我们看看水平效应是如何阻止深度优先搜索解决问题的(回忆一下那些离目标状态只有两三步远的状态却被加入闭合集)。事实上,在1000次实验中,深度优先搜索使用最大深度限制为13时,60%的实验都失败了。
分析主要关注于搜索状态的数目,这是决定搜索效率的主要因素。当三种搜索都有可能搜索指数级的状态时,由于h*(n)函数计算出的启发式信息,A*搜索将搜索最少的状态。
解决滑动n2-1个方块这样的问题不仅仅只是有寻路这种方法。Parberry(1995)提出了一种别出心裁的方法,使用分治思想。也就是说,给定一个n×n数码,n>3,首先完成最左边的列和最上部的行,然后递归解决(n-1)2-1数码问题。我们得到一个3×3的子问题,这是可以简单地使用穷举法来解决。这个方法保证能在5*n3步内找到解。
我们现在结束对搜索树的讨论。本章剩余的算法都是基于博弈树的。