一、迭代加深名词
在计算机科学中,迭代深化搜索(\(iterative\) \(deepening\) \(search\))或者更确切地说迭代深化深度优先搜索 (\(iterative\) \(deepening\) \(depth-first\) \(search\) (\(ids\) \(or\) \(iddfs\))) 是一个状态空间(状态图)搜索策略。在这个搜索策略中,一个具有深度限制的深度优先搜索算法会不断重复地运行,并且同时放宽对于搜索深度的限制,直到找到目标状态。
\(iddfs\) 与广度优先算法是等价的,但对内存的使用会少很多;在每一步迭代中,它会按深度优先算法中的顺序,遍历搜索树中的节点,但第一次访问节点的累积顺序实际上是广度优先的。
(以上摘自百度百科)
二、理解与感悟
优化搜索的一种方法,可以看成把广搜和深搜的优点结合在一起的算法,但是空间比广搜要小的多。(一般在求最少步数类似的题目中可以运用)算法流程如下:
- 先枚举每次搜索的深度
- 如果当前深度超过了指定的深度,便\(return\)。
- 如果当前已经找到了答案,便可直接返回解,省略后面无用的搜索。
三、一般套路
int s;
for(s=0;;s++)//枚举DFS搜索的最大深度
if(dfs(0,..))break;
cout<<s<<endl;
而搜索时也不要忘了剪枝
//剪枝
if(deep>s)return;
四、疑惑问题
每次都枚举深度,深度不断++,而每次又从头开始进行搜索,那会有很多进行重复搜索的呀?
解释:
因为深度越大,结点的数目也就越多,耗费的时间是呈几何级增长的,重复搜索的部分时间基本可忽略不计。