算法合集之淺談貪心思想在動(dòng)態(tài)規(guī)劃中的應(yīng)用學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1算法合集之淺談貪心算法合集之淺談貪心(tnxn)思想在動(dòng)態(tài)規(guī)思想在動(dòng)態(tài)規(guī)劃中的應(yīng)用劃中的應(yīng)用第一頁，共23頁。轉(zhuǎn)移(zhuny)困難p 在動(dòng)態(tài)規(guī)劃的解題中我們面臨著兩大困難在動(dòng)態(tài)規(guī)劃的解題中我們面臨著兩大困難p 1、不知道、不知道(zh do)是否可以用動(dòng)態(tài)規(guī)劃求解是否可以用動(dòng)態(tài)規(guī)劃求解p 2、直觀的動(dòng)態(tài)規(guī)劃算法過于低效、直觀的動(dòng)態(tài)規(guī)劃算法過于低效p 在這個(gè)時(shí)候，巧妙的使用貪心思想，將其融入在這個(gè)時(shí)候，巧妙的使用貪心思想，將其融入到動(dòng)態(tài)規(guī)劃中，動(dòng)態(tài)規(guī)劃便煥發(fā)出了新的光彩到動(dòng)態(tài)規(guī)劃中，動(dòng)態(tài)規(guī)劃便煥發(fā)出了新的光彩狀態(tài)過于龐大第1頁/共22頁第二頁，共23頁。第2頁/共22頁第三頁，共23頁

2、。第3頁/共22頁第四頁，共23頁。第4頁/共22頁第五頁，共23頁。時(shí)間復(fù)雜(fz)度過大，無法滿足要求田忌田忌齊王齊王2000-200第5頁/共22頁第六頁，共23頁。齊王最強(qiáng)的馬田忌最強(qiáng)的馬用田忌最差的馬去輸給齊王最強(qiáng)的馬用田忌最差的馬去輸給齊王最強(qiáng)的馬輸給能贏用田忌最強(qiáng)的馬去戰(zhàn)勝用田忌最強(qiáng)的馬去戰(zhàn)勝(zhnshng)齊齊王最強(qiáng)的馬王最強(qiáng)的馬戰(zhàn)平用田忌最強(qiáng)的馬去打平齊王最強(qiáng)的馬用田忌最強(qiáng)的馬去打平齊王最強(qiáng)的馬或者或者(huzh)用田忌最差的馬去輸給齊王最強(qiáng)的馬用田忌最差的馬去輸給齊王最強(qiáng)的馬第6頁/共22頁第七頁，共23頁。收益(shuy)為0收益(shuy)為200第7頁/共22頁第八

3、頁，共23頁。收益(shuy)為200收益(shuy)為0第8頁/共22頁第九頁，共23頁。igj,1- j1,-fii,1,j)-(i-gnj1,-maxfi jfi,O(n2)第9頁/共22頁第十頁，共23頁。第10頁/共22頁第十一頁，共23頁。第11頁/共22頁第十二頁，共23頁。樹上的結(jié)點(diǎn)樹上的結(jié)點(diǎn)(ji din)個(gè)數(shù)個(gè)數(shù)n最多為最多為1000，每，每個(gè)結(jié)點(diǎn)個(gè)結(jié)點(diǎn)(ji din)的分叉數(shù)的分叉數(shù)k最多為最多為8。第12頁/共22頁第十三頁，共23頁。(1+4+6)/3 = 11/3蝸牛從根結(jié)點(diǎn)蝸牛從根結(jié)點(diǎn)1 1出發(fā)開始尋找出發(fā)開始尋找(xnzho)(xnzho)它的房它的房子子它的房

4、子可能遺失在葉結(jié)點(diǎn)它的房子可能遺失在葉結(jié)點(diǎn)2 2、4 4、5 5上上在結(jié)點(diǎn)在結(jié)點(diǎn)3 3上住著一只蟲子，它會(huì)告訴蝸牛，房子上住著一只蟲子，它會(huì)告訴蝸牛，房子是否在以是否在以3 3為根的子樹上為根的子樹上這種走法沒有充分發(fā)揮蟲子在這里這種走法沒有充分發(fā)揮蟲子在這里(zhl)的的作用！作用！第13頁/共22頁第十四頁，共23頁。(3+2+4)/3 = 3Worm Said : No!Worm Said : Yes!第14頁/共22頁第十五頁，共23頁。 不難分析出本題是用樹型動(dòng)態(tài)規(guī)劃來求解。 Fai表示蝸牛的房子在i為根的子樹上的期望步數(shù)和 Fbi表示蝸牛的房子不在i為根的子樹上的期望步數(shù)和（也就是

5、遍歷該子樹需要的時(shí)間，如果i處有蟲子(chng zi)，那么Fbi=0） 用Leavesi 表示i為根的子樹上葉子節(jié)點(diǎn)的數(shù)目。 問題的解答就是Fa根結(jié)點(diǎn)/Leaves根結(jié)點(diǎn)。如果結(jié)點(diǎn)如果結(jié)點(diǎn)u u有有k k個(gè)兒子個(gè)兒子, ,我們按照我們按照(nzho)S1.Sk(nzho)S1.Sk進(jìn)行訪問，進(jìn)行訪問，F(xiàn)auFau的計(jì)算方式的計(jì)算方式是：是：Fau = 0; Fbu = 0;Fau = 0; Fbu = 0;for i = 1 for i = 1 to to k do k dobeginbegin Fau = Fau + (Fbu + 1) Fau = Fau + (Fbu + 1) Leav

6、esSi + LeavesSi + FaSi;FaSi; Fbu = Fbu + FbSi + 2; Fbu = Fbu + FbSi + 2;end;end; kiijiijSFaSLeavesSFbuFa111) ) 1)2(Fbu的值與訪問的值與訪問(fngwn)順序無關(guān)順序無關(guān)第15頁/共22頁第十六頁，共23頁。第16頁/共22頁第十七頁，共23頁。另一個(gè)結(jié)論：如果另一個(gè)結(jié)論：如果A一定一定(ydng)放在放在B前，前，B一定一定(ydng)放在放在C前，可以推導(dǎo)出前，可以推導(dǎo)出A一定一定(ydng)放在放在C前。前。O(nklog2k)12kvv+1。 運(yùn)用貪心(tnxn)思想分析

7、問題u)2()2(11vvvvSLeavesSFbSLeavesSFb元素之間存在可比性，且可比元素之間存在可比性，且可比性存在著傳遞性，因此可以確性存在著傳遞性，因此可以確定出一個(gè)全序關(guān)系定出一個(gè)全序關(guān)系此時(shí)此時(shí)FaS1.k和和FbS1.k的值都已知，的值都已知，F(xiàn)au的值待定的值待定我們考慮一種訪問順序中的兩個(gè)相鄰元素我們考慮一種訪問順序中的兩個(gè)相鄰元素v和和v+1第17頁/共22頁第十八頁，共23頁。第18頁/共22頁第十九頁，共23頁。確立確立(qul)狀狀態(tài)態(tài)優(yōu)化算法優(yōu)化算法合理的運(yùn)用題目中隱含的合理的運(yùn)用題目中隱含的特殊信息特殊信息第19頁/共22頁第二十頁，共23頁。勇于探索大膽(ddn)創(chuàng)新舉一反三(j y fn sn)第20頁/共22頁第二十一頁，共23頁。第21頁/共22頁第二十二頁，共23頁。NoImage內(nèi)容(nirng)總結(jié)會(huì)計(jì)學(xué)。而在實(shí)際的解題過程中，狀態(tài)信息往往是隱含(yn hn)的。第3頁/共22頁。這個(gè)問題很顯然可以轉(zhuǎn)化成一個(gè)二分圖最佳匹配的問題。蝸牛從根結(jié)點(diǎn)出發(fā)開始尋找它遺失在某個(gè)葉子結(jié)點(diǎn)的房子。它的房子可能遺失在葉結(jié)點(diǎn)