迭代加深搜索

迭代加深搜索（Iterative Deepening Depth First Search,IDDFS），是朴素深度优先搜索（Depth First Search,DFS）的一种改进。它的核心思想是：控制当前搜索的深度上限$mxd$，初始化为$1$并令其不断递增，在这个深度限制上进行DFS……

一 引入

1 概念

迭代加深搜索（Iterative Deepening Depth First Search,IDDFS），是朴素深度优先搜索（Depth First Search,DFS）的一种改进。它的核心思想是：控制当前搜索的深度上限$mxd$，初始化为$1$并令其不断递增，在这个深度限制上进行DFS。

2 优势

迭代加深搜索是状态空间搜索（即隐式图的搜素）中比较常用的搜索方式之一，适用于解决搜索树（即状态树）的深度的广度看似都没有明显上限的状态空间搜索问题。与其类似的算法还有IDA*（Iterative Deepening A-Star）算法，在状态空间搜索问题中也比较常用。

最常见的两种搜索方式（或称搜索顺序）即是深度优先搜索和广度优先搜索（Breadth First Search），前者优先遍历当前节点的一棵子树，后者优先遍历当前节点的所有子节点。但是如果有一棵看似非常庞大的搜索树，如下图（请把它想得再庞大一点），这两种搜索方式劣势明显。

如图，无论使用DFS还是BFS，从初始状态到达目标状态都要消耗不少的时间，因为该搜索树无论在深度上还是在广度上都是看似无限大的（请人为脑补）。

但是目标状态只有一个且是确定的。这时不妨先控制每次DFS的深度，并且通过最大深度对当前所有子状态进行可行性剪枝，也就是限制广度，那么我们只需要花费一定的时间就可以到达目标状态。
如下图，即是IDDFS的搜索方法。注意在DFS的深度扩大的同时，广度也是在不断扩大的。

---

二 应用

「UVa12558」埃及分数

在古埃及，人们用若干单位分数（形如1/a，a是有理数）的和表示一切有理数。例如，2/3=1/2+1/6，但不允许2/3=1/3+1/3，因为加数不允许相同。
对于一个分数a/b，有多种表示方法，其中加数少的比加数多的好，若加数个数相同，则最小的分数越大越好。例如，19/45=1/5+1/6+1/18是最优方案。
输入整数a/b，计算最佳表达式，加数从大到小排列。

1 分析

此题显然可以用搜索来解决，但是它的解答树是及其庞大的。你既无法预估它的深度（加数个数），也无法预估当前深度下解答树的广度（加数大小）。此时只能通过IDDFS来求解。

2 思路

设当前最大深度限制为$mxd$，定义DFS函数为$\text{dfs}(d,c,a,b)$，其中$d$为当前深度，$a/b$为当前剩余的分数，$c$为满足$1/c \leqslant a/b$的最小$c$。
DFS的流程如下：

检查是否到达深度限制
T -> 检查剩余分数(a/b)是否为埃及分数，并返回true/false
F ->
    1. 确定c的值，并循环i : from c to INFTY
    2. 检查1/i*(mxd-d+1)<=a/b（可行性剪枝），若否，跳出循环
    3. 计算新的剩余分数(a/b-1/i)，向下一层递归
    4. 检查递归结果，若为ture，跳出循环并返回ture
    5. repeat 1.
    fin. 循环结束，返回false

3 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
using namespace std;

#define LL long long

const int CN = 1e5+5;
int t;

LL gcd(LL a,LL b){ //最大公约数
    return b ? gcd(b,a%b):a;
}

//IDDFS
int mxd;
LL ans[CN],cur[CN];

/*返回getfirst(a,b)=c,使得1/c<=a/b且c的值最大*/
LL getfirst(LL a,LL b){
    if(b % a) return (b/a)+1;
    return b/a;
}
/*检查当前的到的答案和之前得到的答案那个更优*/
bool better(int pos){
    for(int i=pos;i;i--)
        if(cur[i] != ans[i])
            return ans[i]==-1 || cur[i]<ans[i];
    return false;
}
/*把f数组赋值到t中，长度为sz*/
inline void copy(LL* f,LL* t,int sz){ 
    for(int i=1;i<=sz;i++) t[i] = f[i];
}
/*当前深度d 当前分数1/c 剩余分数a/b*/
bool dfs(int d,LL c,LL a,LL b){
    if(d == mxd){ //最后一个分数是1/(a/b)，即b/a
        if(b%a) return false; //检查它是不是埃及分数
        cur[d] = b/a; //记录答案
        if(better(d)) copy(cur,ans,d); //维护答案
        return true;
    }
    bool flag = false;
    c = max(c, getfirst(a,b)); //找到c值
    for(LL i=c;;i++){ //枚举
        if((mxd-d+1)*b <= a*i) break; //可行性剪枝
        cur[d] = i; //记录答案
        /*计算a/b - 1/i = a1/b1*/
        LL a1 = a*i-b,b1 = b*i；
        LL g = gcd(a1,b1); //便于约分 
        if(dfs(d+1,i+1, a1/g, b1/g)) flag = true;
    }
    return flag;
}

int main()
{
    ... //scan
    bool found = false;
    for(mxd=1; !found; mxd++){ //主求解代码
        memset(ans,-1,sizeof(ans));
        found = dfs(0,getfirst(fa,fb),fa,fb);
    }
    ... //print
    return 0;
}