論文國家隊朱晨光

《論文國家隊朱晨光》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在工程資料-天天文庫。

1、優(yōu)化，再優(yōu)化！——從《鷹蛋》一題淺析對動態(tài)規(guī)劃算法的優(yōu)化安徽省蕪湖市第一中學朱晨光目錄＞關鍵字2＞摘要2＞正文2■引言2■問題2■分析3?算法一3?算法二4?算法三4?算法四6?小結7?算法五7＞總結10＞結束語11第1頁共22頁關鍵字優(yōu)化動態(tài)規(guī)劃模型摘要木文就Ural1223《鷹蛋》這道題冃介紹了五種性能各異的算法，并在此基礎上總結了優(yōu)化動態(tài)規(guī)劃算法的本質思想及其一般方法。全文可以分為四個部分。第一部分引言，闡明優(yōu)化動態(tài)規(guī)劃算法的重要性；第二部分給出本文討論的題目；第三部分詳細討論這道題冃五種不同的動態(tài)規(guī)劃算法，并闡述其中的優(yōu)化思

2、想；第四部分總結全文，再次說明對于動態(tài)規(guī)劃進行優(yōu)化的重要性，并分析優(yōu)化動態(tài)規(guī)劃的本質思想與般方法。正文引言在當今的信息學競賽中，動態(tài)規(guī)劃可以說是一種十分常用的算法。它以其高效性受到大家的青睞。然而，動態(tài)規(guī)劃算法有時也會遇到時間復雜度過高的問題。因此，要想真正用好用活動態(tài)規(guī)劃，對于它的優(yōu)化方法也是一定要掌握的。優(yōu)化動態(tài)規(guī)劃的方法有許多，例如四邊形不等式、斜率優(yōu)化等。但是這些方法只能對某些特定的動態(tài)規(guī)劃算法進行優(yōu)化，尚不具有普遍的意義。本文將就《鷹蛋》這道題目做較為深入的分析，并從中探討優(yōu)化動態(tài)規(guī)劃的本質思想與一般方法。問題有一堆共M個

3、鷹蛋，一位教授想研究這些鷹蛋的堅硬度Eo他是通過不斷從一幢N層的樓上向下扔鷹蛋來確定E的。當鷹蛋從第E層樓及以下樓層落下時是不會碎的，但從第（E+1）層樓及以上樓層向下落時會摔碎。如果鷹蛋未摔碎，還可以繼續(xù)使用；但如果鷹蛋全碎了卻仍未確定E,這顯然是一個失敗的實驗。教授希望實驗是成功的。例如：若鷹蛋從第1層樓落下即摔碎，E=0；若鷹蛋從第N層樓落下仍未碎,E=No這里假設所有的鷹蛋都具有相同的堅硬度。給定鷹蛋個數(shù)M與樓層數(shù)N。要求最壞情況下確定E所需要的最少次數(shù)。第2頁共22頁樣例：M=l,N=10ANS=10樣例解釋：為了不使實驗

4、失敗，只能將這個鷹蛋按照從一樓到十樓的順序依次扔卜一旦在第(E+1)層樓摔碎，E便確定了。(假設在第(N+1)層摔鷹蛋會碎)分析算法一乍一看這道題，算法并不十分明晰，因為這并不是簡單的二分查找，述有對鷹蛋個數(shù)的限制。但由于這題是求最優(yōu)值，我們便自然想到了動態(tài)規(guī)劃。狀態(tài)定義即為用i個蛋在j層樓上最壞情況下確定E所需要的最少次數(shù)，記為f(i,j)o(j-w)層很顯然，當層數(shù)為0時f(i,j)=O,即f(i,O)=O(i>=0);當鷹蛋個數(shù)為1時，為了不使實驗失敗，只能從下往上依次扔這個鷹蛋以確定E,即f(lj)=j(j>=0).下面是狀

5、態(tài)轉移：假設我們在第w層扔下鷹蛋，無外乎有兩種結果：j層(w?l)層①鷹蛋摔碎了，此時必有Evw,我們便只能用(i-1)個蛋在下面的(w?l)層確定E,并且要求最壞情況卜?次數(shù)最少，這是一個子問題，答案為f(i?l,w?l),總次數(shù)便為f(i-l,w-l)+l；②鷹蛋沒摔碎，此時必有E>二w.我們還能用這i個蛋在上面的(j?w)層確定Eo注意，這里的實驗與在第1?(j?w)層確定E所需次數(shù)是一樣圖1的，因為它們的實驗方法與步驟都是相同的，只不過這(j?w)層在上面罷To完全可以把它看成是對第l~(j?w)層進行的操作。因此答案為f(

6、i,j-w),總次數(shù)便為f(i,j-w)+lo(如圖1)題目要求最壞情況下的最小值，所以這兩種情況的答案須取較大值，R又要在所有決策屮取最小值，所以有f(i,j)=min{max{f(i-l,w-l),f(ij-w)}4-lll<=w<=j}①很顯然，所需鷹蛋個數(shù)必不會大于N,因此當M>N時可令M=N,且并不彫響結果。所以這個算法的時間復雜度是0(MN?=0(N3),宇間復雜度是0(N)(可用滾動數(shù)組優(yōu)化)。-算法二這個算法的時間復雜度太高，有沒有可以優(yōu)化的余地呢？答案是肯定的。首先，這題很類似于二分查找，即每次根據(jù)扔鷹蛋所得信息來

7、決定下一步操作的區(qū)間，只不過對鷹蛋碎的次數(shù)有限制罷了。假設我們對于鷹蛋的個數(shù)不加限制，那么根據(jù)判定樹的理論葉子結點個數(shù)共有(n+1)個，E的取值只可能是0丄共(n+1)種情況),則樹的高度至少為〔10孕(〃+1)]+1,即比較次數(shù)在最壞情況下需要bog2(/2+1)1次。而我們又知道，在n個排好序的數(shù)里進行二分杏找最壞情況下需要比較llog2(n+l)l次(在這個問題中，若未查找到可視為E=0)o這兩點便決定了Ilog：(n+1)1是下限而且是可以達到的下限。換句話說，對于一個確定的n,任意M所得到的結果均不會小于tlog2(?+1

8、)1o一旦M>=[log2(n+1)],該題就成了求二分查找在最壞情況下的比較次數(shù)，可以直接輸出bog2(/i+l)1。因此時間復雜度立即降為O(N21og2N).由此可見，對于動態(tài)規(guī)劃的優(yōu)化是十分必要的。算法二僅通過考察問題自身的性