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

1、動態(tài)規(guī)劃的深入討論動態(tài)規(guī)劃的深入討論東北育才學校東北育才學校李剛李剛【關鍵字關鍵字】動態(tài)規(guī)劃、狀態(tài)動態(tài)規(guī)劃、狀態(tài)【摘要摘要】本文討論了一種解決問題十分有效的技術本文討論了一種解決問題十分有效的技術——“動態(tài)規(guī)劃動態(tài)規(guī)劃”。它較高的解題效率一直受到很大的關注。本文首先對。它較高的解題效率一直受到很大的關注。本文首先對“動態(tài)動態(tài)規(guī)劃規(guī)劃”的理論基礎進行了討論。給出了一個用的理論基礎進行了討論。給出了一個用“動態(tài)規(guī)劃動態(tài)規(guī)劃”可以解決的問題的

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

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

4、應用價值呢？本文將對此進行討論。我們先通過一個具體問題認識一下“動態(tài)規(guī)劃”?！祭?〗：圖1中給出了一個地圖，地圖中每個頂點代表一個城市，兩個城市間的連線代表道路，連線上的數(shù)值代表道路的長度?，F(xiàn)在，我們想從城市A到達城市E，怎樣走路程最短，最短路程的長度是多少？或者或者I，J不連通，或者不連通，或者Dis[I]Map[IJ]≥Dis[J]。因為如果I，J連通且Dis[I]Map[IJ]Dis[J]，則說明Dis[J]存在更優(yōu)的情況，可J位

5、于I后，就不可能推出此情況，會影響最后的解。那么，我們?nèi)绾蝿澐窒群蟠涡蚰?？如圖2所示。我用不同顏色給城市分階段，可以用階段階段表示每個城市的次序，因為階段階段的劃分有如下性質：1：階段：階段I的取值只與階段的取值只與階段I1有關，階段有關，階段I的取值只對階段的取值只對階段I1的取值產(chǎn)的取值產(chǎn)生影響；生影響；2：每個階段的順序是確定的，不可以調換任兩個階段順序；：每個階段的順序是確定的，不可以調換任兩個階段順序；通過這兩個性質，可以推出

6、階段作為“前”、“后”順序滿足剛才提出的條件，所以我們可以用階段階段作為每個城市的次序，然后從階段3倒推至階段1，再推出Dis[A]。公式：公式：Dis[X]=MinDis[Y]：Y是下一個階段中與是下一個階段中與X相連通的城市相連通的城市注：可以把E看成第4個階段，A看成第0個階段。程序：Dis[E]=0FX=階段階段3的每個城市每個城市Downto階段階段0的每個城市的每個城市DoBeginDis[X]:=MaxintFY=階段階段