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

当前位置:主页 > 人工智能 > 迭代加深搜索

迭代加深搜索

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

对于深度d比较大的情况,深度优先搜索需要很长的运行时间,而且还可能得不到解答。一种比较好的问题求解方法是对搜索树的深度进行控制,即有界深度优先搜索方法。有界深度优先搜索过程总体上按深度优先搜索方法进行,但对搜索深度需要给出一个深度限制dm,当深度达到了dm的时候,如果还没有找到解答,就停止对该分支的搜索,换到另外一个分支进行搜索。

对于有界深度搜索策略,有下面几点需要说明:

(1)在有界深度搜索算法中,深度限制dm是一个很重要的参数。当问题有解,且解的路径长度小于或等于dm时,则搜索过程一定能够找到解,但是和深度优先搜索一样,这并不能保证最先找到的是最优解:即这时有界深度搜索是完备的但不是最优的。但是当dm取的太小,解的路径长度大于dm时,则搜索过程就找不到解:即这时搜索过程甚至是不完备的。

(2)深度限制dm不能太大。当dm太大时,搜索过程会产生过多的无用节点,既浪费了计算机资源,又降低了搜索效率。有界深度搜索的时间和空间复杂度与深度优先搜索类似,空间是线性复杂度为O(bdm),时间是指数复杂度为O(bdm)。

(3)有界深度搜索的主要问题是深度限制值dm的选取。该值也被称为状态空间的直径,如果该值设置的比较合适,则会得到比较有效的有界深度搜索。

但是对很多问题,我们并不知道该值到底为多少,直到该问题求解完成了,才可以确定出深度限制dm。为了解决上述问题,可采用如下的改进方法:先任意给定一个较小的数作为dm,然后按有界深度算法搜索,若在此深度限制内找到了解,则算法结束;如在此限制内没有找到问题的解,则增大深度限制dm,继续搜索。这就是迭代加深搜索的基本思想。

迭代加深搜索是一种回避选择最优深度限制问题的策略,它是试图尝试所有可能的深度限制:首先深度为0,然后深度为1,然后为2,等等,一直进行下去。如果初始深度为0,则该算法只生成根节点,并检测它。如果根节点不是目标,则深度加1,通过典型的深度优先搜索算法,生成深度为1的树。同样当深度限制为m时,树的深度也会为m。

迭代加深搜索看起来会很浪费,因为很多节点都可能要扩展多次。然而对于很多问题,这种多次的扩展负担实际上很小。直觉上可以想象,如果一棵树的分支系数很大,几乎所有的节点都在最底层上,则对于上面各层节点多次扩展对整个系统来说影响不是很大。

我们知道搜索深度为h时,由深度优先搜索方法生成的节点数为:(bh+1-1)/(b-1)由迭代加深搜索过程中的失败搜索所产生的节点数量的总和为:{1/(b-1)}d-1h=0(bh+1-1)≈b(bd-d)/(b-1)2该算法的最后一次搜索在深度d找到了成功节点,则该次搜索的平均时间复杂度为典型的深度有限搜索:b(bd+d)/2(b-1)。则总的平均时间复杂度为:b(bd-d)/(b-1)2+b(bd+d)/2(b-1)≈(b+1)bd+1/2(b-1)2则迭代深度搜索和深度优先搜索的时间复杂度的比率为:[(b+1)bd+1/2(b-1)2]∶[b(bd+d)/2(b-1)]对于比较大的d来说,上式简化为:[(b+1)bd+1/2(b-1)2]∶[(bd+1)/2(b-1)]=(b+1)∶(b-1)迭代深度搜索和宽度优先搜索的时间复杂度的比率为:[(b+1)bd+1/2(b-1)2]∶[bd(b+1)/2(b-1)]=b∶(b-1)对于一个分支系数b=10的深度目标,迭代深度搜索比深度优先搜索增加20%左右的节点,而只比宽度优先搜索增加了11%左右的额外节点。而且,分支系数越大,重复搜索所产生的额外节点比率越少。因此迭代加深搜索和深度优先搜索方法以及宽度优先搜索方法相比并没有增加很多的时间复杂度。这就是说迭代加深搜索的时间复杂度为O(bd),空间复杂度为O(bd),它既满足深度优先搜索的线性存储要求,同时又能保证发现最小深度的目标。

迭代加深搜索 免费邮件订阅: 邮件订阅

图片推荐

热点排行榜

CopyRight? 2013 www.cangfengzhe.com All rights reserved