網(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ī)劃算法過(guò)于低效在這個(gè)時(shí)候，巧妙的使用貪心思想，將其融入到動(dòng)態(tài)規(guī)劃中，動(dòng)態(tài)規(guī)劃便煥發(fā)出了新的光彩狀態(tài)過(guò)于龐大目錄貪心思想在動(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í)際的解題過(guò)程中，狀態(tài)信息往往是隱含的這個(gè)時(shí)候，合理的運(yùn)用貪心思想，可以迅速的從繁蕪叢雜的問(wèn)題

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

3、總是根據(jù)齊王所出的馬來(lái)分配自己的馬去對(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é)合貪心思想分析問(wèn)題用合理的假設(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)移方程，但是直觀上的算法往往效率不高而貪心歷來(lái)是與高效一詞密不可分的運(yùn)用好貪

5、心思想能夠使原來(lái)效率低下的算法得到重生例四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ù)（走過(guò)一條邊算作一步）樹上的結(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為根的子樹上這種走法沒(méi)有充分發(fā)揮蟲子在這里的作用！例四The Lost H

6、ouse(3+2+4)/3 = 3Worm Said : No!Worm Said : Yes!例四The Lost House不難分析出本題是用樹型動(dòng)態(tài)規(guī)劃來(lái)求解。Fai表示蝸牛的房子在i為根的子樹上的期望步數(shù)和Fbi表示蝸牛的房子不在i為根的子樹上的期望步數(shù)和（也就是遍歷該子樹需要的時(shí)間，如果i處有蟲子，那么Fbi=0）用Leavesi 表示i為根的子樹上葉子節(jié)點(diǎn)的數(shù)目。問(wèn)題的解答就是Fa根結(jié)點(diǎn)/Leaves根結(jié)點(diǎn)。如果結(jié)點(diǎn)u有k個(gè)兒子,我們按照S1.Sk進(jìn)行訪問(wè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的值與訪問(wèn)順序無(wú)關(guān)例四 The Lost House問(wèn)題的關(guān)鍵是如何決定兒子的訪問(wèn)順序一種直觀的方法是枚舉所有可能訪問(wè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)用貪心思想分析問(wèn)題u元素之間存在可比性，且可比性存在著傳遞性，因此可以確定出一個(gè)全序關(guān)系此時(shí)FaS1.k和FbS1.k的值都已知，F(xiàn)au的值待定我們考慮一種訪問(wèn)順序中的兩個(gè)相鄰元素v和v+1小結(jié)2從原始的動(dòng)態(tài)規(guī)劃入