迭代加深搜索 (IDDFS)和IDA算法

IDDFS：

我个人这个搜索的理解就是以BFS的思想写DFS。

具体来说就是，**首先深度优先搜索k层，若没有找到可行解，再深度优先搜索k+1层，直到找到可行解为止。**由于深度是从小到大逐渐增大的，所以当搜索到结果时可以保证搜索深度是最小的。这也是迭代加深搜索在一部分情况下可以代替广度优先搜索的原（还比广搜省空间）。

前提：

题目一定要有解，否则会无限循环下去。

好处：

1.时间复杂度只比BFS稍差一点（虽然搜索k+1层时会重复搜索k层，但是整体而言并不比广搜慢很多）。

2.空间复杂度与深搜相同，却比广搜小很多。

3.利于剪枝。

使用搜索算法的时候，选择正确的搜索方式很重要。当有一类问题需要做广度优先搜索，但却没有足够的空间，而时间却很充裕，碰到这类问题，我们可以选择迭代加深搜索算法。

IDA*算法：

IDA算法能简要概述为：IDA = IDDFS + 乐观估计函数
在这里乐观估计函数的作用是判断在某个深度时问题是否可解，若无解则返回，即IDDFS利用乐观估计函数进行剪枝操作。

使用迭代加深搜素时没有剪枝操作时，时间开销是非常大的（因为迭代加深搜索是通过限制每次dfs的最大深度进行的搜索。令maxd表示最大的搜索深度，那么dfs就只能在0~maxd之间来进行，如果在这个范围内找到了解，就退出大循环，否则maxd++，扩大搜索范围。所以可想而知，倘若没有高效及时的退出无解的情况，那么时间上的开销也是会比较大的。）

如何及时的退出无解情况呢？这里引入乐观估计函数。这时就需要进行“剪枝”操作，及时地判断此时能否找到解。对于迭代加深搜索，经常通过设计合适的“乐观估价函数”来判断能否剪枝。

乐观估计函数：从当前深度到找到最终的解“至少”还需要多少步，或者距离找到最终的解还需要扩展多少层。如果超出了当前限制的深度maxd，说明当前限制的最大深度下是不可能找到解的，直接退出。（这个函数你只需要乐观的去构造就行了）设当前搜索的深度是cur，乐观估价函数是h(),那么当cur+h()>maxd时就需要剪枝。

比如在“埃及分数”问题中要求将一个分数a/b分解成为若干个形如1/d的加数之和，而且加数越少越好，如果加数个数相同，那么最小的分数越大越好。要拆分19/45这样的一个分数，假设当前搜索到了第三层，得到19/45=1/5+1/100…那么根据题意此时最大的分数为1/101，而且如果需要凑够19/45，需要(19/45-1/5-1/100)*101=23个1/101才行。即从第3层还要向下扩展至少大于23层的深度才可能找到所有的解。所以如果此时的maxd<23，就可以直接剪枝了。因此(a/b-c/d)/(1/e)便是本题的乐观估价函数。

注意，使用IDA*算法时要保证一定可以找到解，否则会无限循环下去。

下面给出“埃及分数”问题的代码以便更好地理解IDA*算法的过程：

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
int maxdepth;
int a, b;
const int maxn = 1000;
int ans[maxn], temp[maxn]; //最终结果 临时结果
int gcd(int a, int b)
{
    return b == 0 ? a : gcd(b, a % b);
}

int get_first(int a, int b) //找到1/c≤a/b时最小的c
{
    int c = 1;
    while (b > a * c)
        c++;
    return c;
}

bool better(int depth) //比较深度为depth时，现在找到的解是不是更优的
{
    for (int i = depth; i >= 0; i--)
        if (temp[i] != ans[i])
        {
            return ans[i] == -1 || temp[i] < ans[i]; //两种情况下说明当前更优：(1)此时尚未找到过解；(2)当前的分母小于原来的分母，说明当前的分数比原来的更大，符合题意要求
        }
    return false;
}

bool dfs(int depth, int from, LL aa, LL bb) //当前深度为depth,分母不能小于from,分数之和恰好是aa/bb
{
    if (depth == maxdepth) //到达了最后一层
    {
        if (bb % aa)
            return false; //不能整除，说明最后一项不符合埃及分数的定义，失败退出
        temp[depth] = bb / aa;
        if (better(depth))
            memcpy(ans, temp, sizeof(LL) * (depth + 1)); //当前找到的解是更优的，更新ans
        return true;
    }
    bool flag = false;
    from = max(from, get_first(aa, bb)); //更新from 使1/from尽可能小 和不越界
    for (int i = from;; i++)             //枚举分母
    {
        if (bb * (maxdepth + 1 - depth) <= i * aa)
            break; //利用乐观估价函数来剪枝，从当前深度depth到达maxdepth一共有maxdepth-depth+1项，如果(maxdepth-depth+1)*(1/i)还凑不够aa/bb，需要剪枝
        temp[depth] = i;
        LL b2 = bb * i; //计算aa/bb-1/i，通分后，分母是bb*i，分母是aa*i-bb
        LL a2 = aa * i - bb;
        LL g = gcd(a2, b2); //计算分子，分母的最大公约数，便于约分
        if (dfs(depth + 1, i + 1, a2 / g, b2 / g))
            flag = true;
    }
    return flag;
}

int main()
{
    while (scanf("%d%d", &a, &b)) //输入分数a/b
    {
        for (maxdepth = 1;; maxdepth++)
        {
            memset(ans, -1, sizeof(ans));
            if (dfs(0, get_first(a, b), a, b))
                break;
        }
        printf("%d/%d=", a, b);
        for (int i = 0;; i++)
            if (ans[i] > 0)
                printf("%s1/%d", i == 0 ? "" : "+", ans[i]);
            else
            {
                printf("\n");
                break;
            }
    }
    return 0;
}