算法合集之从鹰蛋一题浅析对动态规划算法优化学习教案.ppt
引言(ynyn) 在当今的信息学竞赛中，动态规划可以说是一种十分常用的算法(sun f)。它以其高效性受到大家的青睐。然而，动态规划算法(sun f)有时也会遇到时间复杂度过高的问题。因此，要想真正用好用活动态规划，对于它的优化方法也是一定要掌握的。 本文将就鹰蛋这道题目做较为深入的分析(fnx)，并从中探讨优化动态规划的本质思想与一般方法。第1页/共45页第一页，共46页。问题(wnt) 当鹰蛋从第E层楼及以下楼层落下时是不会碎的，但从第（E+1）层楼及以上楼层向下落(xilu)时会摔碎。 有一堆共M个鹰蛋，一位教授想研究这些鹰蛋的坚硬度E。他是通过不断(bdun)从一幢N层的楼上向下扔鹰蛋来确定E的。 如果鹰蛋未摔碎，还可以继续使用；但如果鹰蛋全碎了却仍未确定E，这显然是一个失败的实验。教授希望实验是成功的。第2页/共45页第二页，共46页。问题(wnt) 例如：若鹰蛋从第1层楼(cn lu)落下即摔碎，E=0；若鹰蛋从第N层楼(cn lu)落下仍未碎，E=N。 这里假设所有(suyu)的鹰蛋都具有相同的坚 硬 度 。 给 定 鹰 蛋 个 数 M 与 楼 层 数 N (M,N=1000) , 求最坏情况下确定E所需要的最少次数。样例： M=1，N=10 ANS=10 （解释：只能将这个鹰蛋从下往上依次摔）第3页/共45页第三页，共46页。算法(sun f)一 由于是求最优值，我们(w men)自然想到了使用动态规划！第4页/共45页第四页，共46页。算法(sun f)一状态(zhungti)定义：f(i,j): 用i个蛋在j层楼上最坏情况(qngkung)下确定E所需要的最少次数。 状态转移：i个鹰蛋 (j-w)层(i-1)个鹰蛋 (w-1)层i个鹰蛋 j层f(i-1,w-1)次f(i,j-w)次第5页/共45页第五页，共46页。算法(sun f)一状态(zhungti)定义：f(i,j): 用i个蛋在j层楼上最坏情况下确定E所需要(xyo)的最少次数。 状态转移：f(i,j)=minmaxf(i-1,w-1),f(i,j-w)+1|1=w= 时，直接输出 即可.) 1(log2n) 1(log2n算法(sun f)的时间复杂度立即降为O(N2log2N)第9页/共45页第九页，共46页。算法(sun f)二 这里，我们是通过减少状态总数(zngsh)而得到了优化的空间，从而大大提高了算法效率。这也是优化动态规划算法的一种常用方法。然而(rn r)优化还远未结束！第10页/共45页第十页，共46页。算法(sun f)三经观察发现，动态规划函数f(i,j)具有(jyu)如下单调性：f(i,j)=f(i,j-1) (j=1)这条性质可以用数学归纳法进行(jnxng)证明，这里就从略了。那么，f(i,j)的单调性有什么作用呢？第11页/共45页第十一页，共46页。算法(sun f)三（如图，令为f(i-1,w-1)的图象(t xin)，为f(i,j-w)的图象(t xin),即为maxf(i-1,w-1),f(i,j-w)+1的图象(t xin)） 第12页/共45页第十二页，共46页。算法(sun f)三 这样，我们就成功地将状态(zhungti)转移的时间复杂度降为O(log2N) ，算法的时间复杂度也随之降为O(N(log2N)2) . 在对算法三进行研究之后，我们会萌生一个想法：既然现在f(i,j)都需要求出，要想找到更高效的算法就只能(zh nn)从状态转移入手，因为这一步是O(log2N)，仍然不够理想。 因此，算法四将以状态转移为切入点，进一步探究优化的空间。第13页/共45页第十三页，共46页。算法(sun f)四根据这个不等式，我们可以得到如下(rxi)推理：若存在一个(y )决策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)=f(i,j)=1)第14页/共45页第十四页，共46页。算法(sun f)四这里(zhl)，我们设一指针p，并使p时刻满足：f(i,p)=f(i,j-1)-1 且 f(i,p+1)=f(i,j-1)由状态(zhungti)转移方程可知，决策时f(i,p)所对应的函数值是f(i-1,j-p-1). 下面，我们将证明只需通过判断f(i,p)与f(i-1,j-p-1)的大小关系便可以决定f(i,j)的取值。第15页/共45页第十五页，共46页。算法(sun f)四f(i-1)f(i)jjpp+1j-1第16页/共45页第十六页，共46页。算法(sun f)四f(i-1)f(i)jjpp+1j-1第17页/共45页第十七页，共46页。算法(sun f)四f(i-1)f(i)jjpp+1j-1第18页/共45页第十八页，共46页。算法(sun f)四f(i-1)f(i)jjpp+1j-1第19页/共45页第十九页，共46页。算法(sun f)四f(i-1)f(i)jjpp+1j-1第20页/共45页第二十页，共46页。算法(sun f)四f(i-1)f(i)jjpp+1j-1第21页/共45页第二十一页，共46页。算法(sun f)四f(i-1)f(i)jjpp+1j-1第22页/共45页第二十二页，共46页。算法(sun f)四f(i-1)f(i)jjpp+1j-1第23页/共45页第二十三页，共46页。算法(sun f)四f(i-1)f(i)jjpp+1s大于等于(dngy)j-1(s=j-p-1)第24页/共45页第二十四页，共46页。算法(sun f)四f(i-1)f(i)jjp+1psj-1第25页/共45页第二十五页，共46页。算法(sun f)四f(i-1)f(i)jjpp+1sf(i,j)=f(i,j-1)j-1第26页/共45页第二十六页，共46页。算法(sun f)四f(i-1)f(i)jjpp+1s小于f(i-1,s)f(i,p)=f(i,j-1)-1j-1第27页/共45页第二十七页，共46页。情况(qngkung)一（pf(i,j-1)大于等于(dngy)大于大于等于(dngy)j-1第28页/共45页第二十八页，共46页。情况(qngkung)二（p=p)f(i-1)f(i)jjp+1psj-1maxf(i,p),f(i-1,s)+1f(i,j-1)大于第29页/共45页第二十九页，共46页。情况(qngkung)三（pp)f(i-1)f(i)jjp+1pspsmaxf(i,p),f(i-1,s)+1f(i,j-1)第30页/共45页第三十页，共46页。算法(sun f)四 因此，我们只需根据f(i,p)与f(i-1,j-p-1)的大小关系便可直接确定f(i,j)的取值，从而使状态转移(zhuny)成功地降为O(1),算法的时间复杂度降为O(Nlog2N) 综上所述， 当f(i,p)=f(i-1,j-p-1)时，可以直接得出(d ch)f(i,j)=f(i,j-1); 当f(i,p)=1)状态(zhungti)转移也十分简单。 很显然，无论有多少鹰蛋，若只试1次就只能确定一层楼，即g(1,j)=1 (j=1)g(i,j)=g(i-1,j-1)+g(i-1,j)+1 (i,j1) 第34页/共45页第三十四页，共46页。算法(sun f)五 我们的目标便是(bin sh)找到一个x，使x满足g(x-1,M)=N ，答案即为x. 这个算法乍一看是O(Nlog2N)的，但实际(shj)情况却并非如此。 经过观察，我们很快会发现，函数g(i,j)与组合函数C(i,j)有着惊人的相似，而且可以很容易证明对于任意i,j (i,j=1), 总有g(i,j)= C(i,j).第35页/共45页第三十五页，共46页。算法(sun f)五 这样，我们(w men)可以得到C(x-1,M)=g(x-1,M)1) 第44页/共45页第四十四页，共46页。感谢您的观看(gunkn)！第45页/共45页第四十五页，共46页。NoImage内容(nirng)总结引言。在当今的信息学竞赛中，动态规划可以说是一种十分常用的算法。本文将就鹰蛋这道题目做较为深入的分析，并从中探讨优化动态规划的本质思想(sxing)与一般方法。第1页/共45页。当鹰蛋从第E层楼及以下楼层落下时是不会碎的，但从第（E+1）层楼及以上楼层向下落时会摔碎。他是通过不断从一幢N层的楼上向下扔鹰蛋来确定E的。若鹰蛋从第N层楼落下仍未碎，E=N。样例： M=1，N=10。(s=j-p-1)。情况一（pp)第四十六页，共46页。
