【正文】 第 四 章 基本的算法策略 動態(tài)規(guī)劃 認識動態(tài)規(guī)劃 算法框架 突出階段性的動態(tài)規(guī)劃應用 突出遞推的動態(tài)規(guī)劃應用 在動態(tài)規(guī)劃算法策略中，體現(xiàn)在它的決策不是線性的而是全面考慮不同的情況分別進行決策 , 并通過多階段決策來最終解決問題。在各個階段采取決策后 , 會不斷決策出新的數(shù)據(jù) ,直到找到最優(yōu)解 .每次決策依賴于當前狀態(tài) , 又隨即引起狀態(tài)的轉(zhuǎn)移。一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“ 動態(tài) ” 的含義。所以，這種多階段決策最優(yōu)化的解決問題的過程稱為 動態(tài)規(guī)劃 。 上節(jié) 下節(jié) 動態(tài)規(guī)劃 我們通過一個簡單的例子來說明動態(tài)規(guī)劃的多階段決策與貪婪算法有什么區(qū)別。 【 例 1】 數(shù)塔問題 上節(jié) 下節(jié) 認識動態(tài)規(guī)劃【 例 1】 數(shù)塔問題 有形如圖 411所示的一個數(shù)塔，從頂部出發(fā)，在每一結(jié)點可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的數(shù)值和最大。 問題分析算法設(shè)計算法小結(jié)問題分析 這個問題用貪婪算法有可能會找不到真正的最大和。以圖 411為例就是如此。用貪婪的策略，則路徑和分別為： 9+15+8+9+10=51 （自上而下）， 19+2+10+12+9=52（自下而上）。都得不到最優(yōu)解，真正的最大和是： 9+12+10+18+10=59。 在知道數(shù)塔的全貌的前提下，可以用 枚舉法 或下一章將學習的搜索算法來完成。 上節(jié) 下節(jié)算法設(shè)計 動態(tài)規(guī)劃設(shè)計過程如下： ： 第一步對于第五層的數(shù)據(jù)，我們做如下五次決策： 對經(jīng)過第四層 2的路徑選擇第五層的 19， 對經(jīng)過第四層 18的路徑選擇第五層的 10， 對經(jīng)過第四層 9的路徑也選擇第五層的 10， 對經(jīng)過第四層 5的路徑選擇第五層的 16。 上節(jié) 下節(jié)以上的決策結(jié)果將五階數(shù)塔問題變?yōu)?4階子問題，遞推出第四層與第五層的和為 : 21(2+19),28(18+10),19(9+10),21(5+16)。 用同樣的方法還可以將 4階數(shù)塔問題 ,變?yōu)?3階數(shù)塔問題?！?最后得到的 1階數(shù)塔問題，就是整個問題的最優(yōu)解。 上節(jié) 下節(jié) 2．存儲、求解： 1) 原始信息存儲 原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個整型 變量 n存儲，數(shù)塔中的數(shù)據(jù)用二維數(shù)組 data， 存儲成如 下的下三角陣 : 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 上節(jié) 下節(jié)2) 動態(tài)規(guī)劃過程存儲 必需用二維數(shù)組 a存儲各階段的決策結(jié)果。二維數(shù)組 a的存儲內(nèi)容如下： d[n][j]=data[n][j] j=1,2,……,n ； i=n1,n2,……1 ， j=1,2,……,i ； 時 d[i][j]=max(d[i+1][j]， d[i+1][j+1])+data[i][j] 最后 a[1][1]存儲的就是問題的結(jié)果。 上節(jié) 下節(jié)3) 最優(yōu)解路徑求解及存儲 僅有數(shù)組 data和數(shù)組 a可以找到最優(yōu)解的路徑， 但需要自頂向下比較數(shù)組 data和數(shù)組 a是可以找到。如圖 和輸出過程如下： 上節(jié) 下節(jié) 輸出 a[1][1]9 b=d[1][1]data[1][1]=599=50 b與 d[2][1],d[2][2] 比較 b與 d[2][1]相等輸出 data[2][1]12 b=d[2][1]data[2][1]=5012=38 b與 d[3][1],d[3][2] 比較 b與 d[3][1]相等輸出 data[3][1]10 b=a[3][1]data[3][1]=3810=28 b與 d[4][1],d[4][2] 比較 b與 d[4][2]相等輸出 data[4][2]18 b=d[4][2]data[4][2]=2818=10 b與 d[5][2],d[5][3] 比較 b與 d[5][3]相等輸出 data[5][3]10“ 上節(jié) 下節(jié)數(shù)組 data 數(shù)組 d 9 59 12 15 50 49 10 6 8 38 34 29 2 18 9 5 21 28 19 21 19 7 10 4 16 19 7 10 4 16 圖 412 數(shù)塔及動態(tài)規(guī)劃過程數(shù)據(jù) 上節(jié) 下節(jié)為了設(shè)計簡潔的算法，我們最后用三維數(shù)組a[50][50][3]存儲以上確定的三個數(shù)組的信息。 a[50][50][1]代替數(shù)組 data， a[50][50][2]代替數(shù)組 d, a[50][50][3]記錄解路徑。 上節(jié) 下節(jié) 數(shù)塔問題的算法main( ){ int a[50][50][3],i,j,n。 print( 39。please input the number of rows:39。)。 input(n)。　 for( i=1 。i=n。i++)　　 for j=1 to i do　　 { input(a[i][j][1])?！　　　? a[i][j][2]=a[i][j][1]?！　　　? a[i][j][3]=0。} 上節(jié) 下節(jié)for (i=n1 。 i=1。i) for (j=1 。j= i 。j++)　　　 if (a[i+1][j][2]a[i+1][j+1][2]) 　　　　 { a[i][j][2]=a[i][j][2]+a[i+1][j][2]。 a[i][j][3]=0。} 　 else　　　　 { a[i][j][2]=a[i][j][2]+a[i+1][j+1][2]。 a[i][j][3]=1。}print(39。max=’,a[1][1][2])。j=1。for( i=1 。i= n1。i++) { print(a[i][j][1],‘’)?！? j=j+a[i][j][3]。 }print (a[n][j][1])。} 上節(jié) 下節(jié)從例子中可以看到： 動態(tài)規(guī)劃 =貪婪策略 +遞推 (降階 )+存儲遞推結(jié)果 貪婪策略、遞推算法都是在 “ 線性 ” 地解決問題，而動態(tài)規(guī)劃則是全面分階段地解決問題?？梢酝ㄋ椎卣f動態(tài)規(guī)劃是 “帶決策的多階段、多方位的遞推算法 ” 。 上節(jié) 下節(jié) 動態(tài)規(guī)劃算法的問題及決策應該具有三個性質(zhì)：最優(yōu) 化原理、無后向性、子問題重疊性質(zhì)。1) 最優(yōu)化原理 (或稱為最佳原則、 最優(yōu)子結(jié)構(gòu) )。 2) 無后向性 (無后效性 )。 3) 有 重疊子問題 。 上節(jié) 下節(jié) 算法框架2. 動態(tài)規(guī)劃的基本思想 動態(tài)規(guī)劃方法的基本思想是，把求解的問題分成許多階段或多個子問題，然后按順序求解各子問題。 最后一個子問題就是初始問題的解 。 由于動態(tài)規(guī)劃的問題有 重疊子問題 的特點，為了減少重復計算，對每一個子問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中。 上節(jié) 下節(jié)3. 設(shè)計動態(tài)規(guī)劃算法的基本步驟 設(shè)計一個標準的動態(tài)規(guī)劃算法的步驟： 1) 劃分階段 2) 選擇狀態(tài) 3) 確定決策并寫出狀態(tài)轉(zhuǎn)移方程 但是 ,實際應用當中的簡化步驟： 1) 分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 2) 遞推地定義最優(yōu)值。 3) 以自底向上的方式或自頂向下的記憶化方法 (備忘錄 法 )計算出最優(yōu)值 . 4) 根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造問題的最優(yōu)解。 上節(jié) 下節(jié)4. 標準動態(tài)規(guī)劃的基本框架for(j=1j=m。j=j+1)//第一個階段　　 xn[j]=初始值；for(i=n1i=1。i=i1)//其它 n1個階段　 for(j=1j=f(i)j=j+1)//f(i)與 i有關(guān)的表達式　　 xi[j]=max(或 min){g(xi1[j1—— j2])， …… ， g(xi1[jk—— jk+1])}；t=g(x1[j1—j2])。//由最優(yōu)解求解最優(yōu)解的方案print(x1[j1])。for(i=2i=n1。i=i+1){t=txi1[ji]。for(j=1j=f(i)j=j+1)if(t=xi[ji])break。} 上節(jié) 下節(jié) 【 例 2】 資源分配問題。 【 例 3】 n個矩陣連乘的問題。 上節(jié) 下節(jié) 突出階段性的動態(tài)規(guī)劃應用【 例 2】 資源分配問題。 設(shè)有資源 a,分配給 n個項目 ,gi(x)為第 i個項目分得資源 x所得到的利潤。求總利潤最大的資源分配方案，也就是解下列問題： max z=g1(x1)+ g2(x2)+…… gn(xn) x1+xx2+x3+…… xn=a, xi≥0,i=1 ， 2,3,……,n函數(shù) gi(x)以數(shù)據(jù)表的形式給出 .例如：現(xiàn)有 7萬元投資到 A， B， C 三個項目，利潤見表 ,求問題總利潤最大的資源分配方案。 上節(jié) 下節(jié)算法設(shè)計1．階段劃分及決策 比較直觀的階段劃分就是 逐步 考慮 每一個項目 在不 同投資額下的利潤情況。