國家集訓(xùn)隊(duì)2006論文集 黃勁松

《國家集訓(xùn)隊(duì)2006論文集 黃勁松》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、貪婪的動(dòng)態(tài)規(guī)劃——淺談貪心思想在動(dòng)態(tài)規(guī)劃中的應(yīng)用紹興縣柯橋中學(xué)黃勁松引言轉(zhuǎn)移困難在動(dòng)態(tài)規(guī)劃的解題中我們面臨著兩大困難1、不知道是否可以用動(dòng)態(tài)規(guī)劃求解2、直觀的動(dòng)態(tài)規(guī)劃算法過于低效在這個(gè)時(shí)候，巧妙的使用貪心思想，將其融入到動(dòng)態(tài)規(guī)劃中，動(dòng)態(tài)規(guī)劃便煥發(fā)出了新的光彩狀態(tài)過于龐大目錄貪心思想在動(dòng)態(tài)規(guī)劃中的應(yīng)用確立狀態(tài)[例一]青蛙的煩惱（詳見論文）[例二]TheHorseRacing優(yōu)化算法[例三]石子歸并（詳見論文）[例四]TheLostHouse貪心思想在動(dòng)態(tài)規(guī)劃中的應(yīng)用一：確立狀態(tài)動(dòng)態(tài)規(guī)劃當(dāng)中，狀態(tài)的確立是重點(diǎn)而在實(shí)際的解題過程中，狀態(tài)信息往往是隱含的

2、這個(gè)時(shí)候，合理的運(yùn)用貪心思想，可以迅速的從繁蕪叢雜的問題背景中巧妙地抽象出狀態(tài)[例二]TheHorseRacing齊王和田忌各派出N匹馬（N≤2000）每匹馬都有一個(gè)固定的速度值每場(chǎng)比賽，輸?shù)囊环綄⒁o贏的一方200兩黃金，如果是平局的話，雙方都不必拿出錢請(qǐng)你扮演一下孫臏，幫助田忌贏最多的錢時(shí)間復(fù)雜度過大，無法滿足要求[例二]TheHorseRacing這個(gè)問題很顯然可以轉(zhuǎn)化成一個(gè)二分圖最佳匹配的問題把田忌的馬放左邊，把齊王的馬放右邊如果田忌的馬勝，則連一條權(quán)為200的邊；如果平局，則連一條權(quán)為0的邊；如果輸，則連一條權(quán)為-200的邊。田忌齊王2

3、000-200[例二]TheHorseRacing運(yùn)用貪心思想分析問題：田忌掌握有比賽的“主動(dòng)權(quán)”，他總是根據(jù)齊王所出的馬來分配自己的馬去對(duì)抗齊王的馬可以假設(shè)齊王按照馬的強(qiáng)弱順序由強(qiáng)到弱出馬齊王最強(qiáng)的馬田忌最強(qiáng)的馬用田忌最差的馬去輸給齊王最強(qiáng)的馬輸給能贏用田忌最強(qiáng)的馬去戰(zhàn)勝齊王最強(qiáng)的馬戰(zhàn)平用田忌最強(qiáng)的馬去打平齊王最強(qiáng)的馬或者用田忌最差的馬去輸給齊王最強(qiáng)的馬最強(qiáng)的馬戰(zhàn)平時(shí)，單一的貪心策略存在反例光是打平比賽田忌的馬123齊王的馬123[例二]TheHorseRacing收益為0收益為200最強(qiáng)的馬戰(zhàn)平時(shí)，單一的貪心策略存在反例光是輸?shù)舯荣愄锛傻鸟R2

4、3齊王的馬13[例二]TheHorseRacing收益為200收益為0“田忌出馬不是出最強(qiáng)的，就是出最弱的”用f[i,j]表示齊王出了i匹較強(qiáng)的馬和田忌的j匹較強(qiáng)的馬，i-j匹較弱的馬比賽之后，田忌所能夠得到的最大盈利。其中g(shù)[i,j]表示齊王和田忌的馬分別按由強(qiáng)到弱的順序排序之后，田忌的第i匹馬和齊王的第j匹馬賽跑所能取得的盈利，勝為200，負(fù)為-200，平為0。[例二]TheHorseRacingO(n2)小結(jié)1拋棄了原本直觀而低效的算法結(jié)合貪心思想分析問題用合理的假設(shè)得到了“田忌出馬不是出最強(qiáng)，就是出最弱”的信息因此得知可以用動(dòng)態(tài)規(guī)劃求解且

5、確立出動(dòng)規(guī)狀態(tài)貪心思想在動(dòng)態(tài)規(guī)劃中的應(yīng)用二：優(yōu)化算法一些題目雖然容易確立出狀態(tài)以及輕松的寫出狀態(tài)轉(zhuǎn)移方程，但是直觀上的算法往往效率不高而貪心歷來是與高效一詞密不可分的運(yùn)用好貪心思想能夠使原來效率低下的算法得到重生[例四]TheLostHouse蝸牛從根結(jié)點(diǎn)出發(fā)開始尋找它遺失在某個(gè)葉子結(jié)點(diǎn)的房子一些中間結(jié)點(diǎn)上住著的蟲子會(huì)告訴蝸牛它的房子是否在以這個(gè)點(diǎn)為根的子樹上房子遺失在每個(gè)葉子結(jié)點(diǎn)的概率都是相等的求蝸牛找到房子的最小數(shù)學(xué)期望步數(shù)（走過一條邊算作一步）樹上的結(jié)點(diǎn)個(gè)數(shù)n最多為1000，每個(gè)結(jié)點(diǎn)的分叉數(shù)k最多為8。[例四]TheLostHouse(1+

6、4+6)/3=11/3蝸牛從根結(jié)點(diǎn)1出發(fā)開始尋找它的房子它的房子可能遺失在葉結(jié)點(diǎn)2、4、5上在結(jié)點(diǎn)3上住著一只蟲子，它會(huì)告訴蝸牛，房子是否在以3為根的子樹上這種走法沒有充分發(fā)揮蟲子在這里的作用！[例四]TheLostHouse(3+2+4)/3=3WormSaid:No!WormSaid:Yes![例四]TheLostHouse不難分析出本題是用樹型動(dòng)態(tài)規(guī)劃來求解。Fa[i]表示蝸牛的房子在i為根的子樹上的期望步數(shù)和Fb[i]表示蝸牛的房子不在i為根的子樹上的期望步數(shù)和（也就是遍歷該子樹需要的時(shí)間，如果i處有蟲子，那么Fb[i]=0）用Leave

7、s[i]表示i為根的子樹上葉子節(jié)點(diǎn)的數(shù)目。問題的解答就是Fa[根結(jié)點(diǎn)]/Leaves[根結(jié)點(diǎn)]。如果結(jié)點(diǎn)u有k個(gè)兒子,我們按照S[1]..S[k]進(jìn)行訪問，F(xiàn)a[u]的計(jì)算方式是：Fa[u]=0;Fb[u]=0;fori=1tokdobeginFa[u]=Fa[u]+(Fb[u]+1)×Leaves[S[i]]+Fa[S[i]];Fb[u]=Fb[u]+Fb[S[i]]+2;end;Fb[u]的值與訪問順序無關(guān)[例四]TheLostHouse問題的關(guān)鍵是如何決定兒子的訪問順序一種直觀的方法是枚舉所有可能訪問順序，復(fù)雜度是O(nk!)，實(shí)在是很低效

8、上述算法存在冗余,我們?cè)儆靡淮蝿?dòng)態(tài)規(guī)劃的話，可以將復(fù)雜度降為O(n2kk)，勉強(qiáng)可以接受了另一個(gè)結(jié)論：如果A一定放在B前，B一定放在C前