预计阅读本页时间：-
比较
广度优先搜索能够保证找到步数最少的解，但是它可能需要评价规模相当大的移动序列。深度优先搜索试着在每次搜索时能够前进更多步，它可能能够快速得到一个解，但是它也可能在搜索树的某个部分浪费大量的时间，尽管看起来这个部分不可能得到解。
我们认为比较深度优先搜索，广度优先搜索和A*搜索是值得的。使用八数码问题作为样例，我们通过随机移动n个方块（n从2、4、8和16开始），注意同样的方块不会在一行中移动两次，因为这就等于什么也没做。当n≥32时，内存耗尽。对于每个棋面状态，我们执行BREADTH-FIRST SEARCH,DEPTH-FIRST SEARCH(n),DEPTH-FIRST SEARCH(2*n)和A*搜索。对于每个n：
·我们将计算开放集合和闭合集中的状态数目，从而可以看出算法得到解的效率如何。标记为#的列表示的是多次运行的平均值。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
·一旦找到解，我们将会计算解的步数，这样能够看出得到的路径的质量。标有s的列表示的是多次运行的结果。括号中的数字技术的是在给定深度限制下，没有能够得到解的次数。
表7-4综合了1000次运行的结果，列出了两个统计值：（a）生成的搜索树的平均状态数目，（b）同样的结果的平均步数。
注意看随着n的增加，盲目搜索的搜索树的规模指数增长，但是A*搜索的搜索树规模还是可控的。更精确地说，这些盲目搜索的增长率如下：
广度优先搜索一直能够找到解的最短路径，但是注意即使A*搜索检查更少的棋面状态，但是得到的解质量也不错（由于GoodEvaluator启发函数）。在达到30步之后，搜索树的增长率达到O（n1.5147），虽然不是线性，但是相比起盲目搜索，这个规模已经相当小了。这些增长率函数的指数部分依赖于问题的分支因子。表7-4的图形化表示如图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步内找到解。
我们现在结束对搜索树的讨论。本章剩余的算法都是基于博弈树的。
