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

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

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

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

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

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

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