迭代加深搜索


定义

迭代加深是一种 每次限制搜索深度的 深度优先搜索。

解释

迭代加深搜索的本质还是深度优先搜索,只不过在搜索的同时带上了一个深度 ,当 达到设定的深度时就返回,一般用于找最优解。如果一次搜索没有找到合法的解,就让设定的深度加一,重新从根开始。

既然是为了找最优解,为什么不用 BFS 呢?我们知道 BFS 的基础是一个队列,队列的空间复杂度很大,当状态比较多或者单个状态比较大时,使用队列的 BFS 就显出了劣势。事实上,迭代加深就类似于用 DFS 方式实现的 BFS,它的空间复杂度相对较小。

当搜索树的分支比较多时,每增加一层的搜索复杂度会出现指数级爆炸式增长,这时前面重复进行的部分所带来的复杂度几乎可以忽略,这也就是为什么迭代加深是可以近似看成 BFS 的。

过程

首先设定一个较小的深度作为全局变量,进行 DFS。每进入一次 DFS,将当前深度加一,当发现 大于设定的深度 就返回。如果在搜索的途中发现了答案就可以回溯,同时在回溯的过程中可以记录路径。如果没有发现答案,就返回到函数入口,增加设定深度,继续搜索。

IDDFS(u,d)
    if d>limit
        return
    else
        for each edge (u,v)
            IDDFS(v,d+1)
return

注意事项

在大多数的题目中,广度优先搜索还是比较方便的,而且容易判重。当发现广度优先搜索在空间上不够优秀,而且要找最优解的问题时,就应该考虑迭代加深。

贡献者:@WenzelTian@mgt@ksyx@H-J-Granger@Ir1d@wjy-yy

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组