广度优先搜索

3.4.1 广度优先搜索

广度优先搜索是一个简单的搜索策略，首先是扩展根节点，接着扩展根节点的所有后继，然后再扩展它们的后继，依此类推。一般来讲，在下一层的任何节点扩展之前搜索树上本层深度的所有节点都已经扩展过。

广度优先搜索可以调用函数TREE-SEARCH来实现，该函数以一个空的边缘为参数，而边缘是一个先进先出（FIFO）队，保证了先访问到的节点先被扩展。换句话说，调用函数 TREE-SEARCH(problem, FIFO-QUEUE())能够得到一个广度优先搜索。先进先出队把所有新生成的后继节点放在队尾，这意味着浅层的节点会在深层节点之前被扩展。图3.10显示了一个简单二叉树的搜索过程。

图3.10 简单二叉树上的广度优先搜索。在每个阶段，下一个要扩展的节点由箭头指示出来

我们将用前面提到的四个标准来评价广度优先搜索。我们很容易知道广度优先搜索是完备的——如果最浅的目标节点处于一个有限的深度 d，广度优先搜索在扩展完比它浅的所有节点（倘若分支因子b是有限的）之后最终能找到这个目标节点。最浅的目标节点不一定就是最优的目标节点；技术上讲，如果路径耗散是节点深度的非递减函数，广度优先搜索才是最优的。（例如，当所有的行动具有相同的耗散。）

到目前为止，关于广度优先搜索的消息都是好的。但要看到为什么通常它不是搜索策略的最佳选择，我们不得不考虑完成搜索所需的时间和内存。我们考虑一个假想的状态空间，状态空间中每个状态都有b个后继。搜索树的根节点生成第一层的b个子节点，每个子节点又生成b个子节点，在第二层总共有b2个节点。这些节点的每一个再生成b个子节点，在第三层则得到b3个节点，依此类推。现在假设解的深度为d。在最坏的情况下，我们将要扩展第d层的除了最后一个节点外的所有节点（因为目标节点本身尚未被扩展），那么在d+1层会生成了bd+1− b个节点。这时已经生成的节点数为：

b+b2+b3+…+bd+(bd+1− b) = O(bd+1)

每个生成的节点都必须保存在内存中，因为它既是边缘的一部分又是边缘节点的祖先。因此，该算法的空间复杂度和它的时间复杂度相等（再加上一个根节点）。

分析复杂度的人也许会对指数级的复杂度产生担心（或者是兴奋，如果他们喜欢挑战的话），比如O(bd+1)。图3.11说明了为什么。它列出了当分支因子b=10的时候广度优先搜索算法搜索到不同的解深度d所需要的时间和空间开销。表中假设每秒钟能够生成10 000个节点，并且存储一个节点需要1000字节。许多搜索问题在现代个人计算机上运行的时候粗略符合这样的假设（可乘以或者除以一个因子100）。

从图3.11中可以学到两个教训。第一，在广度优先搜索算法中内存的需求是比执行时间的消耗更大的问题。要求解一个重要问题，搜索到第8层花费31个小时也许还不算太长，但是很少有计算机能具备上T字节（1T = 1MM 约为1012）的主存支持其存储要求。幸运的是，还有其它需要内存较少的搜索策略。

图3.11 广度优先搜索的时间和内存需求。显示的数字在如下假设基础上得到：搜索树的分支因子为b=10；10000个节点/秒；1000字节/节点

第二个教训，时间需求仍然是个主要因素。如果你的问题在第12层有一个解，那么（按照我们所给的假设）广度优先搜索（或者事实上任何无信息搜索）需要花费35年的时间来找到它。一般来讲，除了最小的实例以外指数级复杂度的搜索问题不能用无信息的方法解决。