资源描述：
《论文国家队朱晨光》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化安徽省芜湖市第一中学朱晨光目录＞关键字2＞摘要2＞正文2■引言2■问题2■分析3♦算法一3♦算法二4♦算法三4♦算法四6♦小结7♦算法五7＞总结10＞结束语11第1页共22页关键字优化动态规划模型摘要木文就Ural1223《鹰蛋》这道题冃介绍了五种性能各异的算法，并在此基础上总结了优化动态规划算法的本质思想及其一般方法。全文可以分为四个部分。第一部分引言，阐明优化动态规划算法的重要性；第二部分给出本文讨论的题目；第三部分详细讨论这道题冃五种不同的动态规划算法，并阐述其中的优化思
2、想；第四部分总结全文，再次说明对于动态规划进行优化的重要性，并分析优化动态规划的本质思想与般方法。正文引言在当今的信息学竞赛中，动态规划可以说是一种十分常用的算法。它以其高效性受到大家的青睐。然而，动态规划算法有时也会遇到时间复杂度过高的问题。因此，要想真正用好用活动态规划，对于它的优化方法也是一定要掌握的。优化动态规划的方法有许多，例如四边形不等式、斜率优化等。但是这些方法只能对某些特定的动态规划算法进行优化，尚不具有普遍的意义。本文将就《鹰蛋》这道题目做较为深入的分析，并从中探讨优化动态规划的本质思想与一般方法。问题有一堆共M个
3、鹰蛋，一位教授想研究这些鹰蛋的坚硬度Eo他是通过不断从一幢N层的楼上向下扔鹰蛋来确定E的。当鹰蛋从第E层楼及以下楼层落下时是不会碎的，但从第（E+1）层楼及以上楼层向下落时会摔碎。如果鹰蛋未摔碎，还可以继续使用；但如果鹰蛋全碎了却仍未确定E,这显然是一个失败的实验。教授希望实验是成功的。例如：若鷹蛋从第1层楼落下即摔碎，E=0；若鹰蛋从第N层楼落下仍未碎,E=No这里假设所有的鹰蛋都具有相同的坚硬度。给定鹰蛋个数M与楼层数N。要求最坏情况下确定E所需要的最少次数。第2页共22页样例：M=l,N=10ANS=10样例解释：为了不使实验
4、失败，只能将这个鷹蛋按照从一楼到十楼的顺序依次扔卜一旦在第(E+1)层楼摔碎，E便确定了。(假设在第(N+1)层摔鹰蛋会碎)分析算法一乍一看这道题，算法并不十分明晰，因为这并不是简单的二分查找，述有对鹰蛋个数的限制。但由于这题是求最优值，我们便自然想到了动态规划。状态定义即为用i个蛋在j层楼上最坏情况下确定E所需要的最少次数，记为f(i,j)o(j-w)层很显然，当层数为0时f(i,j)=O,即f(i,O)=O(i>=0);当鷹蛋个数为1时，为了不使实验失败，只能从下往上依次扔这个鹰蛋以确定E,即f(lj)=j(j>=0).下面是状
5、态转移：假设我们在第w层扔下鹰蛋，无外乎有两种结果：j层(w・l)层①鹰蛋摔碎了，此时必有Evw,我们便只能用(i-1)个蛋在下面的(w・l)层确定E,并且要求最坏情况卜•次数最少，这是一个子问题，答案为f(i・l,w・l),总次数便为f(i-l,w-l)+l；②鹰蛋没摔碎，此时必有E>二w.我们还能用这i个蛋在上面的(j・w)层确定Eo注意，这里的实验与在第1〜(j・w)层确定E所需次数是一样图1的，因为它们的实验方法与步骤都是相同的，只不过这(j・w)层在上面罢To完全可以把它看成是对第l~(j・w)层进行的操作。因此答案为f(
6、i,j-w),总次数便为f(i,j-w)+lo(如图1)题目要求最坏情况下的最小值，所以这两种情况的答案须取较大值，R又要在所有决策屮取最小值，所以有f(i,j)=min{max{f(i-l,w-l),f(ij-w)}4-lll<=w<=j}①很显然，所需鹰蛋个数必不会大于N,因此当M>N时可令M=N,且并不彫响结果。所以这个算法的时间复杂度是0(MN»=0(N3),宇间复杂度是0(N)(可用滚动数组优化)。-算法二这个算法的时间复杂度太高，有没有可以优化的余地呢？答案是肯定的。首先，这题很类似于二分查找，即每次根据扔鹰蛋所得信息来
7、决定下一步操作的区间，只不过对鹰蛋碎的次数有限制罢了。假设我们对于鹰蛋的个数不加限制，那么根据判定树的理论叶子结点个数共有(n+1)个，E的取值只可能是0丄共(n+1)种情况),则树的高度至少为〔10孕(〃+1)]+1,即比较次数在最坏情况下需要bog2(/2+1)1次。而我们又知道，在n个排好序的数里进行二分杏找最坏情况下需要比较llog2(n+l)l次(在这个问题中，若未查找到可视为E=0)o这两点便决定了Ilog：(n+1)1是下限而且是可以达到的下限。换句话说，对于一个确定的n,任意M所得到的结果均不会小于tlog2(«+1
8、)1o一旦M>=[log2(n+1)],该题就成了求二分查找在最坏情况下的比较次数，可以直接输出bog2(/i+l)1。因此时间复杂度立即降为O(N21og2N).由此可见，对于动态规划的优化是十分必要的。算法二仅通过考察问题自身的性
