您的位置: 首页  >  文章  >  迭代加深、IDDFS解决埃及分数问题

迭代加深、IDDFS解决埃及分数问题

分类: 文章 • 2024-12-25 18:45:46

http://blog.****.net/u014800748/article/details/47376435

迭代加深搜索(IDDFS)的思想

迭代加深搜索一般用来求解状态树“非常深”，甚至深度可能趋于无穷，但是“目标状态浅”的问题。如果用普通的DFS去求解，往往效率不够高。此时我们可以对DFS进行一些改进。最直观的一种办法是增加一个搜索的最大深度限制maxd，一般是从1开始。每次搜索都要在maxd深度之内进行，如果没有找到解，就继续增大maxd，直到成功找到解，然后break。


如下图所示，如果用DFS，需要15步才能找到结点3，但是用迭代加深搜索，很快即可找到结点3。

迭代加深、IDDFS解决埃及分数问题

在使用迭代加深搜索时，通常还要引入一个估价函数h()，来预测从当前深度还有至少多少步才能到达目标状态。假设当前在第cur层，当cur+h(cur)>maxd时候，就说明不论怎么走，都不可能在maxd的限制之内找到目标状态，此时就可以进行“剪枝”操作。这样的和带有估价函数的迭代加深搜索就是IDA*算法。为了更好的理解该算法，下面以“埃及分数”这一经典的例子来作为说明。


埃及分数问题

在古埃及，人们使用单位分数的和（即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(0<a<b<500)，试编程计算最佳表达式。

样例输入：

495 499

样例输出：

Case 1： 495/499=1/2+1/5+1/6+1/8+1/3992+1/14970


问题分析

首先，根据题意可以发现，本题的解答树非常的庞大，不仅深度没有明显的上界，而且在理论上加数的选择也是无限的，即每一层的结点数量也是无限的。这样的话，如果使用普通的BFS，第一层都扩展不完。然而本题要实现两个目标：1.加数的个数尽量少。2.最小的那个分数尽量大，即最大的分母尽量小。


为了实现第一个目标，我们自然想到可以逐一枚举可能的个数，设maxd表示一共有maxd+1个分数相加恰好等于a/b（下标从0开始），按照这样的思路，一定可以找到加数最少的解。


接下来考虑如何实现第二个目标。第二个目标其实是在告诉我们如果存在多解的时候，要更新当前找到的最优解。这里容易犯的一个错误是：找到了解之后立即全部return true。这样的写法只能实现目标1，并没有真正实现目标2。


那么自然会问：那正确的做法是什么？正确的做法应该是找到了一组解后，继续返回上一层继续新的搜索。假设当前已经在第cur层，即0~cur的所有的分母都已经确定了，剩下的分数还需要aa/bb，再假设我们此时需要从分母i>=from的数开始寻找，不难发现，如果(maxd+1-d)*(1/i)≤aa/bb，即剩下的分数全部都为1/i时候，他们的和才刚好等于aa/bb。而实际情况是：分母不允许重复出现，即实际的和肯定小于(maxd+1-d)*(1/i)，这个时候如果i继续增加，(maxd+1-d)*(1/i)只会更小于aa/bb，情况更糟糕，因此在此处应该停止枚举。这样，我们就分析出来了正确的停止搜索的条件：当出现(maxd+1-d)*(1/i)≤aa/bb时，break。


通过以上分析，我们还确定出来了dfs时候的入口参数: cur表示当前在第cur层，from表示第cur层分母的起点， aa表示剩下的分数的分子，bb表示剩下的分数的分母。即dfs(cur,from,aa,bb)。至此，本题的算法的整体框架已经分析完毕了，我们成功地利用IDA*算法解决了这道经典例题。


代码：

[cpp] view plain copy
 print?
  1. #define _CRT_SECURE_NO_WARNINGS  
  2. #include<iostream>  
  3. #include<algorithm>  
  4. #include<string>  
  5. #include<sstream>  
  6. #include<set>  
  7. #include<vector>  
  8. #include<stack>  
  9. #include<map>  
  10. #include<queue>  
  11. #include<deque>  
  12. #include<cstdlib>  
  13. #include<cstdio>  
  14. #include<cstring>  
  15. #include<cmath>  
  16. #include<ctime>  
  17. #include<cctype>  
  18. #include<functional>  
  19. using namespace std;  
  20.   
  21. #define me(s) memset(s,0,sizeof(s))  
  22. #define pb push_back  
  23. typedef long long ll;  
  24. typedef unsigned int uint;  
  25. typedef unsigned long long ull;  
  26. typedef pair <int, int> P;  
  27.   
  28.   
  29.   
  30. int maxd;  
  31. const int N = 1000;  
  32. int ans[N];  
  33. int v[N];  
  34.   
  35. int get_first(int x, int y)//找到第一个小于x/y的单位分数的分母  
  36. {  
  37.     int res = y / x;  
  38.     return res*x >= y ? res : res + 1;  
  39. }  
  40.   
  41. ll gcd(ll a, ll b)  
  42. {  
  43.     return b == 0 ? a : gcd(b, a%b);  
  44. }  
  45.   
  46. bool better(int d)//更新当前的解  
  47. {  
  48.     for (int i = d; i >= 0; i--)//由于分母是由小到大存储的，因此逆序枚举  
  49.     if (v[i] != ans[i])  
  50.         return ans[i] == -1 || v[i]<ans[i];  
  51.     return false;  
  52. }  
  53. bool dfs(int d, int from, ll aa, ll bb)  
  54. {  
  55.     if (d == maxd)  
  56.     {  
  57.         if (bb%aa)return false;//如果不能整除，搜索失败  
  58.         v[d] = bb / aa;        //不要忽略最后一个分母  
  59.         if (better(d))memcpy(ans, v, sizeof(ll)*(d + 1));  
  60.         return true;  
  61.     }  
  62.     bool ok = false;  
  63.     from = max(from, get_first(aa, bb));//更新from这一步容易忽略,假设第d-1个分数的分母是a,第d个分数的分母不一定要从a+1开始，还要考虑1/(a+1)是否小于等于aa/bb  
  64.     for (int i = from;; i++)  
  65.     {  
  66.         if (bb*(maxd + 1 - d) <= i*aa)break;//此处才是正确的停止枚举的条件  
  67.         v[d] = i;//枚举新的分母  
  68.         ll b2 = bb*i;//计算aa/bb-1/i的分子，分母  
  69.         ll a2 = aa*i - bb;  
  70.         ll g = gcd(a2, b2);//计算最大公约数，进行约分  
  71.         if (dfs(d + 1, i + 1, a2 / g, b2 / g))ok = true;//注意，不要写成return true，因为找到一组解并不能当做停止枚举的条件  
  72.     }  
  73.     return ok;//返回从第cur层到maxd层是否成功找到了解，ok一旦为true就一直是true  
  74. }  
  75. int main()  
  76. {  
  77.     int a, b;  
  78.     int rnd = 0;  
  79.     while (~scanf("%d%d", &a, &b))  
  80.     {  
  81.         int ok = 0;  
  82.         for (maxd = 1;; maxd++)//迭代加深搜索的主体框架，maxd要设置为全局变量  
  83.         {  
  84.             memset(ans, -1, sizeof(ans));//开始新一轮搜索时不完整的答案要清空  
  85.             if (dfs(0, get_first(a, b), a, b))  
  86.             {  
  87.                 ok = 1;  
  88.                 break;  
  89.             }  
  90.         }  
  91.         printf("Case %d: %d/%d=", ++rnd, a, b);  
  92.         for (int i = 0; i <= maxd; i++)  
  93.         {  
  94.             if (i)printf("+");  
  95.             printf("1/%d", ans[i]);  
  96.         }  
  97.         printf("\n");  
  98.     }  
  99. } 

相关推荐