说到搜索，我们第一反应都是深度优先搜索(DFS)和广度优先搜索(BFS)这两种经典的搜索算法，这两种方法各有千秋在不同的领域都有非常广泛的应用。那么就会有好奇的同学问道了，我们能不能将两者的优点结合起来呢？这不，迭代加深搜索或许就是这个问题最好的解答。

DFS or BFS

说起搜索，就不得不提到深度优先搜索(DFS)和广度优先搜索(BFS)这两种搜索算法。

我们都知道 DFS 就是“一条路走到黑”，空间的开销很小但是时间的开销非常大。

而 BFS 就是“广撒网”，能够保证不会一条路走太远但是由于要保存每一层搜索的节点，其空间开销往往很大，经常会爆空间。

并且在许多情况下，我们是不太知道是用 DFS 好还是 BFS好的，比如在下面这棵树当中要你找某个编号的点是否存在：

如果要找9，那可能是 DFS 更快找到，但如果要找4，DFS 就可能要搜索很多无用的点而 BFS 刷的一下就找到了，但是我们是不能面向数据编程的啊。不事先知道数据的话 DFS 和 BFS 确实很难抉择。

小孩子才做选择，作为成年人我全都要！所以我们就会想能不能找一种算法，能即有 DFS 的优点又有 BFS 的优点，能够在这两种领域中表现的都不算差呢？下面让我们来看看迭代加深搜索算法。

迭代加深搜索

算法原理

所谓迭代加深搜索算法，在我看来其实就是用 DFS 的方法去 BFS 。那为什么这么说呢？

其实迭代加深搜索的本质还是深度优先搜索(DFS)，只不过在搜索的同时带上了一个深度限制maxdepth，当我们当前搜索的深度depth达到设定的深度限制maxdepth时就直接返回。这样就能保证我们的 DFS 不会搜的太过于深入，一般用于找最优解。如果一次搜索没有找到合法的解，就让设定的深度maxdepth加一，重新从根开始进行 DFS。

那有的同学可能就要问了，既然是为了找最优解，为什么不直接用 BFS 呢？我们知道 BFS 的基础是一个队列，队列的空间复杂度很大，当状态比较多或者单个状态比较大时，使用队列的 BFS 就显出了劣势。事实上，迭代加深就类似于用 DFS 方式实现的 BFS，它的空间复杂度相对较小。而且在 BFS 当中空间其实是比时间更容易爆炸的，1e8的状态时间可能还顶得住，但是空间就已经要起飞了。

那我们每次增加深度限制maxdepth时都要重新进行搜索，是不是就意味着我们的时间花销会比普通的 BFS 大很多呢？其实也未必。当搜索树的分支比较多时，每增加一层的搜索复杂度会出现指数级爆炸式增长，这时前面重复进行的部分所带来的复杂度几乎可以忽略，这也就是为什么迭代加深的时间复杂度是可以近似看成 BFS 的时间复杂度。

深搜的空间复杂度+广搜的时间复杂度，迭代加深搜索因为其优越的特性经常被运用在各种搜索毒瘤题当中。

算法实现

首先我们设定一个较小的深度maxdepth作为全局变量，进行 DFS。每进入一次 DFS，将当前深度depth加一，当发现 depth 大于设定的深度 maxdepth 就返回。如果在搜索的途中发现了答案就可以回溯，同时在回溯的过程中可以记录路径。如果没有发现答案，就返回到函数入口，增加设定深度maxdepth，继续搜索。

所以大致的代码框架就如下：

void find(层数参数) {
    if(层数>规定最大层数) return ;
    进行搜索......
}

int main() {
    for(从一开始枚举规定最大层数) {
        find(1);
    }
}

经典例题

[LOJ #10022]埃及分数

题目描述

题目传送门

在古埃及，人们使用单位分数的和(形如1/a的, a是自然数)表示一切有理数。
如：2/3=1/2+1/6,但不允许2/3=1/3+1/3,因为加数中有相同的。
对于一个分数a/b,表示方法有很多种，但是哪种最好呢？
首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。
如：
19/45=1/3 + 1/12 + 1/180
19/45=1/3 + 1/15 + 1/45
19/45=1/3 + 1/18 + 1/30,
19/45=1/4 + 1/6 + 1/180
19/45=1/5 + 1/6 + 1/18.
最好的是最后一种，因为1/18比1/180,1/45,1/30,1/180都大。
给出a,b(0〈a〈b〈1000),编程计算最好的表达方式。
 

Input
一行包含a,b(0〈a〈b〈1000)。

Output
每组测试数据若干个数，自小到大排列，依次是单位分数的分母。

Sample Input
19 45

Sample Output
5 6 18

解题思路

简单来说就是将一个分数 a/b 分解成若干个单位分数 1/x 的和，要求找到加数个数最少且最小的单位分数最大的方案。

既然不知道能分成多少个分数，我们不妨就通过迭代加深搜索枚举我们分成多少个分数即限定搜索层数，然后进行 DFS 就好了。

这里需要注意的是，由于搜索空间还是很大，我们需要尽可能的确定每一层分母 x 的上界的下界。具体来说，我们设当前减去若干个单位分数后得到的分数是 a/b ，当前 DFS 到第 i 层枚举的分母为 now[i]。那么首先我们的 1/now[i] <= a/b，也就是我们的now[i]>=b/a，所以我们的枚举下界就是 b/a 的上取整。

其次，假设我们限制限制最多分解成为maxdepth个分数，我们规定每一层枚举选取的分母都比上一层大(相当于去掉顺序的考虑，减小搜索空间)，也就是我们后面的 maxdepth-i 个分数都会比现在的 1/now[i] 小（分母越大分数越小）,而总和又要达到 a/b 所以 (maxdepth - i + 1)/now[i] > a/b，即(maxdepth - i + 1)*b > a*now[i]，故a*now[i] >= (maxdepth - i + 1)*b时break就好啦，这样就确定了上界。

这样一来就能顺利通过题目了。

算法模板

下面附上算法的模板：

#include <cmath> 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
long long a, b, maxdepth;
long long ans[11000], now[11000];
long long gcd(long long x, long long y) {
    if(y == 0) return(x);
    return(gcd(y, x % y));
}//求解最小公倍数 
long long max_num(long long a, long long b) {
    //a * k >= b
    long long ans = b / a;
    if(b % a) ans++;
    return(ans);
}//计算下界 
bool find(long long a, long long b, long long depth) {
    long long flag = 0;
    if(depth == maxdepth) { 
        if(b % a) return(false);//不是合法答案 
        now[depth] = b / a;
        if(now[depth] < ans[depth] || ans[1] == 0) {
            for(long long i = 1; i <= depth; i++) {
                ans[i] = now[i];
            }
        }//如果找到最小的单位分数更大的方案 
        return(true);
    }
    for(long long i = max_num(a, b); ; i++) {
        //a / b >= (maxdepth - depth + 1) / i => GG
        if(a * i >= (maxdepth - depth + 1) * b) break;
        //上界控制 
        now[depth] = i;
        long long c = gcd(a * i - b, b * i);
        //减去1/i 
        if(find((a * i - b) / c, b * i / c, depth + 1)) flag = 1;
    }
    return(flag);
}
int main() {
    scanf("%lld%lld", &a, &b);//读入 
    for(maxdepth = 1; ; maxdepth++) {
    //枚举最大搜索深度也就是拆解的分数的个数 
        if(find(a, b, 1LL)) {//如果找到了答案 
            printf("%lld", ans[1]);
            for(long long i = 2; i <= maxdepth; i++) printf(" %lld", ans[i]);
            return 0;
        }
    }
    return 0;
} 

结语

通过这篇BLOG，相信你对于搜索又有了更加深入的理解。其实搜索无定形，并没有说哪一种搜索算法就一定是最好的，针对题目灵活应用才是搜索算法的真谛。最后希望你喜欢这篇BLOG!