算法合集之《从《鹰蛋》一题浅析对动态规划算法的优化》.ppt
《算法合集之《从《鹰蛋》一题浅析对动态规划算法的优化》.ppt》由会员分享,可在线阅读,更多相关《算法合集之《从《鹰蛋》一题浅析对动态规划算法的优化》.ppt(45页珍藏版)》请在三一文库上搜索。
1、优化,再优化!,从鹰蛋一题浅析对动态规划算法的优化,安徽省芜湖市第一中学 朱晨光,引言,在当今的信息学竞赛中,动态规划可以说是一种十分常用的算法。它以其高效性受到大家的青睐。然而,动态规划算法有时也会遇到时间复杂度过高的问题。因此,要想真正用好用活动态规划,对于它的优化方法也是一定要掌握的。,本文将就鹰蛋这道题目做较为深入的分析,并从中探讨优化动态规划的本质思想与一般方法。,问题,当鹰蛋从第E层楼及以下楼层落下时是不会碎的,但从第(E+1)层楼及以上楼层向下落时会摔碎。,有一堆共M个鹰蛋,一位教授想研究这些鹰蛋的坚硬度E。他是通过不断从一幢N层的楼上向下扔鹰蛋来确定E的。,如果鹰蛋未摔碎,还可
2、以继续使用;但如果鹰蛋全碎了却仍未确定E,这显然是一个失败的实验。教授希望实验是成功的。,问题,例如:若鹰蛋从第1层楼落下即摔碎,E=0;若鹰蛋从第N层楼落下仍未碎,E=N。,这里假设所有的鹰蛋都具有相同的坚硬度。给定鹰蛋个数M与楼层数N (M,N=1000) , 求最坏情况下确定E所需要的最少次数。,样例: M=1,N=10 ANS=10 (解释:只能将这个鹰蛋从下往上依次摔),算法一,由于是求最优值,我们自然想到了使用动态规划!,算法一,状态定义:,f(i,j): 用i个蛋在j层楼上最坏情况下确定E所需要的最少次数。,状态转移:,f(i-1,w-1)次,f(i,j-w)次,算法一,状态定义
3、:,f(i,j): 用i个蛋在j层楼上最坏情况下确定E所需要的最少次数。,状态转移:,f(i,j)=minmaxf(i-1,w-1),f(i,j-w)+1|1=w=j,算法一,显然,这个算法的时间复杂度为O(N3),太高了!,如何才能降低它的时间复杂度呢?,算法二,经过观察,我们发现这题很类似于二分查找,只不过是对鹰蛋的个数有限制。,若是对鹰蛋的个数没有限制呢?,这题就变成求二分查找在最坏情况下的比较次数!,答案即为,算法二,因此,当M= 时,直接输出 即可.,算法的时间复杂度立即降为O(N2log2N),算法二,这里,我们是通过减少状态总数而得到了优化的空间,从而大大提高了算法效率。这也是优
4、化动态规划算法的一种常用方法。,然而优化还远未结束!,算法三,经观察发现,动态规划函数f(i,j)具有如下单调性:,f(i,j)=f(i,j-1) (j=1),这条性质可以用数学归纳法进行证明,这里就从略了。,那么,f(i,j)的单调性有什么作用呢?,算法三,(如图,令为f(i-1,w-1)的图象,为f(i,j-w)的图象,即为maxf(i-1,w-1),f(i,j-w)+1的图象),算法三,这样,我们就成功地将状态转移的时间复杂度降为O(log2N) ,算法的时间复杂度也随之降为O(N(log2N)2) .,在对算法三进行研究之后,我们会萌生一个想法:既然现在f(i,j)都需要求出,要想找到
5、更高效的算法就只能从状态转移入手,因为这一步是O(log2N),仍然不够理想。,因此,算法四将以状态转移为切入点,进一步探究优化的空间。,算法四,根据这个不等式,我们可以得到如下推理:,若存在一个决策w使得f(i,j)=f(i,j-1),则f(i,j)=f(i,j-1),若所有决策w均不能使f(i,j)=f(i,j-1),则f(i,j)=f(i,j-1)+1,通过进一步挖掘状态转移方程,我们得到如下不等式:,f(i,j-1)=1),算法四,这里,我们设一指针p,并使p时刻满足:,f(i,p)=f(i,j-1)-1 且 f(i,p+1)=f(i,j-1),由状态转移方程可知,决策时f(i,p)所
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 从【鹰蛋 算法 鹰蛋 浅析 动态 规划 优化
链接地址:https://www.31doc.com/p-2158880.html