迭代加深搜索算法(iterative deepening depth-first search (IDS or IDDFS)) 可以被视作是广度优先搜索算法（BFS）和深度优先搜索算法（DFS）的结合。常用于解决在广度很深度上都无限的问题，最经典的便是埃及分数：
在古埃及，人们使用单位分数的和(形如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
Output：
一个等式
Sample Input：
3 4
Sample Output:
3/4 = 1/2 + 1/4
埃及分数问题的广度（单位分数的大小）和深度（单位分数的求和数量）都是无限的。在单纯的DFS问题中，很多时候剪枝技术只是一种优化，但在IDDFS中，剪枝直接限定了合理有效的边界，使搜索在优先的范围内进行，使得回溯和搜索都成为了可能。因此在IDDFS中，如何剪枝成为了不可绕过的重要话题，直接决定了是否能合理地解决问题。
简要回顾以下IDDFS的思想：逐渐增加DFS的递归深度，同时每一层都采用BFS进行搜索，可以说IDDFS就是用DFS串起来的BFS，又或者用笔者在DFS笔记中的类比，DFS是”动态循环“，普通的DFS的循环体只是一个简单判断，而IDDFS中的循环体就是一个BFS。
本题存在两个维度的最优解情况：1、和式中的分数最少，2、和式中的最小的分数最大（分母最小），其中2是在1的条件下进行判断。考虑到IDDFS中DFS和BFS的从属关系，自然1应当由DFS处理，而2则是BFS。
接下来具体分析一下题目，首先本题采用分数作为结果，为了保证过程没有误差，采用浮点型进行计算是错误且复杂的，会牵扯到小数和分数的转换问题。在本题中，对于分数而言分子和分母成对出现，不如用pair<int,int>来储存它们，first是分子，second是分母。在此基础上，需要重新定义这种特殊类型的分数的求和函数：
int gcd(int a,int b) //辗转相除法求公约数
{return b==0 ? a : gcd(b,a%b);}
pair<int,int> sum(pair<int,int> a, pair<int,int> b){
pair<int,int> result;
int c = a.first*b.second+b.first*a.second;
int d = a.second*b.second;
int g = abs(gcd(d,c));
c /= g; d /= g;
result.first = c; result.second = d;
return result;
}有了求和方法之后似乎分数运算变得可行，如果要比大小的话只需要将其中一个的first*（-1）传入，再比较结果的符号即可。同时本题需要输出一个和式，这个和式再DFS的过程中也需要被跟踪，所以不妨先放出两个字符串和整型互转函数：
string ItS(int num){
string str;
stringstream ss;
ss<<num;
ss>>str;
return str;
}
int StI(string str){
int num;
stringstream ss;
ss<<str;
ss>>num;
return num;
}准备好基本工具后我们来理一下解题思路：先试2个分数的和，再试3个分数的和，再...直到在第n个分数的和找到了我们想要的结果a/b，便解决了最优解条件1，再在这一层中继续寻找别的可能解且不再深入，最后根据最优解条件2排序，输出最优解。
从深度上说，IDDFS中DFS的部分往往需要两个基本参数（now和deep），now是当前的递归深度，deep是最深的递归深度，一旦now=deep则返回，deep+1后再继续，deep则有主函数给出。所以IDDFS的递归思路是从0-1，再0-2，再0-3...直到解决问题。
埃及分数是恒有解问题，这一点在题目中也有暗示（没有impossible的情况），且大部分IDDFS的问题在深度上的无限正体现在这一点上。因此我们不用担心由于深度无限而无法跳出，我们总会找到合适的解，并且事实上它不会在深度上花费太多。
而在广度上，我们需要不断地求和，并记录这些和的结果，运用到下一层的BFS中去，为了简单说明这个问题的思路，我们将算法中位于+号左边的称为“头”，位于+号右边的称为“尾”，作为暴力算法，遍历求和的思路便是将头作为外循环，尾作为内循环，储存求和结果，下面用一个代码解释这个思路：
for(int head=0;head<10;head++){
for(int tail = head+1;tail<10;tail++){
int sum = head + tail;
}
}在IDDFS中，这个head正在自于上一层的BFS中，而这个tail正是当前层的BFS给出的遍历，而sum则是当前层BFS的搜索用元。DFS则在其中但仍传递head的作用，并且决定传递几层。
了解了BFS和DFS再IDDFS中分别担任的角色和它们互相作用的原理关系，接下来我们需要解决能使整个解决过程变得可行，变得不再无穷的核心问题——如何剪枝。
事实上在这里称剪枝或许并不准确，毕竟剪枝是DFS中用于避免无效递归的手段，而在IDDFS中，实际上我们更关注给BFS进行“划界”，使得BFS在一个合理的范围内搜索，剩余的无穷的无效范围是不必要的。
在本题中的“划界”方法是：用递增顺序枚举分数，如果接下来的递归层数（deep-now)全加上目前这个分数(1/n)仍然小于目标值（a/b)，说明剩下的分数枚举是无效的，可以直接结束枚举，划出右界，同时如果当前分数比目标分数大，则同样不需要枚举，划出左界。给出检测函数：
int check(pair<int,int>now, int after, int deep){//after是小于当前枚举分数的最大分数的分母，
pair<int,int> p; //deep为递归深度,同时也是求和宽度
pair<int,int>temp;
p.first = deep; p.second = after;
temp.first = a*(-1); temp.second = b;
if(sum(now,temp).first>0) return 2; //左界以左
p = sum(now,p);
p = sum(p,temp);
return(p.first>=0); //右界以右
}之所以check函数不用bool型而是用int型，是因为需要区分左界以左，右界以右和在范围内三种情况，在住主函数中需要另外处理它们，保证主函数给出的head是左界，使IDDFS效率更高。
有了IDDFS的基础模块check划界后，我们继续解决题目中的具体问题。
首先是记录每个head的加合路径，这个路径将再最后被调用输出，简单写一个字符串函数，同时用map<pair<int,int>,stirng>来储存它们：
string road(string pre, pair<int,int> next){
string str;
str = pre + " + " + ItS(next.first) + "/" + ItS(next.second);
return str;
}另外，在BFS中tail的左值取决于head的road中的最后一个分数，并且如果最后目标值有多解，我们还需要比较它们最后一个分数的大小，所以需要一个提取最后一个分数分母的函数：
int GetStringTail(string str){ //找到分数加和式中的最后一个分母
int num;
string st;
for(string::reverse_iterator it=str.rbegin();it!=str.rend();it++){
if((*it)=='/') break;
st+=(*it);
}
reverse(st.begin(),st.end());
stringstream ss;
ss<<st;
ss>>num;
return num;
}最后还有一些细节：在读入目标分数后，首先进行化简，不然分母是错误的。如果目标分数的分子是1（已经是埃及分数），避免麻烦，直接输出即可。
整合它们！
#include<bits/stdc++.h>
using namespace std;
int a, b;
bool findthedeep;
map<pair<int,int>,string> m;
vector<string> result;
int gcd(int a,int b) //辗转相除法求公约数
{ return b==0 ? a : gcd(b,a%b);}
pair<int,int> sum(pair<int,int> a, pair<int,int> b){
pair<int,int> result;
int c = a.first*b.second+b.first*a.second;
int d = a.second*b.second;
int g = abs(gcd(d,c));
c /= g; d /= g;
result.first = c; result.second = d;
return result;
}
string ItS(int num){
string str;
stringstream ss;
ss<<num;
ss>>str;
return str;
}
int StI(string str){
int num;
stringstream ss;
ss<<str;
ss>>num;
return num;
}
int check(pair<int,int>now, int after, int deep){ //after是小于当前枚举分数的最大分数的分母，
pair<int,int> p; //deep为递归深度,同时也是求和宽度
pair<int,int>temp;
p.first = deep; p.second = after;
temp.first = a*(-1); temp.second = b;
if(sum(now,temp).first>0) return 2;
p = sum(now,p);
p = sum(p,temp);
return(p.first>=0);
}
string road(string pre, pair<int,int> next){
string str;
str = pre + " + " + ItS(next.first) + "/" + ItS(next.second);
return str;
}
int GetStringTail(string str){ //找到分数加和式中的最后一个分母
int num;
string st;
for(string::reverse_iterator it=str.rbegin();it!=str.rend();it++){
if((*it)=='/') break;
st+=(*it);
}
reverse(st.begin(),st.end());
stringstream ss;
ss<<st;
ss>>num;
return num;
}
void IDDFS(pair<int,int> top, int now, int deep){
if(now == deep) return;
queue<pair<int,int>> q;
int k = 0;
int s = GetStringTail(m[top]);
for(int i=s+1;;i++){
if(check(top,i,deep-now) != 1) break;
pair<int,int> num;
num.first = 1; num.second = i;
q.push(num);
k++;
}
pair<int,int> head, next;
while(k--){
head = q.front();
q.pop();
next = sum(top,head);
q.push(next);
m[next] = road(m[top],head);
if(next.first == a && next.second == b){
result.push_back(m[next]);
findthedeep = 1;
}
}
while(!q.empty()){
IDDFS(q.front(),now+1,deep);
q.pop();
}
return;
}
int main(){
cin>>a>>b;
cout<<a<<"/"<<b<<"=";
int c = gcd(a,b);
a /= c; b /= c; //化简
if(a==1){
cout<<a<<"/"<<b;
return 0;
}
queue<pair<int,int>> q;
pair<int,int> top;
for(int i=2;;i++){
for(int t=2;;t++){
top.first = 1; top.second = t;
if(check(top,top.second+1,i) == 0) break;
if(check(top,top.second+1,i) == 2) continue;
q.push(top);
}
while(!q.empty()){
m.clear();
top = q.front();
q.pop();
m[top] = "1/" + ItS(top.second);
IDDFS(top,1,i);
}
if(findthedeep) break;
}
int max = 0;
string res;
for(int i=0;i<result.size();i++){
int num = GetStringTail(result[i]);
if(max>num || max==0){
max = num;
res = result[i];
}
}
cout<<res<<endl;
return 0;
}最后的补充：在IDDFS中，实际上是对DFS和BFS的配合使用，主要分为以下3个要点：
1、BFS：依然是找到核心队列，注意结合DFS的递归深度划分左右界。
2、DFS：依然是找到核心递归，注意逐步加深递归深度。
3、DFS给BFS传递枚举head，BFS负责找到最优解。