百度一下 藏锋者 就能快速找到本站! 每日资讯归档 下载藏锋者到桌面一键访问

当前位置:主页 > 人工智能 > 宽度优先搜索

宽度优先搜索

所在栏目:人工智能 时间:10-11 15:17 分享:

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

ProcedureBreadth-first-searchBegin(1)把初始节点放入队列;(2)Repeat取得队列最前面的元素为current;Ifcurrent=goal成功返回并结束;ElsedoBegin如果current有子女,把current的子女以任意次序添加到队列的尾部;EndUntil队列为空End.上面给出的宽度优先搜索算法依赖于简单的原理:如果当前的节点不是目标节点,则把当前节点的子孙以任意顺序增加到队列的后面,并把队列的前端元素定义为current。如果目标发现,则算法终止。

1.时间复杂度

为了便于分析,我们考虑1棵树,其每个节点的分支系数都为b,最大深度为d。其中分支系数是指1个节点可以扩展产生的新的节点数目。因此搜索树的根节点在第1层会产生b个节点,每个节点又产生b个新的节点,这样在第2层就会有b2个节点。因为目标不会出现在深度为(d-1)层,失败搜索的最小节点数目为:1+b+b2+…+bd-1=(bd-1)/(b-1)b>>1而在找到目标节点之前可能扩展的最大节点数目为:1+b+b2+…+bd-1+bd=(bd+1-1)/(b-1)对于d层,目标节点可能是第1个状态,也可能是最后1个状态。因此,平均需要访问的d层节点数目为:(1+bd)/2所以,平均总的搜索的节点数目为:(bd-1)/(b-1)+(1+bd)/2≈bd(b+1)/2(b-1)因此,宽度优先搜索的时间复杂度和搜索的节点数目成正比。

2.空间复杂度

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

宽度优先搜索 免费邮件订阅: 邮件订阅

图片推荐

热点排行榜

CopyRight? 2013 www.cangfengzhe.com All rights reserved