宽度优先搜索算法在虚拟现实与人工智能应用技术融合研究中的成果

宽度优先搜索算法沿着树的宽度遍历树的节点，它从深度为0 的层开始，直到最深的层次。它可以很容易地用队列实现。宽度优先算法可以表示如下。

算法5.2 宽度优先搜索算法

Procedure Breadth First Search

Begin

1.把初始节点放入队列。

2.Repeat

取得队列最前面的元素为current；

If current=goal

成功返回并结束；

Else do

Begin

如果current有子女，则把current的子女以任意次序添加到队列的尾部；

End

Until队列为空

End.(www.xing528.com)

上面给出的宽度优先搜索算法依赖于简单的原理：如果当前的节点不是目标节点，则把当前节点的子女以任意次序添加到队列的尾部，并把队列的前端元素定义为current；如果目标发现，则算法终止。

（一）时间复杂度

为便于分析，我们考虑一棵树，其每个节点的分支系数都为b，最大深度为d。其中分支系数是指一个节点可以扩展产生的新的节点数目。因此，搜索树的根节点在第一层会产生b个节点，每个节点又产生b个新的节点，这样在第二层就会有b2个节点。因为目标不会出现在深度为（d-1）层，失败搜索的最小节点数目为：

而在找到目标节点之前可能扩展的最大节点数目为：

对于d层，目标节点可能是第一个状态，也可能是最后一个状态。因此，平均需要访问的d层节点数目为（I+bd）/2。

所以，平均总的搜索的节点数目为：

因此，宽度优先搜索的时间复杂度和搜索的节点数目成正比。

（二）空间复杂度

宽度优先搜索中，空间复杂度和时间复杂度一样，需要很大的空间，这是因为树的所有的叶节点都需要同时存储起来。根节点扩展后，队列中有b个节点。第一层的最左边节点扩展后，队列中有（2b-1）个节点。而当d层最左边的节点正在检查是否为目标节点时，在队列中的节点数目最多，为（bd）。该算法的空间复杂度和队列长度有关，在最坏的情况下约为指数级0（bd）。

表5-2给出了宽度优先搜索的时间和空间需求情况，其中分支系数b=10，每秒处理1000个节点，每个节点需要100个字节。

表5-2　宽度优先搜索的时间和空间需求

宽度优先搜索是一种盲目搜索，时间和空间复杂度都比较高，当目标节点距离初始节点较远时（即d较大时）会产生许多元用的节点，搜索效率较低。从表6-2可以看出，宽度优先搜索中，时间需求是一个很大的问题，特别是当搜索的深度比较大时，尤为严重，然而空间需求是比执行时间更为严重的一个问题。

但是宽度优先搜索也有其优点：目标节点如果存在，用宽度优先搜索算法总可以找到该目标节点，而且是d最小（最短路径）的节点。