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

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

2、。第3頁/共22頁第四頁，共23頁。第4頁/共22頁第五頁，共23頁。時間復(fù)雜(fz)度過大，無法滿足要求田忌田忌齊王齊王2000-200第5頁/共22頁第六頁，共23頁。齊王最強的馬田忌最強的馬用田忌最差的馬去輸給齊王最強的馬用田忌最差的馬去輸給齊王最強的馬輸給能贏用田忌最強的馬去戰(zhàn)勝用田忌最強的馬去戰(zhàn)勝(zhnshng)齊齊王最強的馬王最強的馬戰(zhàn)平用田忌最強的馬去打平齊王最強的馬用田忌最強的馬去打平齊王最強的馬或者或者(huzh)用田忌最差的馬去輸給齊王最強的馬用田忌最差的馬去輸給齊王最強的馬第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é)點樹上的結(jié)點(ji din)個數(shù)個數(shù)n最多為最多為1000，每，每個結(jié)點個結(jié)點(ji din)的分叉數(shù)的分叉數(shù)k最多為最多為8。第12頁/共22頁第十三頁，共23頁。(1+4+6)/3 = 11/3蝸牛從根結(jié)點蝸牛從根結(jié)點1 1出發(fā)開始尋找出發(fā)開始尋找(xnzho)(xnzho)它的房它的房子子它的房

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

5、遍歷該子樹需要的時間，如果i處有蟲子(chng zi)，那么Fbi=0） 用Leavesi 表示i為根的子樹上葉子節(jié)點的數(shù)目。 問題的解答就是Fa根結(jié)點/Leaves根結(jié)點。如果結(jié)點如果結(jié)點u u有有k k個兒子個兒子, ,我們按照我們按照(nzho)S1.Sk(nzho)S1.Sk進行訪問，進行訪問，F(xiàn)auFau的計算方式的計算方式是：是：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頁。另一個結(jié)論：如果另一個結(jié)論：如果A一定一定(ydng)放在放在B前，前，B一定一定(ydng)放在放在C前，可以推導出前，可以推導出A一定一定(ydng)放在放在C前。前。O(nklog2k)12kvv+1。 運用貪心(tnxn)思想分析

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