【正文】 函數(shù)，只需直接取 aMaxSum[r][j]的值即可。 ? 如何存放計算出來的 MaxSum（ r, j）值呢？顯然，用一個二維數(shù)組 aMaxSum[N][N]就能解決。即第一次算出MaxSum(r, j)的值時，就將該值存放起來，下次再需要計算MaxSum(r, j)時，直接取用存好的值即可，不必再次調(diào)用MaxSum 進行函數(shù)遞歸計算了。當(dāng) N= 100 時，總的計算次數(shù)是一個讓人無法接受的大數(shù)字。 在 題 目 中 給 出 的 例 子 里 ， 如 果 我 們 將MaxSum(r, j)被計算的次數(shù)都寫在位置 （ r, j） ， 那么就能得到右面的三角形： 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 7 3 8 8 1 0 2 7 4 4 4 5 2 6 5 程序分析 ? 從上圖可以看出，最后一行的計算次數(shù)總和是 16，倒數(shù)第二行的計算次數(shù)總和是 8。 那么 ， 每次計算 MaxSum(r, j)的時候 ， 都要計算一次 MaxSum(r+1, j+1)，而每次計算 MaxSum(r, j+1)的時候 ， 也要計算一次 MaxSum(r+1, j+1)。 為什么會這樣呢 ？ 是因為過多的重復(fù)計算 。 return 0。D[i][j])。 j = i。 i = N。N)。 } 參考程序 I int main(void) { int m。 if( nSum1 nSum2 ) return nSum1+D[r][j]。 int nSum1 = MaxSum(r+1, j)。 int N。所以，選擇往哪里走，就看 MaxSum(r+1, j)和 MaxSum(r+1, j+1)哪個更大了。 從某個 D(r, j)出發(fā)，顯然下一步只能走 D(r+1, j)或者 D(r+1, j+1)。 解題思路 這道題目可以用遞歸的方法解決。你的任務(wù)就是求出最佳路徑上的數(shù)字之和。從三角形的頂部到底部有很多條不同的路徑。 21 21 動態(tài)規(guī)劃算法的基本要素 三、備忘錄方法 ?備忘錄方法的控制結(jié)構(gòu)與直接遞歸方法的控制結(jié)構(gòu)相同，區(qū)別在于備忘錄方法為每個解過的子問題建立了備忘錄以備需要時查看，避免了相同子問題的重復(fù)求解。 ?通常不同的子問題個數(shù)隨問題的大小呈多項式增長。 這種性質(zhì)稱為 子問題的重疊性質(zhì) 。最優(yōu)子結(jié)構(gòu)是問題能用動態(tài)規(guī)劃算法求解的前提。 ?在分析問題的最優(yōu)子結(jié)構(gòu)性質(zhì)時，所用的方法具有普遍性：首先假設(shè)由問題的最優(yōu)解導(dǎo)出的子問題的解不是最優(yōu)的，然后再設(shè)法說明在這個假設(shè)下可構(gòu)造出比原問題最優(yōu)解更好的解，從而導(dǎo)致矛盾。 17 ?習(xí)題 :多段圖問題 (multistage graph problem) 2 3 4 5 8 7 6 11 10 9 1 s 12 t 9 7 3 2 4 2 2 7 1 11 11 8 6 5 4 3 5 6 5 2 4 V1 V2 V3 V4 V5 18 動態(tài)規(guī)劃的設(shè)計要素 19 19 動態(tài)規(guī)劃算法的基本要素 一、最優(yōu)子結(jié)構(gòu) ?問題的最優(yōu)解包含著其子問題的最優(yōu)解。 以上五步是建立動態(tài)規(guī)劃數(shù)學(xué)模型的一般步驟。 16 確定狀態(tài)轉(zhuǎn)移方程 根據(jù) k 階段狀態(tài)變量和決策變量，寫出 k+1階段狀態(tài)變量，狀態(tài)轉(zhuǎn)移方程應(yīng)當(dāng)具有遞推關(guān)系。 一般地 ， 狀態(tài)變量的選擇是從過程演變的特點中尋找 。 對于靜態(tài)問題要人為地賦予 “ 時間 ” 概念 ， 以便劃分階段 。 在求整個問題的最優(yōu)策略時，由于初始狀態(tài)是已知的，而每段的決策都是該段狀態(tài)的函數(shù)，故最優(yōu)策略所經(jīng)過的各段狀態(tài)便可逐段變換得到，從而確定了最優(yōu)路線。因此，每段決策的選取是從全局來考慮的，與該段的最優(yōu)選擇答案一般是不同的 . 最優(yōu)化原理：作為整個過程的最優(yōu)策略具有這樣的性質(zhì)：無論過去的狀態(tài)和決策如何，相對于前面的決策所形成的狀態(tài)而言，余下的決策序列必然構(gòu)成最優(yōu)子策略。即從邊界條件開始，逐段遞推尋優(yōu)，在每一個子問題的求解中，均利用了它前面的子問題的最優(yōu)化結(jié)果，依次進行，最后一個子問題所得的最優(yōu)解，就是整個問題的最優(yōu)解。 多階段決策問題： 是動態(tài)決策問題的一種特殊形式； 在多階段決策過程中 ,系統(tǒng)的動態(tài)過程可以按照時間進程分為 狀態(tài) 相互 聯(lián)系 而又相互 區(qū)別 的各個 階段 ； 1 2 n ? 狀態(tài) 決策 狀態(tài) 決策 狀態(tài) 狀態(tài) 決策 13 動態(tài)規(guī)劃方法的關(guān)鍵在于正確地寫出基本的遞推關(guān)系式和恰當(dāng)?shù)倪吔鐥l件（簡稱基本方程）。 1 多階段決策問題 動態(tài)規(guī)劃 的基本思想 11 即在系統(tǒng)發(fā)展的不同時刻（或階段）根據(jù)系統(tǒng)所處的狀態(tài)，不斷地做出決策； 動態(tài)決策問題的特點： 系統(tǒng)所處的狀態(tài)和時刻是進行決策的重要因素； 找到不同時刻的最優(yōu)決策以及整個過程的最優(yōu)策略。 需指出：動態(tài)規(guī)劃是求解某類問題的一種方法，是考察問題的一種途徑，而不是一種算法。 10 動態(tài)規(guī)劃是用來解決多階段決策過程最優(yōu)化的一種數(shù)量方法。假定圖的邊數(shù)為 m，則這部分的時間性能是O(m)；第三部分是輸出最短路徑經(jīng)過的頂點，其時間性能是 O(n)。 i=path[i]。 3． 輸出最短路徑長度 cost[0]。 i) 對頂點 i的每一個鄰接點 j， 根據(jù)式 cost[i]。則： cost[i]=min{cij+cost[j]} (i≤j≤n且頂點 j是頂點 i的鄰接點 ) （ 式 1） path[i]=使 cij+cost[j]最小的 j （ 式 2） 9 算法 1—— 多段圖的最短路徑 1． 初始化：數(shù)組 cost[n]初始化為最大值 ， 數(shù)組 path[n]初始化為 1； 2． for (i=n2。 8 下面考慮多段圖的最短路徑問題的填表形式 。假設(shè)圖中的頂點個數(shù)為 n，則源點 s的編號為 0，終點 t的編號為 n1，并且， 對圖中的任何一條邊 (u, v)，頂點 u的編號小于頂點 v的編號 。 4 2 1 2 0 3 4 5 6 7 8 9 4 9 3 8 7 6 8 4 7 5 6 8 6 6 5 3 7 一個多段圖 由于多段圖將頂點劃分為 k個互不相交的子集，所以，多段圖劃分為 k段，每一段包含頂點的一個子集。1 第五章 動態(tài)規(guī)劃 2 ? ? 動態(tài)規(guī)劃算法的設(shè)計要素 ? 動態(tài)規(guī)劃算法的典型應(yīng)用 ?投資問題； ?0－ 1背包問題； ?最優(yōu)二叉搜索樹問題 3 引例： 多段圖的最短路徑問題 設(shè)圖 G=(V, E)是一個帶權(quán)有向連通圖 ， 如果把頂點集合 V劃分成 k個互不相交的子集 Vi（ 2≤ k≤ n, 1≤ i≤ k） ， 使得 E中的任何一條邊 (u, v)， 必有u∈ Vi， v∈ Vi+m（ 1≤ i＜ k, 1＜ i+m≤ k） ， 則稱圖 G為多段圖 ， 稱 s∈ V1為源點 ， t∈ Vk為終點 。 多段圖的最短路徑問題是求從源點到終點的最小代價路徑 。不失一般性， 將多段圖的頂點按照段的順序進行編號 ，同一段內(nèi)頂點的相互順序無關(guān)緊要。 5 對多段圖的邊 (u, v)，用 cuv表示邊上的權(quán)值，將從源點 s到終點 t的最短路徑記為 d(s, t)，則從源點 0到終點 9的最短路徑 d(0, 9)由下式確定： d(0, 9)=min{c01+d(1, 9), c02+d(2, 9), c03+d(3, 9)} 這是最后一個階段的決策 ， 它依賴于 d(1, 9)、d(2, 9)和 d(3, 9)的計算結(jié)果 ， 而 d(1, 9)=min{c14+d(4, 9), c15+d(5, 9)} d(2, 9)=min{c24+d(4, 9), c25+d(5, 9), c26+d(6, 9)} d(3, 9)=min{c35+d(5, 9), c36+d(6, 9)} 這一階段的決策又依賴于 d(4, 9)、 d(5, 9)和 d(6, 9)的計算結(jié)果： 6 d(4, 9)=min{c47+d(7, 9), c48+d(8, 9)} d(5, 9)=min{c57+d(7, 9), c58+d(8, 9)} d(6, 9)=min{c67+d(7, 9), c68+d(8, 9)} 這一階段的決策依賴于 d(7, 9)和 d(8, 9)的計算 ， 而 d(7, 9)和 d(8, 9)可以直接獲得 （ 括號中給出了決策產(chǎn)生的狀態(tài)轉(zhuǎn)移 ） ： d(7, 9)=c79＝ 7(7→ 9) d(8, 9)=c89＝ 3(8→ 9) 再向前推導(dǎo) ， 有： d(6, 9)=min{c67+d(7, 9), c68+d(8, 9)}=min{6+7, 5+3}=8(6→ 8) d(5, 9)=min{c57+d(7, 9), c58+d(8, 9)}=min{8+7, 6+3}=9(5→ 8) d(4, 9)=min{c47+d(7, 9), c48+d(8, 9)}=min{5+7, 6+3}=9(4→ 8) 7 d(3, 9)=min{c35+d(5, 9), c36+d(6, 9)}=min{4+9, 7+8}=13(3→ 5) d(2, 9)=min{c24+d(4, 9), c25+d(5, 9), c26+d(6, 9)}=min{6+9, 7+9, 8+8}=15(2→ 4) d(1, 9)=min{c14+d(4, 9), c15+d(5, 9)}=min{9+9, 8+9}=17(1→ 5) d(0, 9)=min{c01+d(1, 9), c02+d(2, 9), c03+d(3, 9)}=min{4+17, 2+15, 3+13}=16(0→ 3) 最后，得到最短路徑為 0→ 3→ 5→ 8→ 9，長度為 16。 用一個數(shù)組 cost[n]作為存儲子問題解的表格， cost[i]表示從頂點 i到終點 n1的最短路徑，數(shù)組 path[n]存儲狀態(tài)，path[i]表示從頂點 i到終點 n1的路徑上頂點 i的下一個頂點。 i=0。 根據(jù)式 path[i]。 4. 輸出最短路徑經(jīng)過的頂點： i=0 循環(huán)直到 path[i]=n1 輸出 path[i]。 算法 1主要由三部分組成：第一部分是初始化部分，其時間性能為 O(n)；第二部分是依次計算各個頂點到終點的最短路徑，由兩層嵌套的循環(huán)組成，外層循環(huán)執(zhí)行 n1次，內(nèi)層循環(huán)對所有出邊進行計算，并且在所有循環(huán)中，每條出邊只計算一次。所以，算法 1的時間復(fù)雜性為 O(n+m)。其特點在于，它可以把一個 n 維決策問題變換為幾個一維最優(yōu)化問題，從而一個一個地去解決。必須對具體問題進行具體分析，運用動態(tài)規(guī)劃的原理和方法，建立相應(yīng)的模型，然后再用動態(tài)規(guī)劃方法去求解。 12 每個階段都要進行 決策 ,目的是使整個過程的決策達到最優(yōu)效果。要做到這一點，就必須將問題的過程分成幾個相互聯(lián)系的階段，恰當(dāng)?shù)倪x取狀態(tài)變量和決策變量及定義最優(yōu)值函數(shù)，從而把一個大問題轉(zhuǎn)化成一組同類型的子問題，然后逐個求解。 2 動態(tài)規(guī)劃的基本思想 14 在多階段決策過程中，動態(tài)規(guī)劃方法是既把當(dāng)前一段和未來一段分開，又把當(dāng)前效益和未來效益結(jié)合起來考慮的一種最優(yōu)化方法?！币簿褪钦f，一個最優(yōu)策略的子策略也是最優(yōu)的。 15 3. 建立動態(tài)規(guī)劃模型的步驟 劃分階段 劃分階段是運用動態(tài)規(guī)劃求解多階段決策問題的第一步 ， 在確定多階段特性后 ， 按時間或空間先后順序 ， 將過程劃分為若干相互聯(lián)系的階段 。 正確選擇狀態(tài)變量 選擇變量既要能確切描述過程演變又要滿足無后效性 ，而且各階段狀態(tài)變量的取值能夠確定 。 確定決策變量及允許決策集合 通常選擇所求解問題的關(guān)鍵變量作為決策變量 ， 同時要給出決策變量的取值范圍 ， 即確定允許決策集合 。 確定階段指標函數(shù)和最優(yōu)指標函數(shù)，建立動態(tài)規(guī)劃基