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

《论文--从《鹰蛋》一题浅析对动态规划算法的优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化目录Ø关键字2Ø摘要2Ø正文2n引言2n问题2n分析3u算法一3u算法二4u算法三4u算法四6u小结7u算法五7Ø总结10Ø结束语11第22页共22页优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化关键字优化动态规划模型摘要本文就Ural1223《鹰蛋》这道题目介绍了五种性能各异的算法，并在此基础上总结了优化动态规划算法的本质思想及其一般方法。全文可以分为四个部分。第一部分引言，阐

2、明优化动态规划算法的重要性；第二部分给出本文讨论的题目；第三部分详细讨论这道题目五种不同的动态规划算法，并阐述其中的优化思想；第四部分总结全文，再次说明对于动态规划进行优化的重要性，并分析优化动态规划的本质思想与一般方法。正文引言在当今的信息学竞赛中，动态规划可以说是一种十分常用的算法。它以其高效性受到大家的青睐。然而，动态规划算法有时也会遇到时间复杂度过高的问题。因此，要想真正用好用活动态规划，对于它的优化方法也是一定要掌握的。优化动态规划的方法有许多，例如四边形不等式、斜率优化等。但是这些方法只

3、能对某些特定的动态规划算法进行优化，尚不具有普遍的意义。本文将就《鹰蛋》这道题目做较为深入的分析，并从中探讨优化动态规划的本质思想与一般方法。问题有一堆共M个鹰蛋，一位教授想研究这些鹰蛋的坚硬度E。他是通过不断从一幢N层的楼上向下扔鹰蛋来确定E的。当鹰蛋从第E层楼及以下楼层落下时是不会碎的，但从第（E+1）层楼及以上楼层向下落时会摔碎。如果鹰蛋未摔碎，还可以继续使用；但如果鹰蛋全碎了却仍未确定E，这显然是一个失败的实验。教授希望实验是成功的。例如：若鹰蛋从第1层楼落下即摔碎，E=0；若鹰蛋从第N层楼

4、落下仍未碎，E=N。这里假设所有的鹰蛋都具有相同的坚硬度。给定鹰蛋个数M与楼层数N。要求最坏情况下确定E所需要的最少次数。第22页共22页优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化样例：M=1，N=10ANS=10样例解释：为了不使实验失败，只能将这个鹰蛋按照从一楼到十楼的顺序依次扔下。一旦在第（E+1）层楼摔碎，E便确定了。（假设在第（N+1）层摔鹰蛋会碎）分析算法一图1乍一看这道题，算法并不十分明晰，因为这并不是简单的二分查找，还有对鹰蛋个数的限制。但由于这题是求最优值，我们便自然

5、想到了动态规划。状态定义即为用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

6、,w-1),总次数便为f(i-1,w-1)+1；②鹰蛋没摔碎，此时必有E>=w.我们还能用这i个蛋在上面的（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(

7、i-1,w-1),f(i,j-w)}+1

8、1<=w<=j}①很显然，所需鹰蛋个数必不会大于N，因此当M>N时可令M=N，且并不影响结果。所以这个算法的时间复杂度是O(MN2)=O(N3),空间复杂度是O(N)（可用滚动数组优化）。第22页共22页优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化算法二这个算法的时间复杂度太高，有没有可以优化的余地呢？答案是肯定的。首先，这题很类似于二分查找，即每次根据扔鹰蛋所得信息来决定下一步操作的区间，只不过对鹰蛋碎的次数有限制罢了。假设我们对于鹰蛋的个数不

9、加限制，那么根据判定树的理论有关判定树的理论详情请见参考文献[1]第292~293页。，叶子结点个数共有(n+1)个，（E的取值只可能是0,1,2,…,n共（n+1）种情况），则树的高度至少为+1,即比较次数在最坏情况下需要次。而我们又知道，在n个排好序的数里进行二分查找最坏情况下需要比较次（在这个问题中，若未查找到可视为E=0）。这两点便决定了是下限而且是可以达到的下限。换句话说，对于一个确定的n，任意M所得到的结果均不会小于。一旦M>=,该题就成了求二分查找在最坏