網(wǎng)上找的一些集訓(xùn)隊(duì)集黃勁松

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)例一青蛙的煩惱（詳見論文）例二The Horse Racing優(yōu)化算法例三石子歸并（詳見論文）例四The Lost House貪心思想在動(dòng)態(tài)規(guī)劃中的應(yīng)用一： 確立狀態(tài)動(dòng)態(tài)規(guī)劃當(dāng)中，狀態(tài)的確立是重點(diǎn)而在實(shí)際的解題過程中，狀態(tài)信息往往是隱含的這個(gè)時(shí)候，合理的運(yùn)用貪心思想，可以迅速的從繁蕪叢雜的問題

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

3、總是根據(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í)，單一的貪心策略存在反例光是打平比賽田忌的馬 1 2 3 齊王的馬 1 2 3例二 The Horse Racing收益為0收益為200最強(qiáng)的馬戰(zhàn)平時(shí)，單一的貪心策略存在反例光是輸?shù)舯荣愄锛傻鸟R 2 3 齊王的馬 1 3例二 The Horse Racing收益為200收益為0“田忌出馬不是出最強(qiáng)的，就是出最弱的”用fi,j表示

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

5、心思想能夠使原來效率低下的算法得到重生例四The Lost House蝸牛從根結(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。例四The Lost House(1+4+6)/3 = 11/3蝸牛從根結(jié)點(diǎn)1出發(fā)開始尋找它的房子它的房子可能遺失在葉結(jié)點(diǎn)2、4、5上在結(jié)點(diǎn)3上住著一只蟲子，它會(huì)告訴蝸牛，房子是否在以3為根的子樹上這種走法沒有充分發(fā)揮蟲子在這里的作用！例四The Lost H

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

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