算法浅谈之迭代加深

本文主要是介绍算法浅谈之迭代加深，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

迭代加深
在计算机科学中，迭代深化搜索（\(iterative\) \(deepening\) \(search\)）或者更确切地说迭代深化深度优先搜索 (\(iterative\) \(deepening\) \(depth-first\) \(search\) (\(IDS\) \(or\) \(IDDFS\))) 是一个状态空间（状态图）搜索策略。在这个搜索策略中，一个具有深度限制的深度优先搜索算法会不断重复地运行，并且同时放宽对于搜索深度的限制，直到找到目标状态。\(IDDFS\) 与广度优先算法是等价的，但对内存的使用会少很多；在每一步迭代中，它会按深度优先算法中的顺序，遍历搜索树中的节点，但第一次访问节点的累积顺序实际上是广度优先的。
（以上摘自百度百科）

迭代加深的思想
优化搜索的一种方法，可以看成把广搜和深搜的优点结合在一起的算法，但是空间比广搜要小的多。（一般在求最少步数类似的题目中可以运用）算法流程如下：先枚举每次搜索的深度，如果当前深度超过了我们指定的深度，那么便可以\(return\)了。如果当前已经找到了答案，便可直接返回解，而省略了后面无用的搜索。（这点\(BFS\)也可以做到，只不过不觉得打\(BFS\)很烦吗？？？）

一般套路:

int s;
for(s=0;;s++)//枚举DFS搜索的最大深度
    if(dfs(0,..))break;
cout<<s<<endl;

而搜索时也不要忘了剪枝

if(deep>s)return;

肯定有人问：每次都枚举深度，深度不断++，而每次又从头开始进行搜索，那会有很多进行重复搜索的呀。

这点其实大家都应该想到了，这里做出解释：

因为深度越大，结点的数目也就越多，耗费的时间是呈几何级增长的，重复搜索的部分时间基本可忽略不计。

这篇关于算法浅谈之迭代加深的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！