動(dòng)態(tài)規(guī)劃策略教材(存儲(chǔ)版)
【正文】 X=x1,x2,…, xm, Y=y1,y2,…, yn, Z=z1,z2,…, zk， Z 為 X 和 Y 的 LCS，那么 (1)若 xi=yj，則 zk=xi=yj， 且 Zk1是 Xi1和 Yj1的最長(zhǎng)公共子序列。循環(huán)體內(nèi)的計(jì)算量為 O(1)，而 3重循環(huán)的總次數(shù)為 O(n3)。 } ]}][1[]][[{]][[ max arg0kjifkigjiajk??????二、動(dòng)態(tài)規(guī)劃問(wèn)題的設(shè)計(jì)方法 ? ?最優(yōu)值 ?遞歸（遞推）公式 ?重復(fù)子問(wèn)題 ?自頂向下遞歸實(shí)現(xiàn) ?存在問(wèn)題：大量重復(fù)計(jì)算 ?解決辦法：備忘錄 ?自底向上遞推實(shí)現(xiàn) ?根據(jù)問(wèn)題遞推公式性質(zhì)，循環(huán)遞推即可 三、進(jìn)一步的例子 ?例 3: (矩陣鏈乘 )給定 n個(gè)矩陣 {A1,A2,… ,An} , 其中 Ai與 Ai+1是可乘的 (i=1,2,3,… ,n1)。 下表是 n=7萬(wàn)元資金分配給三個(gè)項(xiàng)目 A、 B、 C的利潤(rùn)表 分析：根據(jù)題意，本質(zhì)上是求下面的優(yōu)化問(wèn)題 J(x1,x2,..,xm)=max{g1(x1)+g2(x2)+… +gm(xm)} x1+x2+… +xm=n 0≤xi≤n， 要求 xi是整數(shù) 這是一個(gè)整數(shù)規(guī)劃問(wèn)題。動(dòng) 態(tài) 規(guī) 劃 河海大學(xué)計(jì)算機(jī)信息學(xué)院 丁海軍 [例 1]：求出從 頂點(diǎn) 1點(diǎn)到 頂點(diǎn) 7點(diǎn)的最短路徑 方法？ 一、導(dǎo)言 ?最優(yōu)性原理 ?根據(jù)窮舉法， (1,3,5,7)為優(yōu)化解。求利潤(rùn)總和為最大的資源分配方案。 j=jx[i]。設(shè)這個(gè)計(jì)算次序在矩陣 Ak和 Ak+1之間將矩陣鏈斷開(kāi)， i≤kj，則其相應(yīng)完全加括號(hào)方式為 )...)(...( 211 jkkkii AAAAAA ???計(jì)算量： A[i:k]的計(jì)算量加上 A[k+1:j]的計(jì)算量，再加上 A[i:k]和 A[k+1:j]相乘的計(jì)算量 ?動(dòng)態(tài)規(guī)劃 ① 劃分子問(wèn)題，確定子問(wèn)題的邊界，有 i和 j確定子問(wèn)題的邊界 ?設(shè)計(jì)算 A[i:j]， 1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問(wèn)題的最優(yōu)值為 m[1,n] ?當(dāng) i=j時(shí)， A[i:j]=Ai，因此， m[i,i]=0 ?當(dāng) ij時(shí) jki pppjkmkimjim 1],1[],[],[ ?????這里 的維數(shù)為 iA ii pp ??1 ?????????????? jipppjkmkimjijimjki }],1[],[{min0],[1jki 的位置只有 種 可能 k ij??可以遞歸地定義 m[i,j]為： ② 確定優(yōu)化函數(shù)和遞推方程： ③設(shè)立標(biāo)記函數(shù)（決策函數(shù)） 為了 確定加括號(hào)的次序 ，定義 s[i,j],記錄 m[i,j]最優(yōu)時(shí)k的位置 s[i,j]=k 問(wèn)題：如何編程實(shí)現(xiàn)？ ① 自頂向下遞歸實(shí)現(xiàn) ② 自底向上迭代（遞推）實(shí)現(xiàn) int RecurMatrixChain(P,i,j) { m[i,j]=? s[i,j]=i for( k=i to j?1 ){ q = RecurMatrixChain(P,i,k) + RecurMatrixChain(P,k+1,j) + pi?1 pk pj If (qm[i,j]){ m[i,j]=q s[i,j]=k }//end if }//end for return m[i,j] } 這里沒(méi)有寫(xiě)出算法的全部描述（進(jìn)入遞歸調(diào)用的初值等） ?方法 1：直接遞歸方法實(shí)現(xiàn) 26 復(fù)雜性滿足遞推關(guān)系 ?????????????????????????????11111111)(2)()()()()(1))1()()((1)1()(nknknknkkTnOknTkTnOnTnOknTkTnOnT 數(shù)學(xué)歸納法證明 T(n)?2n?1 n=2,顯然為真 假設(shè) 對(duì)于任何小于 n 的 k 命題為真 , 則 11111112)12(2)(22)()(2)()(??????????????? ??nnnkknknOnOkTnOnT*遞歸實(shí)現(xiàn)的復(fù)雜性 27 n=5，計(jì)算子問(wèn)題： 81個(gè) ；不同的子問(wèn)題： 15個(gè) 子問(wèn)題 11 22 33 44 55 12 23 34 45 13 24 35 14 25 15 數(shù) 8 12 14 12 8 4 5 5 4 2 2 2 1 1 1 2 復(fù)雜性高的原因：子問(wèn)題重復(fù)計(jì)算 ?方法 2：直接遞推方法 MatrixChain(P,n) { 令 所有的 m[i,j]初值為 0 1? i j ? n for( r ?2 to n) // r為計(jì)算的矩
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號(hào)-1