论文--从《鹰蛋》一题浅析对动态规划算法的优化.doc

优化,再优化!——从《鹰蛋》一题浅析对动态规划算法的优化目录关键字 2摘要 2正文 2引言 2问题 2分析 3算法一 3算法二 4算法三 4算法四 6小结 7算法五 7总结 10结束语 11关键字优化动态规划模型摘要本文就Ural1223《鹰蛋》这道题目介绍了五种性能各异的算法,并在此基础上总结了优化动态规划算法的本质思想及其一般方法。全文可以分为四个部分。第一部分引言,阐明优化动态规划算法的重要性;第二部分给出本文讨论的题目;第三部分详细讨论这道题目五种不同的动态规划算法,并阐述其中的优化思想;第四部分总结全文,再次说明对于动态规划进行优化的重要性,并分析优化动态规划的本质思想与一般方法。正文引言在当今的信息学竞赛中,动态规划可以说是一种十分常用的算法。它以其高效性受到大家的青睐。然而,动态规划算法有时也会遇到时间复杂度过高的问题。因此,要想真正用好用活动态规划,对于它的优化方法也是一定要掌握的。优化动态规划的方法有许多,例如四边形不等式、斜率优化等。但是这些方法只能对某些特定的动态规划算法进行优化,尚不具有普遍的意义。本文将就《鹰蛋》这道题目做较为深入的分析,并从中探讨优化动态规划的本质思想与一般方法。问题有一堆共M个鹰蛋,一位教授想研究这些鹰蛋的坚硬度E。他是通过不断从一幢N层的楼上向下扔鹰蛋来确定E的。当鹰蛋从第E层楼及以下楼层落下时是不会碎的,但从第(E+1)层楼及以上楼层向下落时会摔碎。如果鹰蛋未摔碎,还可以继续使用;但如果鹰蛋全碎了却仍未确定E,这显然是一个失败的实验。教授希望实验是成功的。例如:若鹰蛋从第1层楼落下即摔碎,E=0;若鹰蛋从第N层楼落下仍未碎,E=N。这里假设所有的鹰蛋都具有相同的坚硬度。给定鹰蛋个数M与楼层数N。要求最坏情况下确定E所需要的最少次数。样例:M=1,N=10ANS=10样例解释:为了不使实验失败,只能将这个鹰蛋按照从一楼到十楼的顺序依次扔下。一旦在第(E+1)层楼摔碎,E便确定了。(假设在第(N+1)层摔鹰蛋会碎)分析算法一图1乍一看这道题,算法并不十分明晰,因为这并不是简单的二分查找,还有对鹰蛋个数的限制。但由于这题是求最优值,我们便自然想到了动态规划。状态定义即为用i个蛋在j层楼上最坏情况下确定E所需要的最少次数,记为f(i,j)。(j-w)层很显然,当层数为0时f(i,j)=0,即f(i,0)=0(i>=0);当鹰蛋个数为1时,为了不使实验失败,只能从下往上依次扔这个鹰蛋以确定E,即f(1,j)=j(j>=0).j层下面是状态转移:假设我们在第w层扔下鹰蛋,无外乎有两种结果:(w-1)层①鹰蛋摔碎了,此时必有E<w,我们便只能用(i-1)个蛋在下面的(w-1)层确定E,并且要求最坏情况下次数最少,这是一个子问题,答案为f(i-1,w-1),总次数便为f(i-1,w-1)+1;②鹰蛋没摔碎,此时必有E>=(j-w)层确定E。注意,这里的实验与在第1~(j-w)层确定E所需次数是一样的,因为它们的实验方法与步骤都是相同的,只不过这(j-w)层在上面罢了。完全可以把它看成是对第1~(j-w)层进行的操作。因此答案为f(i,j-w),总次数便为f(i,j-w)+1。(如图1)题目要求最坏情况下的最小值,所以这两种情况的答案须取较大值,且又要在所有决策中取最小值,所以有f(i,j)=min{max{f(i-1,w-1),f(i,j-w)}+1|1<=w<=j}①很显然,所需鹰蛋个数必不会大于N,因此当M>N时可令M=N,且并不影响结果。所以这个算法的时间复杂度是O(MN2)=O(N3),空间复杂度是O(N)(可用滚动数组优化)。算法二这个算法的时间复杂度太高,有没有可以优化的余地呢?答案是肯定的。首先,这题很类似于二分查找,即每次根据扔鹰蛋所得信息来决定下一步操作的区间,只不过对鹰蛋碎的次数有限制罢了。假设我们对于鹰蛋的个数不加限制,那么根据判定树的理论有关判定树的理论详情请见参考文献[1]第292~293页。,叶子结点个数共有(n+1)个,(E的取值只可能是0,1,2,…,n共(n+1)种情况),则树的高度至少为+1,即比较次数在最坏情况下需要次。而我们又知道,在n个排好序的数里进行二分查找最坏情况下需要比较次(在这个问题中,若未查找到可视为E=0)。这两点便决定了是下限而且是可以达到的下限。换句话说,对于一个确定的n,任意M所得到的结果均不会小于。一旦M>=,该题就成了求二分查找在最坏情况下的比较次数,可以直接输出。因此时间复杂度立即降为O(N2log2N).由此可见,对于动态规划的优化是十分必要的。算法二仅通过考察问题自身的性质便成功地减少了状态总数,从而降低了算法一的时间复杂度,大大提高了算法效率。算法三然而优化还远未结束。经实践证明,M的大小已经