首先我们先来上一下这个东西的概念
IDA*算法就是基于迭代加深的A_star算法
——摘自百度百科
此算法的优势，主要是改成了深度优先的方式，与A比起来，IDA更实用：1.不需要判重，不需要排序；2.空间需求减少。
最典型的应用就是八数码问题和十五数码问题。
上面这一条我还是真的没有看出来！
毕竟是百度百科说的，还是信一信吧！
题目链接：
P1379 八数码难题
这道题还是比较基础的，但是里面的stl的map用的非常妙，不懂的可以自行百科，我对这篇代码就不重点讲解了。
代码如下：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL ch,d[10]={100000000,10000000,1000000,100000,10000,1000,100,10,1};
int dirx[5]={0,0,0,-1,1};
int diry[5]={0,1,-1,0,0};
queue<LL> q;
map<LL,LL> m;
int c[4][4];
void change(int &x,int &y,LL a)
{
c[1][1]=(a/d[0])%10;c[1][2]=(a/d[1])%10;c[1][3]=(a/d[2])%10;
c[2][1]=(a/d[3])%10;c[2][2]=(a/d[4])%10;c[2][3]=(a/d[5])%10;
c[3][1]=(a/d[6])%10;c[3][2]=(a/d[7])%10;c[3][3]=(a/d[8])%10;
for(int i=1;i<=3;++i)for(int j=1;j<=3;++j)if(!c[i][j]) x=i,y=j;
}
LL rechange()
{
LL sum=0;
for(int i=1;i<=3;++i)
for(int j=1;j<=3;++j)
sum=sum*10+c[i][j];
return sum;
}
int main()
{
scanf("%lld",&ch);m[ch]=0;
q.push(ch);
while(!q.empty())
{
LL now=q.front();q.pop();
if(now==123804765) {printf("%lld",m[now]);break;}
else
{
int x0,y0;
change(x0,y0,now);
for(int i=1;i<=4;++i)
{
int nx=x0+dirx[i],ny=y0+diry[i];
if(nx>3||ny>3||nx<1||ny<1) continue;
swap(c[x0][y0],c[nx][ny]);
int re=rechange();
if(!m.count(re))
{
m[re]=m[now]+1;//map去重的同时顺便统计到达这个状态所需的步数
q.push(re);
}
swap(c[x0][y0],c[nx][ny]);
}
}
}
return 0;
}
其实最典型的IDA*
（迭代加深）搜索就要数这道题了——埃及分数
其实代码还是非常好理解的，我们这里的大概思路就是，我们先枚举搜索树的深度，从小到大，开始搜索我们按照只比原分数小一点的分数（但是必须保证分子为0）开始搜，然后依次递归，若有更优解就更新，然后就完了。
AC代码如下：
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int maxd;
long long v[1005],ans[1005];
long long a,b;
long long get_first(long long a,long long b)
{
return b/a+1;
}
bool better(int d){
/*
for(int i=d;i>=0;i--)
if(v[i] != ans[i])
return ans[i] == -1 || v[i] < ans[i];
return false;
*/
return ans[d]==-1 || v[d]<ans[d];//若最小的是一样的，那么我们以第一次搜索出来的答案为准
}
bool dfs(int d,int from,long long fz,long long fm)
{
if(d==maxd)
{
if(fz!=1) return false;
v[d]=fm;
if(better(d)) memcpy(ans,v,sizeof(long long )*(d+1));
return true;
}
from=max((long long )from,get_first(fz,fm));
bool ok=false;
while(true)
{
if(fm*(maxd+1-d)<=from*fz) break;
v[d]=from;
long long b2 = fm*from;
long long a2 = fz*from - fm;
long long g = __gcd(a2,b2);
if(dfs(d+1,from+1,a2/g,b2/g)){ok=true;}
from++;
}
return ok;
}
int main()
{
scanf("%lld%lld",&a,&b);
int c=__gcd(a,b);
a/=c;b/=c;
if(a==1){printf("%lld",b);return 0;}
while(maxd<=10)
{
maxd++;
memset(ans,-1,sizeof(ans));
if(dfs(0,get_first(a,b),a,b))
{
for(int i=0;i<=maxd;++i)
printf("%lld ",ans[i]);
break;
}
}
}
By njc