迭代加深搜索算法：
对于可以用回溯法解决，但是解答树结点数大的恐怖的问题的一种解决办法，有的问题甚至用bfs连一层节点都遍历不完就超时了。具体方法就是依次枚举搜索层数，从1到一个上限。
结构：
int solve() {
for (int maxd = 1; maxd < MAXN; maxd++) {
if (dfs(0, maxd)) return maxd;
}
return MAXN;
}
优点：
相较于bfs老老实实的枚举解答树而言， 迭代加深搜索算法可以以深度优先搜索，也就是说可以第一时间到达最深层次进行搜索。平均时间上而言比bfs逐层搜索要快太多太多了，再配合回溯剪枝。优化效果相当可观！
举例：
对于这道题， 0 < n < 10, 也就是总状态有9！ ＝ 362880个。 虽然看起来很少，但是每个结点可以扩展到的结点个数是 (n * (n/2) * (n/2)) ＝ (n^3)/4 ≈ 183, 再加上对每个结点判重和剪枝计算，每个结点的计算量大概是 183 * 40 ＝ 7290
所以对于一组n = 9的数据，最差情况的计算量是 n! * (n^3)/4 * 40 ≈ 26亿
然而测试数据一共有20组
也就是说 总计算量是 26亿 ＊ 20 ＝ 520亿
即便我用bfs＋剪枝， 程序还是毫无悬念的超时了。
然而如果我用迭代加深搜索算法，20组数据运行时间总和是73ms， 快了1183倍！
迭代加深搜索算法总结（ID）
原文：http://www.cnblogs.com/Bowen-/p/4952431.html
