論文國(guó)家隊(duì)朱晨光

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

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

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

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

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

5、態(tài)轉(zhuǎn)移：假設(shè)我們?cè)诘趙層扔下鷹蛋，無(wú)外乎有兩種結(jié)果：j層(w?l)層①鷹蛋摔碎了，此時(shí)必有Evw,我們便只能用(i-1)個(gè)蛋在下面的(w?l)層確定E,并且要求最壞情況卜?次數(shù)最少，這是一個(gè)子問(wèn)題，答案為f(i?l,w?l),總次數(shù)便為f(i-l,w-l)+l；②鷹蛋沒(méi)摔碎，此時(shí)必有E>二w.我們還能用這i個(gè)蛋在上面的(j?w)層確定Eo注意，這里的實(shí)驗(yàn)與在第1?(j?w)層確定E所需次數(shù)是一樣圖1的，因?yàn)樗鼈兊膶?shí)驗(yàn)方法與步驟都是相同的，只不過(guò)這(j?w)層在上面罷To完全可以把它看成是對(duì)第l~(j?w)層進(jìn)行的操作。因此答案為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}①很顯然，所需鷹蛋個(gè)數(shù)必不會(huì)大于N,因此當(dāng)M>N時(shí)可令M=N,且并不彫響結(jié)果。所以這個(gè)算法的時(shí)間復(fù)雜度是0(MN?=0(N3),宇間復(fù)雜度是0(N)(可用滾動(dòng)數(shù)組優(yōu)化)。-算法二這個(gè)算法的時(shí)間復(fù)雜度太高，有沒(méi)有可以優(yōu)化的余地呢？答案是肯定的。首先，這題很類似于二分查找，即每次根據(jù)扔鷹蛋所得信息來(lái)

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

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