有这样一些题目，它们的搜索树很特别：不仅很深，而且很宽，深度可能到无穷，宽度也可能极广

如果直接朴素 DFS ，会陷入递归无法返回，如果直接朴素 BFS，队列空间会爆炸

鄙人想了一个简单的例子，来说明为什么需要迭代加深搜索

Why use IDDFS

假设你需要使用枚举的方式暴力破解一个用户的密码，密码只由 26 个小写字母组成，但是密码的位数未知

假设你的内存同时能存储 100 个字符，你该如何枚举？

先试试 BFS？首先把 26 个字母加入队列，目前队列中的状态是这样的

1
{"a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"}

现在，拿出第一个状态 "a" ，枚举它能到达的状态，并且扔到队列后面

1
{"b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z","aa","ab","ac","ad","ae","af","ag","ah","ai","aj","ak","al","am","an","ao","ap","aq","ar","as","at","au","av","aw","ax","ay","az"}

这时你会发现，队列貌似是以指数速度扩张的，100 的容量还不够搜两层！

这也是 BFS 的一个弊端：必须同时存储同一层的所有状态，很容易 MLE，但是能保证最先找到的就是搜索树上最近的解

那试试 DFS？DFS 搜索的时候是一条长链，每时每刻只存储当前的状态，100 的空间可以理论上可以存下长度为 100 的密码

但是朴素 DFS 也是不行的，因为它会始终会递归自己，你只会得到全是 a 的密码，然后超过 100 位之后爆内存（

你可能会说：不对哇？我可以每次都在第 101 层返回，这样就不会爆内存了

的确如此，你已经找到些感觉了

但是如果这样的话，最先枚举出来的是长度为 100 的密码，如果真实的密码很短呢？（或者说，有很多解，但题目要求的是搜索树上最近的解）

那可以这样：先用 DFS 限定只搜一层，搜完就返回，搜不到再搜两层，再搜不到就搜三层， 以此类推

其实这就是迭代加深搜索了

What is IDDFS

迭代加深搜索（Iterative Deeping DFS，IDDFS），一种结合了 BFS（一层一层搜） 和 DFS（栈式状态存储）思想的搜索算法，具体操作方法如下：

  1. 先假设搜索深度为 1，用 DFS 搜索到第一层就停止，也就是说，用 DFS 搜索一个深度为 1 的搜索树
  2. 如果没有找到答案，再设定搜索深度为 2，用 DFS 搜索前两层即停止，也就是说，用 DFS 搜索一个深度为 2 的搜索树
  3. 继续设定深度为 3、4 ······逐步扩大 DFS 的搜索深度，直到找到答案

这个迭代过程，在每一层的广度上采用了 BFS 的思想，在具体编程实现上则是 DFS 的

How to use IDDFS

最经典的题目非P1763 埃及分数莫属

点击查看题目

  • 题目描述

    在古埃及，人们使用单位分数的和（形如 1a\dfrac{1}{a} 的，aa 是自然数）表示一切有理数。如：23=12+16\dfrac{2}{3} = \dfrac{1}{2} + \dfrac{1}{6}，但不允许 23=13+13\dfrac{2}{3} = \dfrac{1}{3} + \dfrac{1}{3}，因为加数中有相同的。对于一个分数 ab\dfrac{a}{b}，表示方法有很多种，但是哪种最好呢？首先，加数少的比加数多的好，其次，加数个数相同的，最小的分数越大越好。如：

    1945=13+112+11801945=13+115+1451945=13+118+1301945=14+16+11801945=15+16+118\begin{aligned} \frac{19}{45} &= \frac{1}{3} + \frac{1}{12} + \frac{1}{180}\\ \frac{19}{45} &= \frac{1}{3} + \frac{1}{15} + \frac{1}{45}\\ \frac{19}{45} &= \frac{1}{3} + \frac{1}{18} + \frac{1}{30}\\ \frac{19}{45} &= \frac{1}{4} + \frac{1}{6} + \frac{1}{180}\\ \frac{19}{45} &= \frac{1}{5} + \frac{1}{6} + \frac{1}{18}\\ \end{aligned}

    最好的是最后一种，因为 118\dfrac{1}{18} 比 1180,145,130\dfrac{1}{180}, \dfrac{1}{45}, \dfrac{1}{30} 都大。
    注意，可能有多个最优解。如：

    59211=14+136+1633+1379859211=16+19+1633+13798\begin{aligned} \frac{59}{211} &= \frac{1}{4} + \frac{1}{36} + \frac{1}{633} + \frac{1}{3798}\\ \frac{59}{211} &= \frac{1}{6} + \frac{1}{9} + \frac{1}{633} + \frac{1}{3798}\\ \end{aligned}

    由于方法一与方法二中，最小的分数相同，因此二者均是最优解。

    给出 a,ba,b，编程计算最好的表达方式。保证最优解满足：最小的分数 ≥1107\ge \cfrac{1}{10^7}。

  • 输入格式

    一行两个整数，分别为 aa 和 bb 的值。

  • 输出格式

    输出若干个数，自小到大排列，依次是单位分数的分母。

  • 样例 #1

    • 样例输入 #1

      1
      19 45
      • 样例输出 #1
      1
      5 6 18

  • 提示

    1<a<b<10001 \lt a \lt b \lt 1000

这道题有那么一点复杂，看了一晚上才搞懂 （毕竟我数学不好）

首先这东西涉及到分数，自然是能约分就要约分，所以需要一个约分的函数

然后需要设计搜索函数，并定义变量：

IDDFS(now,x,y)IDDFS(now,x,y)

  • 定义本次迭代搜索的最大深度为 limlim ，目前的搜索深度为 nownow ，也就是说，当前最多还能构造 lim−now+1lim-now+1 个分数（算上目前这个）
  • 数组 ans[i]ans[i] 保存本次搜索的答案（ans[1]ans[1] 至 ans[now−1]ans[now-1] 依次是前面分数的分母）
  • 初始分数为 ab\dfrac{a}{b} ，目前还剩下需要表示部分为 xy\dfrac{x}{y}，也就是说 xy=ab−∑i=1now−11ans[i]\dfrac{x}{y}=\dfrac{a}{b}-\sum ^{now-1}_{i=1}\dfrac{1}{ans\left[ i\right] }

现在需要知道当前分数的分母 ans[now]ans[now] ，方法自然是靠枚举，但是范围是什么？总不能从 11 一直枚举到 10710^{7} 吧，现在来确定分母的上下界

  • 因为后面的分数总是小于前面的分数，也就是 1ans[now]<1ans[now−1]\dfrac{1}{ans[now]}<\dfrac{1}{ans[now-1]} ，结合分母必是整数可得 ans[now]≥ans[now−1]+1ans[now]\geq ans[now-1]+1
  • 当前分数不得大于目前还需要表示的部分，也就是 1ans[now]≤xy\dfrac{1}{ans[now]}\leq\dfrac{x}{y} ， 化简得 ans[now]≥yxans[now]\geq\dfrac{y}{x}
  • 目前还剩下 xy\dfrac{x}{y} ，但最多还能有 lim−now+1lim-now+1 个分数，平均下来每个分数最小为 xylim−now+1\dfrac{\dfrac{x}{y}}{lim-now+1} ，将分子化为 11 ，可知分母最大为 (lim⁡−now+1)⋅yx\left( \lim -now+1\right) \cdot \dfrac{y}{x} ，故 ans[now]≤(lim⁡−now+1)⋅yxans[now]\leq\left( \lim -now+1\right) \cdot \dfrac{y}{x}

这样，当前分母的上下界就清楚了，上界为 (lim⁡−now+1)⋅yx\left( \lim -now+1\right) \cdot \dfrac{y}{x} ，下界为 max(ans[now−1]+1,yx)max(ans[now-1]+1,\dfrac{y}{x})

枚举分母 i=ans[now]∈[max(ans[now−1]+1,yx),(lim⁡−now+1)⋅yx]i=ans[now]\in [max(ans[now-1]+1,\dfrac{y}{x}),\left( \lim -now+1\right) \cdot \dfrac{y}{x}] ，本次构造出来的分数为 1i\dfrac{1}{i}， 还剩下的部分为 xy−1i\dfrac{x}{y}-\dfrac{1}{i} ，通分得 ix−yiy\dfrac{ix-y}{iy}

故继续迭代 IDDFS(now+1,ix−y,iy)IDDFS(now+1,ix-y,iy) 即可

然后，你就能 AC 了

吗？

你会发现你居然能构建出负的分数

因为在计算下界的时候，整型除法直接把小数砍掉了，按理来说应当向上取整

另外一种方法是过滤掉负的分数，毕竟向上取整又牵扯到 double

但是这样其实还不够，因为最先搜出来的不一定是最优的，加数个数相同的，最小的分数越大越好

所以，还要一个 flagflag 保存当前深度有没有解，再使用 best[i]best[i] 记录最优解，每找到一个解就去对比一下

还有最后一个坑，就是要开 long long

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define int long long
using namespace std;
const int N = 1e6 + 5;
int ans[N], best[N], lim = 1;
bool flag;

inline int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

// 分数约分
void simplify(int &a, int &b)
{
    int g = gcd(a, b);
    a /= g;
    b /= g;
}

void IDDFS(int now, int x, int y)
{
    if (now > lim)
        return;
    simplify(x, y);
    if (x == 1 && y > ans[now - 1])
    {
        flag = true;
        ans[now] = y;
        if (ans[now] < best[now])
            for (int i = 1; i <= now; i++)
                best[i] = ans[i];
        return;
    }

    int up = (lim - now + 1) * y / x, down = max(ans[now - 1] + 1, ceil((double)y / x));
    for (int i = down; i <= up; i++)
    {
        int nx = x * i - y, ny = y * i;
        ans[now] = i;
        IDDFS(now + 1, nx, ny);
    }
    return;
}

signed main()
{
    int a, b;
    cin >> a >> b;

    memset(ans, 0, sizeof(ans));
    memset(best, 0x3f, sizeof(best));

    while (!flag)
    {
        IDDFS(1, a, b);
        lim++;
    }

    for (int i = 1; i < lim; i++)
        cout << best[i] << ' ';
}