题目:EOJ1154 CAN YOU DFS?  IDA*搜索算法

Description
在古埃及，人们使用单位分数的和(形如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(0〈a〈b〈1000)。

Output
每组测试数据若干个数，自小到大排列，依次是单位分数的分母。输出字典序最小的一组解。

Sample Input
19 45

Sample Output
5 6 18

题目分析：题意给出一个真分数，将它拆成若干个数分之一的形式。要求优先级如下：1，分数个数尽量少。2，最后一个分数的分母尽量大。3，分母字典序尽量小。

主要思路：按字典序搜索所有情况，若能够组合出所求分数，且最后一位分母更小，则更新答案。

这题主要难点是搜索边际的确定……一个数可以拆分成无数个数。又因为要求分数个数尽量少，所以可以每次限制搜索深度，逐渐增加搜索深度，知道找到答案。这就是迭代加深的搜索思想。

同时要求分母逐渐变大，即分数逐渐变小，若后面的分数均无限接近当前最后一个分数却任然无法在规定深度内搜索到正确答案时，就要进行剪枝，这就是A*算法的思想。

这题要综合上述两种思想。

归纳一下，IDA*的基本思路是：首先将初始状态结点的H值设为阈值maxH，然后进行深度优先搜索，搜索过程中忽略所有H值大于maxH的结点；如果没有找到解，则加大阈值maxH，再重复上述搜索，直到找到一个解。在保证H值的计算满足A*算法的要求下，可以证明找到的这个解一定是最优解

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

using namespace std;

long long ans[1500],v[1500];

int maxd;

long long gcd(long long a,long longb){       //求gcd用于约分化简

   return !b?a:gcd(b,a%b);

}

long long get_first(long long a,long long b){  //求拼b分之a时，第一个分数的最大值，分母最小值

   long long c=b/a;

   if(b%a) ++c;

   return c;

}

bool dfs(long long a,long long b,long longfrom,int deep){

   if(deep==maxd){   //达到规定最大搜索深度，结束当前搜索

       if(a!=1)

           return false;

       v[deep]=b;

       if(v[deep]<ans[deep] || ans[deep]==-1)          //判断是否更优解

           memcpy(ans,v,sizeof(long long)*(deep+2));

       return true;

    }

   bool ok=false;

   for(int i=from;;++i){

       if((maxd-deep+1)*b<=a*i) break;//无法在当前规定深度内找到解，剪枝，A*算法的思想

       v[deep]=i;

       long long aa=a*i-b,bb=b*i;

       int c=gcd(aa,bb);

       aa/=c;bb/=c;

       from=max((long long)(i+1),get_first(aa,bb));//下次搜索的起点

       if(dfs(aa,bb,from,deep+1)) ok=true;

    }

   return ok;

}

int main()

{

   long long a,b;

   while(~scanf("%I64d%I64d",&a,&b)){

       long long c=gcd(a,b);

       a/=c;b/=c;

       for(maxd=1;;++maxd){            //逐渐增加递归深度，迭代加深

           memset(ans,-1,sizeof(ans));

           if(dfs(a,b,get_first(a,b),1)){

                for(int i=1;i<=maxd;++i){

                    if(i>1) printf("");

                   printf("%I64d",ans[i]);

                }

                printf("\n");

                break;

           }

       }

    }

   return 0;

}

EOJ1154 CAN YOU DFS? IDA*搜索算法