本篇简述一下迭代加深搜索,并列出了伪代码帮助大家理解。
迭代加深是一种每次限制搜索深度的深度优先搜索。
(1)本质:它的本质还是深度优先搜索,只不过在搜索的同时带上了一个深度d ,当d达到设定的深度时就返回,一般用于找最优解。如果一次搜索没有找到合法的解,就让设定的深度+1 ,重新从根开始。
既然是为了找最优解,为什么不用BFS呢?我们知道BFS的基础是一个队列,队列的空间复杂度很大,当状态比较多或者单个状态比较大时,使用队列的BFS就显出了劣势。事实上,迭代加深就类似于用DFS方式实现的BFS,它的空间复杂度相对较小。
当搜索树的分支比较多时,每增加一层的搜索复杂度会出现指数级爆炸式增长,这时前面重复进行的部分所带来的复杂度几乎可以忽略,这也就是为什么迭代加深是可以近似看成BFS的。
(2)步骤:首先设定一个较小的深度作为全局变量,进行DFS。每进入一次DFS,将当前深度d++ ,当发现d大于设定的深度就返回。如果在搜索的途中发现了答案就可以回溯,同时在回溯的过程中可以记录路径。如果没有发现答案,就返回到函数入口,增加设定深度,继续搜索。
(3)伪代码:
void IDDFS(u,d) { if(d>设定深度) return; else for(each edge(u,v)) IDDFS(v,d+1); return; }
(4)解题策略
在大多数的题目中,广度优先搜索还是比较方便的,而且容易判重。当发现广度优先搜索在空间上不够优秀,而且要找最优解的问题时,就应该考虑迭代加深。
1021 | [编程入门]迭代法求平方根 |
知识点标签:搜索
本文固定URL:https://www.dotcpp.com/course/955