埃及分数问题.docx

1、埃及分数问题埃及分数问题: 在古埃及,人们用单位分数的和(形如1a,a是自然数)表示一切有理数。如:231216,但不允许231313,加数中有相同的。对于一个分数ab,表示方法有很多种,但是哪种最好呢?1. 加数少的比加数多的好2. 加数个数相同的,最小的分数越大越好。如: 1945131121180 194513115145 194513118130 194514161180 19451516118最好的是最后一种即19451516118,因为118比1180、145、130、1180都大。给定两个整数a、b(0ab1000),编程计算出最好的表达方式。本算法出自ACM程序设计与分析P25

2、8。【贪心法】解析: 本算法出自吕国英版算法设计与分析P149(旧),P160(新)。由于书上算法只使用了int类型变量进行计算,而当分数比较大时(如: 0ab1000),那么则会溢出,导致计算结果错误,故此本算法将使用高精度计算进行求解。其算法思想不变,只是在计算时使用高精度计算,这样便可以求出0ab1000范围内的解。根据书中说明,贪心法求解思想是:逐步选择分数所包含的最大埃及分数,这些埃及分数之和就是问题的一个解。但是这样求出的解在决大多数情况下,不是最佳表示法。只是问题的一个解而已。下面我们利用IDA*算法求得问题的最佳解。【IDA*法】解析: 在进行本算法解析之前,我们先分析几个问题

3、。上面我们利用贪心法进行了求解,在贪心法逐步选择当前分数所包含的最大埃及分数时,是按照如下方法计算的,例如:78内所包含的最大埃及分数是什么呢? 78包含最大埃及分数分母8712781238,寻找38内的最大埃及分数如下: 38包含最大埃及分数分母8313得到3813124,此时124已经是埃及分数,则不再进行计算,得到解781213124。这样,我们总结得到每次当前被求解的分数的下界如下:1(当前分数的分母当前分数的分子1)那么上界是什么呢?在进行IDA*算法求解之前,我利用了一般的搜索技术进行了求解,下面先说明一般搜索算法的思想。上面我们可以利用(分母分子1)的方法求得当前分数的下界,由于

4、这个下界是当前分数内所包含的最大埃及分数,那么从当前分数内减掉这个最大埃及分数后,假设得到的一个分数还不是埃及分数,将进入下一层的计算(同样求得下界)。那么这个下界一定是小于上一层的下界值的(原因很简单,分数越减越小),而由于本问题求解的是分数问题,那么逐层下降的下界涉及到分数的分母上则是递增的,例如:1945131121180781213124其解的分母递增。那么要保证其分母递增,其每次的减数则不应超过被减数(即:小于被减数),否则得到的结果是降序的。这样我们得到一个求解上界的方法,下面举例说明: 194513445, 则得到445为下界,那么上界是多少呢?根据上面的分析结果,要保证升序则减

5、数应不超过被减数,而不超过1945的减数是多少呢?我们将1945乘以12即可(例如:被减数为5那么保证升序的结果时,最大减数为2,也就是将5121)。不过这里面还有一个小问题需要说明:1. 当分子是1时则上界是:1(被减数分母21)2. 当分子非1时则上界是:被减数12(通过比较)例如: 194513445,则3215(即:最小将13缩减至15,可以保证升序)将13的分母逐步扩大如下:19451431180(3118015) 19451529(2915)1945162390(239015)下面我们看一下后两种继续计算的结果:194515292915(本层下界)145从而得到一个解1945151

6、5145,但是问题中不允许出现加数相同的解,故这个解是要被舍掉的。再看一下另一个计算结果:1945162390239014(本层下界)1180从而得到一个解194516141180,显然解中出现了降序的分母排列,这个解也要被舍掉(原因是前面我们搜索的升序解时已经出现了一个14161180,而题目中并未对每个加数的出现位置做规定,为了过滤掉重复出现的解,并减少搜索空间,故此我们只按照升序的方向进行搜索,这样就保证了不出现重复的解,及不出现加数重复的解,也不会漏掉解)。上面说明了当分子是1的情况。当分子非1时,我们要将减数12,然后通过比较大小确定是否再进行深度搜索。再看下面的例子: 首先1945

7、13445,然后求得445的下界是12,则有4451121180。得到一个解:1945131121180那么以112为起点的下界的搜索上界是多少呢?我们将445乘以12得到245,而这个245是要通过与每次的减数比较大小而确定是否继续进行深度搜索的(原因是它是分数,且分子非1)。而这个比较还要进行精确计算得到结果(不能用每个分数除得的结果草草比较,这样的比较属于C+中的浮点数比较,是比较忌讳的操作且不准确,可能会出现上界过小而漏掉解的情况)。下面将112的分母逐步扩大如下: 4451137585(7585245) 44511411630(11630245) 445115145(145245解)

8、 44511619720(19720245) 44511723765(23765245) 445118130(130245解) 44511931855(31855245) 4451207180(7180245) 44512113315(13315245) 44512243990(43990245) 445123471035(471035245)当分母增加到23时出现降序,这时我们可以确定不再向下层搜索,而是立刻返回到上层搜索上层剩余未搜索完的部分。那么如何进行分数的比较运算呢?我们知道当两个分数进行相加、减时先要进行通分母的操作,然后才进行分子相加、减得到结果。故设有ABCD则有如下公式: A

9、 C ADBCB D BD通过观察上面公式我们得到当进行减法计算时,一旦出现分子为负数的情况,则表明被减数小于减数,这样通过上述公式进行计算则得到的结果是精确判断。至此,对于分子是1与分子非1的情况阐述完毕。下面我们以1945为例,详细说明一下求解过程: 首先, 1945内所包含的最大埃及分数是13,则用194513445(以13为下界,而上界为15,本层为1层),而445还不是埃及分数,继续找到445内所包含的最大埃及分数是112(以112为下界,以245为上界比较点进行比较,本层为2层),则有4451121180。得到一个解为: 1945131121180。返回到2层,扩大减数分母为13,

10、则有4451137585,而7585还不是埃及分数,但此时如果继续向下搜索的话,其最终结果至少大于已得到的一个解的加数个数3,所以不必继续向下层搜索(这里称为越界,下同)。而是继续第2层未计算完的部分。扩大减数分母为14,则有44511411630(越界)。继续有445115145。得到一个解为: 194513115145。返回2层,扩大分母至16,有44511619720(越界)。继续扩大至17,则44511723765(越界)。继续扩大至18,则445118130。得到一个解为: 194513118130。返回2层,有44511913855(越界)。继续扩大至20,则4451207180(

11、越界)。继续扩大至21,则44512113315(越界)。继续扩大至22,则44512243990(越界)。继续扩大至23,而此时通过比较有245123(已超过2层上界),返回到1层。将13的分母3扩大至4,则有19451431180,继续搜索进入2层,找到31180包含的最大埃及分数是16,则31180161180(下界16,上界以31360比较)。得到一个解为: 194514161180。返回2层,扩大分母为7有3118017371260(越界)。继续扩大至8,则311801817360(越界)。继续扩大至9,则311801911180(越界)。继续扩大至10,则3118011013180

12、(越界)。继续扩大至11,则311801111611980(越界)。继续扩大至12,此时通过比较有31360112(已超过2层上界),返回到1层。将1层的分母4扩大至5,则有19451529,继续搜索进入2层,找到29包含的最大埃及分数是15,则291515(下界15,上界以19比较)。此时,虽然得到了一个解,但是解中出现相同加数,则放弃这个解,返回2层将扩大分母5至6,则有2916118。得到一个解为: 19451516118。返回2层,扩大分母为7则有2917563(越界)。继续扩大至8,则2918772(越界)。继续扩大至9,此时的19与上界相同,则放弃搜索(即:到达上界),返回1层,而

13、1层的分母也已经到达上界5,算法结束。最终找到5个解,其最佳表示法是19451516118,这里可以通过比较最后一个加数的分母大小求得(因为我们是按照升序搜索的,故最后一个加数一定是最小的一个,那么按照题目要求就比较它的分母即可)。上面就是一般搜索算法的求解思想及过程(在这个算法中一并使用高精度计算求解),虽然在算法中计算了上下界(通过上下界进行了范围界定),但是当出现类似998999、13997的分数进行求解时,会由于其每层的上下界之差过大,而反复调用高精度计算进行增量、加、乘等操作。而对于高精度计算我们不可避免的要使用字符串数组存储计算结果,而埃及分数算法中又要涉及到反复的递归计算,这样就

14、不可避免的在每次进入递归口时要使用动态分配字符串空间(即:调用堆空间),而在如上的尖端分数其上下界过大时,又要反复进行递归、返回操作,这就不断的在消耗堆资源(堆空间不象栈空间,它只能在整个算法结束后才释放分配的空间,而栈是随时释放的,算法未结束时下次还可以使用。这就导致了堆被分配后不能被重复利用),最终算法没有结束,而堆空间被耗尽导致算法崩溃(即便将高精度计算中用到的动态分配空间统一提出来作为公共数组使用,那么也不能满足计算0ab1000范围内的埃及分数求解,最终放弃一般搜索方法的代码编制)。以上是对一般搜索算法的分析。那么要满足题目要求的计算范围内求解埃及分数,该采用什么方法呢?下面我们就来

15、探讨IDA*算法进行求解的原理。所谓IDA*算法就是基于迭代加深的A*算法。算法以试探性的递归深度进行搜索,如果当前的试探搜索深度找到了解,那么算法在本次搜索深度完毕后结束,否则就增加一层搜索深度进行搜索,直到找到解并结束于本次搜索深度。下面详细讲解IDA*算法的求解过程: M19、N45开始在Search_IDA函数中置parts1,found0。进入while()循环,由于还没有找到解,那么将parts加1,表示将以2层的搜索深度进行搜索(注:如果1层出现解,那么不会进入到while循环)。接下来进入Decomposition(m,n,Deep)函数(以下简称D()函数)。D(19,45,

16、2)计算得到min3,而max如何计算呢?前面的一般搜索算法我们讲过计算下界时,以分母分子1的方式计算,而计算上界时以不超过本层分数的一半为上界(注:通过计算后的值比较参考是否返回上层)。那么如果此时在IDA*算法中同样用此方法的话,就回出现大量重复的计算(前提是在控制递归深度的同时),故此我们用一种新的方法计算出上界,此方法计算出的上界控制了搜索范围(这个范围是配合当前的递归深度进行的),并减少了大量重复的搜索。那么如何计算呢?我们同样以分母分子求得一个数,由于要配合递归深度,那么我们将这个计算结果乘以递归深度,便可得到其上界值(注:对于代码中的max部分的判断操作,见下面的解析。对于分母分

17、子Deep的计算,为了尽量保证计算精度,我们应采取以Deep分母分子的形式求得)。下面返回讲解处,求得max4,那么本层的上下界为3,4。置Temp13后进入下一层D(12,135,1),由于转到下一层后其分子不为1,则返回到本层。置Temp14后进入下一层D(31,180,1)同样其分子不为1,返回本层。这时本层已到达下界4,退回到Search_IDA()函数中将parts增加为3层搜索深度后重新进入D()函数。(注:在此如果我们按照一般搜索技术的方法求得的上界是5,那么此时就要多计算1次以5为第一层的搜索,同样得不到解)。D(19,45,3)计算本层上下界3,7,Temp23,进入2层D(

18、12,135,2),计算上下界12,22,Temp112,进入3层D(3,540,1),可知nm为1,Temp0180得到一个解:3、12、180,found1。返回到2层Temp113,进入3层D(7,585,1)本次分子不为1返回2层。Temp114,进入3层D(11,630,1)本次分子不为1返回2层。Temp115,进入3层D(15,675,1)得到15整除675为45,Temp045得到解3、15、45,比较解的最后一项45180,则更新最优解为:3、15、45。返回2层Temp116,进入3层D(19,720,1)分子不为1返回2层。Temp117进入3层D(23,765,1)分子

19、不为1返回2层。Temp118进入3层D(27,810,1)27整除810为30得到解:3、18、30,比较末项3045,更新最优解为:3、18、30。返回2层。Temp119进入3层D(31,855,1)分子不为1返回2层。Temp120进入3层D(35,900,1)分子不为1返回2层。Temp121进入3层D(39,945,1)分子不为1返回2层。Temp122进入3层D(43,990,1)分子不为1返回2层。此时2层到达搜索上界,返回1层Temp24进入2层D(31,180,2)计算上下界6,11,Temp16进入3层D(6,1080,1)得到6整除1080为180,Temp0180得到

20、解4、6、180,比较解的最后一项18045,则放弃当前解。返回2层,Temp17进入3层D(37,1260,1)分子不为1返回2层。Temp18进入3层D(68,1440,1)分子不为1返回2层。Temp19进入3层D(99,1620,1)分子不为1返回2层。Temp110进入3层D(130,1800,1)分子不为1返回2层。Temp111进入3层D(161,1980,1)分子不为1返回2层。此时2层到达搜索上界,返回1层Temp25进入2层D(50,225,2) 计算min2255015,而通过判断Deepparts & TempDeep1min成立,这表示当前Deep层被搜索的数非第一层

21、(即:不是第一项值),且已经存储于Temp中的第一项值与此值相等(如:Temp25,而刚刚计算的min5,那么如果按照当前层最小值为5进行搜索的话,就会出现将Temp1置为5则重复出现两个5,违反题意。如果当小于此值时还会出现逆序分母的情况)。故遇到此种情况则将本此下界min改为Temp21即可。最终计算上下界为6,8,Temp16进入3层D(3,54,1)得到3整除54为18,Temp018得到解5、6、18,比较解的最后一项1830,则更新最优解为:5、6、18。返2层,Temp17进入3层D(5,63,1)分子不为1返回2层。Temp18进入3层D(7,72,1)分子不为1返回2层。此时

22、2层到达搜索上界,返回1层。Temp26进入2层D(69,270,2),计算上下界为7,7,Temp17进入3层D(71,630,1)分子不为1,返回2层,2层到达搜索上界,返回1层。Temp27,进入2层D(88,315,2)计算min4,改变min为Temp218(否则出现逆序与重复),max7,由于minmax直接返回1层,此时1层到达搜索上界,算法结束。最终被保留的最佳埃及分数表示法为:5、6、18。对于max的计算问题,按照上面一般搜索技术的方法,第一层最多max为5,当大于5时将出现逆序分母。而本算法当按照3层深度搜索时,计算第一层的max为7,这与一般搜索技术的方法略有出入,但是

23、它并不影响计算结果,且很快就可判断并返回到上层函数中。而对于max部分的判断操作参见下面: 当首层Temp25时,进入第2层D(2,9,2),此时计算max9(判断部分为Deepnm0),而通过对上面讲述的一般搜索方法的求解过程得知,当本层下界为9时,将出现重复分母问题(即:151919)。故将max减1去掉这个出现重复分母的下界值(即:max判断部分的用途)。至此,IDA*算法计算埃及分数的过程讲解完毕。总结: 对于埃及分数这类问题,可以由任意的分数凑成,而对于加数个数(如:1945中的三个加数),也可以有不同大小的分数构成。所以其状态空间是无穷大的,深度搜索的话,就会出现无限递归而没有返回

24、的情况。广度搜索的话,其空间消耗不起。而ID(iterative deepening)的实质就是:使用深搜的框架来写宽搜(即:在dfs搜索算法的基础上逐步加大搜索的深度,它避免了广度优先搜索占用搜索空间太大的缺点,也减少了深度优先搜索的盲目性。那么,总要牺牲一点东西,就是时间,每次加深的工作量是重复的。但是这个重复的工作量,由于搜索的状态空间为指数级增长,可以不记。IDA*算法主要是在递归搜索函数的开头判断当前搜索的深度是否大于预定义的最大搜索深度,如果大于,就退出这一层的搜索,如果不大于,就继续进行搜索。这样最终获得的解必然是最优解。而在A*算法中,我们通过使用合理的估价函数,然后在获得的子

25、节点中选择fCost最小的节点进行扩展,以此完成搜索最优解的目的。但是A*算法中,需要维护关闭列表和开放列表,需要对扩展出来的节点进行检测,忽略已经进入到关闭列表中的节点(也就是所谓的”已经检测过的节点”),另外也要检测是否与待扩展的节点重复,如果重复则进行相应的更新操作。所以A*算法主要的代价花在了状态检测和选择代价最小节点的排序上,这个过程中占用的内存是比较大的,一般为了提高效率都是使用hash进行重复状态检测。IDA*算法综合了A*算法的人工智能性和回溯法对空间消耗较少的优点,在一些规模很大的搜索问题中会起意想不到的效果。它的具体名称是 Iterative Deepening A*,19

26、85年由Korf提出。该算法的最初目的是为了利用深度搜索的优势解决广度A*的空间问题,其代价是会产生重复搜索。归纳一下IDA*的基本思路:首先将初始状态结点的H值设为阈值maxH,然后进行深度优先搜索,搜索过程中忽略所有H值大于maxH的结点;如果没有找到解，则加大阈值maxH,再重复上述搜索,直到找到一个解。在保证H值的计算满足A*算法的要求下,可以证明找到的这个解一定是最优解。在程序实现上,IDA*要比 A*方便,因为不需要保存结点,不需要判重复,也不需要根据 H值对结点排序,占用空间小。在IDA*算法中也要使用合适的估价函数来评估与目标状态的距离。在一般的问题中是这样使用IDA*算法的:当前局面的估价函数值当前的搜索深度预定义的最大搜索深度就进行剪枝。这个估价函数的选取没有统一的标准,找到合适的该函数并不容易(例如:上述IDA*算法在计算max值时可能会出现不准确的情况),但是可以大致按照这个原则在一定范围内加大各个状态启发函数值的差别。【注:对于IDA*算法求解埃及分数时,同样不能用高精度计算,因为它同样会出现过度调用系统资源的问题,最终导致程序崩溃。最终我们选取C+中的unsigned _int64类型变量进行计算(相当于long long类型),它可以满足0ab1000范围内的埃及分数求解问题】