動態(tài)規(guī)劃的深入討論論文

1、動態(tài)規(guī)劃的深入討論動態(tài)規(guī)劃的深入討論【關(guān)鍵字】【關(guān)鍵字】動態(tài)規(guī)劃、狀態(tài)動態(tài)規(guī)劃、狀態(tài)【摘要】摘要】本文討論了一種解決問題十分有效的技術(shù)本文討論了一種解決問題十分有效的技術(shù)——“動態(tài)規(guī)“動態(tài)規(guī)劃”。它較高的解題效率一直受到很大的關(guān)注。本文首先對劃”。它較高的解題效率一直受到很大的關(guān)注。本文首先對“動態(tài)規(guī)劃”的理論基礎(chǔ)進(jìn)行了討論。給出了一個用“動態(tài)規(guī)“動態(tài)規(guī)劃”的理論基礎(chǔ)進(jìn)行了討論。給出了一個用“動態(tài)規(guī)劃”可以解決的問題的兩個先決條件：“最

2、優(yōu)子結(jié)構(gòu)”與“無劃”可以解決的問題的兩個先決條件：“最優(yōu)子結(jié)構(gòu)”與“無后效性”。接著，討論了在實際應(yīng)用中的兩個比較常見的問后效性”。接著，討論了在實際應(yīng)用中的兩個比較常見的問題：“動態(tài)規(guī)劃”中狀態(tài)的選定與存儲。再通過以上問題的討題：“動態(tài)規(guī)劃”中狀態(tài)的選定與存儲。再通過以上問題的討論，引出了“動態(tài)規(guī)劃”的基本思維方法：“不做已經(jīng)做過的論，引出了“動態(tài)規(guī)劃”的基本思維方法：“不做已經(jīng)做過的工作”以及“動態(tài)規(guī)劃”技術(shù)在解決問題中速度驚人的原

3、因工作”以及“動態(tài)規(guī)劃”技術(shù)在解決問題中速度驚人的原因——“解決了查看中的冗余，達(dá)到了速度的極限”。最后，闡述“解決了查看中的冗余，達(dá)到了速度的極限”。最后，闡述了解決“動態(tài)規(guī)劃”問題的一般步驟，即“思考，計劃，應(yīng)了解決“動態(tài)規(guī)劃”問題的一般步驟，即“思考，計劃，應(yīng)用”。用”。【正文】【正文】一引引論在信息學(xué)競賽中，特別是最近幾年，“動態(tài)規(guī)劃”作為一種解題工具，經(jīng)常被提及。其應(yīng)用范圍愈來愈廣，應(yīng)用程度也愈來愈深。那么，“動態(tài)規(guī)劃”究竟與

4、其它的算法有什么差別？它有什么具體的應(yīng)用價值呢？本文將對此進(jìn)行討論。我們先通過一個具體問題認(rèn)識一下“動態(tài)規(guī)劃”。Dis[A]:=Long(A)End.這個程序的效率如何呢？我們可以看到，每次除了已經(jīng)訪問過的城市外，其他城市都要訪問，所以時間復(fù)雜度為，這是一個“指數(shù)級”的算法，)!(NO那么，還有沒有更好的算法呢？首先，我們來觀察一下這個算法。在求從B1到E的最短路徑的時候，先求出從C2到E的最短路徑；而在求從B2到E的最短路徑的時候，又

5、求了一遍從C2到E的最短路徑。也就是說，從C2到E的最短路徑我們求了兩遍。同樣可以發(fā)現(xiàn)，在求從C1、C2到E的最短路徑的過程中，從D1到E的最短路徑也被求了兩遍。而在整個程序中，從D1到E的最短路徑被求了四遍，這是多么這是多么大的一個浪費(fèi)啊！大的一個浪費(fèi)??！如果在求解的過程中，同時將求得的最短路徑的距離“記錄在案”，隨時調(diào)用，那會是多么的方便??！那會是多么的方便?。∮谑?，一個新的思路誕生了，即：由后往前由后往前依次推出每個Dis值，直到

6、推出Dis[A]為止。這個思路的確很好，但等等，究竟什么是“由后往前”呢？所謂“后”、“前”是我們自己為城市編的序號，當(dāng)兩個城市I，J的前后順序定為I“前”J“后”時，必須滿足這個條件：或者或者I，J不連通，或者不連通，或者Dis[I]Map[IJ]≥Dis[J]。因為如果I，J連通且Dis[I]Map[IJ]Dis[J]，則說明Dis[J]存在更優(yōu)的情況，可J位于I后，就不可能推出此情況，會影響最后的解。那么，我們?nèi)绾蝿澐窒群蟠涡蚰兀?/p>

7、如圖2所示。我用不同顏色給城市分階段，可以用階段階段表示每個城市的次序，因為階段階段的劃分有如下性質(zhì)：1：階段：階段I的取值只與階段的取值只與階段I1有關(guān)，階段有關(guān)，階段I的取值只對階段的取值只對階段I1的取值產(chǎn)的取值產(chǎn)生影響；生影響；2：每個階段的順序是確定的，不可以調(diào)換任兩個階段順序；：每個階段的順序是確定的，不可以調(diào)換任兩個階段順序；通過這兩個性質(zhì)，可以推出階段作為“前”、“后”順序滿足剛才提出的條件，所以我們可以用階段階段作為每