國家集訓(xùn)隊2004論文集 朱晨光

《國家集訓(xùn)隊2004論文集 朱晨光》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、優(yōu)化，再優(yōu)化！——從《鷹蛋》一題淺析對動態(tài)規(guī)劃算法的優(yōu)化安徽省蕪湖市第一中學(xué)朱晨光引言在當(dāng)今的信息學(xué)競賽中，動態(tài)規(guī)劃可以說是一種十分常用的算法。它以其高效性受到大家的青睞。然而，動態(tài)規(guī)劃算法有時也會遇到時間復(fù)雜度過高的問題。因此，要想真正用好用活動態(tài)規(guī)劃，對于它的優(yōu)化方法也是一定要掌握的。本文將就《鷹蛋》這道題目做較為深入的分析，并從中探討優(yōu)化動態(tài)規(guī)劃的本質(zhì)思想與一般方法。問題當(dāng)鷹蛋從第E層樓及以下樓層落下時是不會碎的，但從第（E+1）層樓及以上樓層向下落時會摔碎。有一堆共M個鷹蛋，一位教授想研究這些鷹蛋的堅硬度E。他是通過不斷從一幢N層的樓上向下扔鷹蛋來確定E的。如果鷹蛋未摔碎，還可以繼續(xù)使

2、用；但如果鷹蛋全碎了卻仍未確定E，這顯然是一個失敗的實驗。教授希望實驗是成功的。問題例如：若鷹蛋從第1層樓落下即摔碎，E=0；若鷹蛋從第N層樓落下仍未碎，E=N。這里假設(shè)所有的鷹蛋都具有相同的堅硬度。給定鷹蛋個數(shù)M與樓層數(shù)N(M,N<=1000),求最壞情況下確定E所需要的最少次數(shù)。樣例：M=1，N=10ANS=10（解釋：只能將這個鷹蛋從下往上依次摔）算法一由于是求最優(yōu)值，我們自然想到了使用動態(tài)規(guī)劃！算法一狀態(tài)定義：f(i,j):用i個蛋在j層樓上最壞情況下確定E所需要的最少次數(shù)。狀態(tài)轉(zhuǎn)移：i個鷹蛋(j-w)層(i-1)個鷹蛋(w-1)層i個鷹蛋j層f(i-1,w-1)次f(i,j-w)次算

3、法一狀態(tài)定義：f(i,j):用i個蛋在j層樓上最壞情況下確定E所需要的最少次數(shù)。狀態(tài)轉(zhuǎn)移：f(i,j)=min{max{f(i-1,w-1),f(i,j-w)}+1

4、1<=w<=j}算法一顯然，這個算法的時間復(fù)雜度為O(N3)太高了！如何才能降低它的時間復(fù)雜度呢？算法二經(jīng)過觀察，我們發(fā)現(xiàn)這題很類似于二分查找，只不過是對鷹蛋的個數(shù)有限制。若是對鷹蛋的個數(shù)沒有限制呢？這題就變成求二分查找在最壞情況下的比較次數(shù)！答案即為算法二因此，當(dāng)M>=時，直接輸出即可.算法的時間復(fù)雜度立即降為O(N2log2N)算法二這里，我們是通過減少狀態(tài)總數(shù)而得到了優(yōu)化的空間，從而大大提高了算法效率。這也是優(yōu)化動態(tài)規(guī)劃算法

5、的一種常用方法。然而優(yōu)化還遠(yuǎn)未結(jié)束！算法三經(jīng)觀察發(fā)現(xiàn)，動態(tài)規(guī)劃函數(shù)f(i,j)具有如下單調(diào)性：f(i,j)>=f(i,j-1)(j>=1)這條性質(zhì)可以用數(shù)學(xué)歸納法進(jìn)行證明，這里就從略了。那么，f(i,j)的單調(diào)性有什么作用呢？算法三（如圖，令①為f(i-1,w-1)的圖象，②為f(i,j-w)的圖象,③即為max{f(i-1,w-1),f(i,j-w)}+1的圖象）算法三這樣，我們就成功地將狀態(tài)轉(zhuǎn)移的時間復(fù)雜度降為O(log2N)，算法的時間復(fù)雜度也隨之降為O(N(log2N)2).在對算法三進(jìn)行研究之后，我們會萌生一個想法：既然現(xiàn)在f(i,j)都需要求出，要想找到更高效的算法就只能從狀態(tài)轉(zhuǎn)移

6、入手，因為這一步是O(log2N)，仍然不夠理想。因此，算法四將以狀態(tài)轉(zhuǎn)移為切入點，進(jìn)一步探究優(yōu)化的空間。算法四根據(jù)這個不等式，我們可以得到如下推理：若存在一個決策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通過進(jìn)一步挖掘狀態(tài)轉(zhuǎn)移方程，我們得到如下不等式：f(i,j-1)<=f(i,j)<=f(i,j-1)+1(j>=1)算法四這里，我們設(shè)一指針p，并使p時刻滿足：f(i,p)=f(i,j-1)-1且f(i,p+1)=f(i,j-1)由狀態(tài)轉(zhuǎn)移方程可知，決策時f(i,p)所對應(yīng)的函

7、數(shù)值是f(i-1,j-p-1).下面，我們將證明只需通過判斷f(i,p)與f(i-1,j-p-1)的大小關(guān)系便可以決定f(i,j)的取值。算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1j-1算法四f(i-1)f(i)jjpp+1s大于等于j-1(s=j-p-1)算法四f(i-1)f(i)jjp+1p

8、sj-1算法四f(i-1)f(i)jjpp+1sf(i,j)=f(i,j-1)j-1算法四f(i-1)f(i)jjpp+1s小于f(i-1,s)>f(i,p)=f(i,j-1)-1j-1情況一（p’f(i,j-1)大于等于大于大于等于j-1情況二（p’=p)f(i-1)f(i)jjp+1p’s’j-1