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

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

3、總是根據(jù)齊王所出的馬來分配自己的馬去對抗齊王的馬可以假設齊王按照馬的強弱順序由強到弱出馬齊王最強的馬田忌最強的馬用田忌最差的馬去輸給齊王最強的馬輸給能贏用田忌最強的馬去戰(zhàn)勝齊王最強的馬戰(zhàn)平用田忌最強的馬去打平齊王最強的馬或者用田忌最差的馬去輸給齊王最強的馬最強的馬戰(zhàn)平時，單一的貪心策略存在反例光是打平比賽田忌的馬 1 2 3 齊王的馬 1 2 3例二 The Horse Racing收益為0收益為200最強的馬戰(zhàn)平時，單一的貪心策略存在反例光是輸?shù)舯荣愄锛傻鸟R 2 3 齊王的馬 1 3例二 The Horse Racing收益為200收益為0“田忌出馬不是出最強的，就是出最弱的”用fi,j表示

4、齊王出了i匹較強的馬和田忌的j匹較強的馬，i-j匹較弱的馬比賽之后，田忌所能夠得到的最大盈利。其中gi,j表示齊王和田忌的馬分別按由強到弱的順序排序之后，田忌的第i匹馬和齊王的第j匹馬賽跑所能取得的盈利，勝為200，負為-200，平為0。例二 The Horse RacingO(n2)小結(jié)1拋棄了原本直觀而低效的算法結(jié)合貪心思想分析問題用合理的假設得到了“田忌出馬不是出最強，就是出最弱”的信息因此得知可以用動態(tài)規(guī)劃求解且確立出動規(guī)狀態(tài)貪心思想在動態(tài)規(guī)劃中的應用二： 優(yōu)化算法一些題目雖然容易確立出狀態(tài)以及輕松的寫出狀態(tài)轉(zhuǎn)移方程，但是直觀上的算法往往效率不高而貪心歷來是與高效一詞密不可分的運用好貪

5、心思想能夠使原來效率低下的算法得到重生例四The Lost House蝸牛從根結(jié)點出發(fā)開始尋找它遺失在某個葉子結(jié)點的房子一些中間結(jié)點上住著的蟲子會告訴蝸牛它的房子是否在以這個點為根的子樹上房子遺失在每個葉子結(jié)點的概率都是相等的求蝸牛找到房子的最小數(shù)學期望步數(shù)（走過一條邊算作一步）樹上的結(jié)點個數(shù)n最多為1000，每個結(jié)點的分叉數(shù)k最多為8。例四The Lost House(1+4+6)/3 = 11/3蝸牛從根結(jié)點1出發(fā)開始尋找它的房子它的房子可能遺失在葉結(jié)點2、4、5上在結(jié)點3上住著一只蟲子，它會告訴蝸牛，房子是否在以3為根的子樹上這種走法沒有充分發(fā)揮蟲子在這里的作用！例四The Lost H

6、ouse(3+2+4)/3 = 3Worm Said : No!Worm Said : Yes!例四The Lost House不難分析出本題是用樹型動態(tài)規(guī)劃來求解。Fai表示蝸牛的房子在i為根的子樹上的期望步數(shù)和Fbi表示蝸牛的房子不在i為根的子樹上的期望步數(shù)和（也就是遍歷該子樹需要的時間，如果i處有蟲子，那么Fbi=0）用Leavesi 表示i為根的子樹上葉子節(jié)點的數(shù)目。問題的解答就是Fa根結(jié)點/Leaves根結(jié)點。如果結(jié)點u有k個兒子,我們按照S1.Sk進行訪問，F(xiàn)au的計算方式是：Fau = 0; Fbu = 0;for i = 1 to k dobegin Fau = Fau + (

7、Fbu + 1) LeavesSi + FaSi; Fbu = Fbu + FbSi + 2;end;Fbu的值與訪問順序無關例四 The Lost House問題的關鍵是如何決定兒子的訪問順序一種直觀的方法是枚舉所有可能訪問順序，復雜度是O(nk!)，實在是很低效上述算法存在冗余, 我們再用一次動態(tài)規(guī)劃的話，可以將復雜度降為O(n2kk)，勉強可以接受了另一個結(jié)論：如果A一定放在B前，B一定放在C前，可以推導出A一定放在C前。例四 The Lost House對交換前后的Fau值做差這只跟元素v和v+1本身的信息有關！因此如果交換后的值優(yōu)秀的話，那么v+1一定放在v的前面O(nklog2k)12kvv+1。運用貪心思想分析問題u元素之間存在可比性，且可比性存在著傳遞性，因此可以確定出一個全序關系此時FaS1.k和FbS1.k的值都已知，F(xiàn)au的值待定我們考慮一種訪問順序中的兩個相鄰元素v和v+1小結(jié)2從原始的動態(tài)規(guī)劃入