贡献者: 有机物
迭代加深是用于优化 DFS 的,DFS 是沿着一条路径一直往下走,一条路走到黑,直到没有路可走了才回溯。但如果存在一课搜索树,树的深度很大,但答案却在深度很浅的右半部分子树中,DFS 会搜很多无用的结点。
如下图,答案在深度很浅的红色部分,普通的 DFS 会先遍历蓝色部分,从而浪费大量的时间。
迭代加深的基本思想是:加一个搜索深度的限制,每次只从不超过深度限制的部分进行搜索,如果在限制搜索内无法搜索到答案,那么就将限制扩大一倍。迭代加深看起来很像 BFS,但两者之间还是有区别的,BFS 每次只是扩展当前结点相邻的一层,但迭代加深的本质还是 DFS,还是会沿着一条路径搜索。BFS 的空间复杂度是指数级别的,但 DFS 是和深度呈正比的。假设当前的深度限制为
迭代加深的基本框架:
例题:加成序列。
数据范围
搜索顺序为:依次枚举序列中的每个位置可以填什么数。
剪枝优化:
C++ 代码: