動態(tài)規(guī)劃策略教材-wenkub
2023-03-23 21:43:44 本頁面
【正文】 ?i+r?1 // 計算鏈 i— j m[i,j] ? m[i+1,j] + pi?1*pi*pj // Ai(Ai+1..Aj) s[i,j] ? i //記錄分割位置 for(k ?i+1 to j?1){ t ?m[i,k]+m[k+1,j]+ pi?1*pk*pj //(Ai..Ak)(Ak+1..Aj) if( tm[i,j]){ m[i,j]?t s[i,j]?k }//end if }// end for(k=…) }//end for(i=….) A1 A2 A3 A4 A5 A6 30?35 35?15 15?5 5?10 10?20 20?25 ??????????????????????????????11 37520233504375]5][5[]4][2[71252053510002625]5][4[]3][2[13 00020233525000]5][3[]2][2[min]5][2[541531521pppmmpppmmpppmmm算法復(fù)雜度分析： 算法 matrixChain的主要計算量取決于算法中對 r，i和 k的 3重循環(huán)。 ?若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標(biāo)準(zhǔn)算法計算出矩陣連乘積 ?給定 n個矩陣｛ A1,A2,… ,An｝，其中 Ai與Ai+1是可乘的 (i=1,2 ,… ,n1)。 j=jx[i]。 求的 a[i][j]之后，就可以求的每個項(xiàng)目分的資源量： j=n。求利潤總和為最大的資源分配方案。 ?無論第一步?jīng)Q策取 {2,3,4}中那一節(jié)點(diǎn)，其后的決策序列必須是該節(jié)點(diǎn)到目的節(jié)點(diǎn)的最短路 ?節(jié)點(diǎn) 1到目的節(jié)點(diǎn)的最短路長度可從 2,3,4到目的節(jié)點(diǎn)的最短路長度＋節(jié)點(diǎn) 1到這些節(jié)點(diǎn)的邊成本經(jīng)枚舉得到 ?應(yīng)用優(yōu)化原理設(shè)計算法的過程如下： ?選擇子問題的表示：設(shè) f(i)為 i到目的節(jié)點(diǎn)的最短路長度 ?建立 f(i)的遞歸方程 ?設(shè) A[i]為與 i相鄰的結(jié)點(diǎn)集合，則有 )}(),({co s)()}(),1({co s)1(minmin][]1[jfjitifjfjtfiAjAj??????初始 f(7)=0 依次計算 f(6),… ,f(1)： f(6)=1,f(5)=2, f(4)=8+f(6) f(3)=min{1+f(5),5+f(6)} f(2)=min{7+f(5),6+f(6)} f(1)=min{1+f(2),4+f(3),6+f(4)} 遞歸還可從前向后： f(i)=節(jié)點(diǎn) 1到節(jié)點(diǎn) i的最短路的長度；遞歸從 f(1)=0開始。動 態(tài) 規(guī) 劃 河海大學(xué)計算機(jī)信息學(xué)院 丁海軍 [例 1]：求出從 頂點(diǎn) 1點(diǎn)到 頂點(diǎn) 7點(diǎn)的最短路徑 方法？ 一、導(dǎo)言 ?最優(yōu)性原理 ?根據(jù)窮舉法， (1,3,5,7)為優(yōu)化解。 ?例 1: (數(shù)字三角問題 )如圖所示的數(shù)字三角形，從頂部出發(fā)，在每一個節(jié)點(diǎn)可以選擇向左走或者向右走，一直走到底部，要求找到一條路徑，使路徑上的數(shù)字和最大。 下表是 n=7萬元資金分配給三個項(xiàng)目 A、 B、 C的利潤表 分析：根據(jù)題意，本質(zhì)上是求下面的優(yōu)化問題 J(x1,x2,..,xm)=max{g1(x1)+g2(x2)+… +gm(xm)} x1+x2+… +xm=n 0≤xi≤n， 要求 xi是整數(shù) 這是一個整數(shù)規(guī)劃問題。 for(i=m。 } ]}][1[]][[{]][[ max arg0kjifkigjiajk??????二、動態(tài)規(guī)劃問題的設(shè)計方法 ? ?最優(yōu)值 ?遞歸（遞推）公式 ?重復(fù)子問題 ?自頂向下遞歸實(shí)現(xiàn) ?存在問題：大量重復(fù)計算 ?解決辦法：備忘錄 ?自底向上遞推實(shí)現(xiàn) ?根據(jù)問題遞推公式性質(zhì)，循環(huán)遞推即可 三、進(jìn)一步的例子 ?例 3: (矩陣鏈乘 )給定 n個矩陣 {A1,A2,… ,An} , 其中 Ai與 Ai+1是可乘的 (i=1,2,3,… ,n1)。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少 ? 為了表示方便 , 以 矩陣 加括號表示矩陣相乘的順序 輸入：向量 P = P0, P1, … , Pn， n個矩陣的行數(shù)、列數(shù) 實(shí)例： P = 10, 100, 5, 50 A1: 10 ? 100, A2: 100 ? 5, A3: 5 ? 50, ?完全加括號的矩陣連乘積可遞歸地定義為： （ 1）單個矩陣是完全加括號的； （ 2）矩陣連乘積 A是完全加括號的，則 A可 表示為 2個完全加括號的矩陣連乘積 B和 C 的乘積并加括號，即 A=((B)(
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1