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

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

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

3、因工作”以及“動(dòng)態(tài)規(guī)劃”技術(shù)在解決問(wèn)題中速度驚人的原因——“解決了查看中的冗余，達(dá)到了速度的極限”。最后，闡述“解決了查看中的冗余，達(dá)到了速度的極限”。最后，闡述了解決“動(dòng)態(tài)規(guī)劃”問(wèn)題的一般步驟，即“思考，計(jì)劃，應(yīng)了解決“動(dòng)態(tài)規(guī)劃”問(wèn)題的一般步驟，即“思考，計(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è)具體問(wèn)題認(rèn)識(shí)一下“動(dòng)態(tài)規(guī)劃”。Dis[A]:=Long(A)End.這個(gè)程序的效率如何呢？我們可以看到，每次除了已經(jīng)訪問(wèn)過(guò)的城市外，其他城市都要訪問(wèn)，所以時(shí)間復(fù)雜度為，這是一個(gè)“指數(shù)級(jí)”的算法，)!(NO那么，還有沒有更好的算法呢？首先，我們來(lái)觀察一下這個(gè)算法。在求從B1到E的最短路徑的時(shí)候，先求出從C2到E的最短路徑；而在求從B2到E的最短路徑的時(shí)候，又

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

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

7、如圖2所示。我用不同顏色給城市分階段，可以用階段階段表示每個(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ì)，可以推出階段作為“前”、“后”順序滿足剛才提出的條件，所以我們可以用階段階段作為每