動態(tài)規(guī)劃策略教材-文庫吧
2025-02-22 21:43 本頁面
【正文】 定義數(shù)組 a[i][j] a[i][j]=kmax 表示前 i個項目分配資源量為 j的情況下，使得前 i個項目利潤最時，第 i個項目分配的資源量為 kmax。 求的 a[i][j]之后，就可以求的每個項目分的資源量： j=n。 for(i=m。i=1。i){ x[i]=a[i][j]。 j=jx[i]。 } ]}][1[]][[{]][[ max arg0kjifkigjiajk??????二、動態(tài)規(guī)劃問題的設(shè)計方法 ? ?最優(yōu)值 ?遞歸（遞推）公式 ?重復(fù)子問題 ?自頂向下遞歸實現(xiàn) ?存在問題：大量重復(fù)計算 ?解決辦法：備忘錄 ?自底向上遞推實現(xiàn) ?根據(jù)問題遞推公式性質(zhì)，循環(huán)遞推即可 三、進一步的例子 ?例 3: (矩陣鏈乘 )給定 n個矩陣 {A1,A2,… ,An} , 其中 Ai與 Ai+1是可乘的 (i=1,2,3,… ,n1)?？疾爝@ n個矩陣的連乘積 A1A2A3… An ?由于矩陣乘法滿足結(jié)合律，所以計算矩陣的連乘可以有許多不同的計算次序。這種計算次序可以用加括號的方式來確定。 ?若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復(fù)調(diào)用2個矩陣相乘的標(biāo)準(zhǔn)算法計算出矩陣連乘積 ?給定 n個矩陣｛ A1,A2,… ,An｝，其中 Ai與Ai+1是可乘的 (i=1,2 ,… ,n1)。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(shù)乘次數(shù)最少 ? 為了表示方便 , 以 矩陣 加括號表示矩陣相乘的順序 輸入：向量 P = P0, P1, … , Pn， n個矩陣的行數(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)(C)) ?設(shè)有四個矩陣 A、 B、 C、 D,它們的維數(shù)分別是 1050 ?? 4010 ?? 3040 ??C 530?D )))((( DBCA )))((( DCAB )))((( BCA )))((( CDB )))((( CDAB16000 10500 36000 87500 34500 四種加括號方式 ?窮舉法 ?列舉出所有可能的計算次序，并計算出每一種計算次序相應(yīng)需要的數(shù)乘次數(shù)，從中找出一種數(shù)乘次數(shù)最少的計算次序。 )/4()(11)()(1)( 2/311nnPnnknPkPnPnnk???????????? ????算法復(fù)雜度分析 ： ?對于 n個矩陣的連乘積，設(shè)其不同的計算次序為 P(n)。 ?由于每種加括號方式都可以分解為兩個子矩陣的加括號問題： (A1...Ak)(Ak+1… An)可以得到關(guān)于 P(n)的遞推式如下： 將矩陣連乘積 A1A2A3,…,An簡記為 A[i:j],這里 i≤j 考察計算 A[i:j]的最優(yōu)計算次序。設(shè)這個計算次序在矩陣 Ak和 Ak+1之間將矩陣鏈斷開， i≤kj，則其相應(yīng)完全加括號方式為 )...)(...( 211 jkkkii AAAAAA ???計算量： A[i:k]的計算量加上 A[k+1:j]的計算量，再加上 A[i:k]和 A[k+1:j]相乘的計算量 ?動態(tài)規(guī)劃 ① 劃分子問題，確定子問題的邊界，有 i和 j確定子問題的邊界 ?設(shè)計算 A[i:j]， 1≤i≤j≤n，所需要的最少數(shù)乘次數(shù)m[i,j]，則原問題的最優(yōu)值為 m[1,n] ?當(dāng) i=j時， A[i:j]=Ai，因此， m[i,i]=0 ?當(dāng) ij時 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ù)） 為了 確定加括號的次序 ，定義 s[i,j],記錄 m[i,j]最優(yōu)時k的位置 s[i,j]=k 問題：如何編程實現(xiàn)？ ① 自頂向下遞歸實現(xiàn) ② 自底向上迭代（遞推）實現(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 fo
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1