動態(tài)規(guī)劃策略教材-文庫吧資料
2025-03-08 21:43本頁面
【正文】 ]= ? 例 4:(最長遞增子序列 ) 若給定序列A=(a1,a2,… ,am),如果存在一個下標序列 i1i2… ik ，使得 則稱 為長度為 k的子序列。 ?其他 情況下，由最優(yōu)子結(jié)構(gòu)性質(zhì)可建立遞歸關(guān)系如下： ?????????????????jijiyxjiyxjijijicjicjicjic。當 i=0或 j=0時，空序列是Xi和 Yj的最長公共子序列 。 ?用 c[i][j]記錄序列和的最長公共子序列的長度。因此，最長公共子序列問題具有 最優(yōu)子結(jié)構(gòu)性質(zhì) 。 (3)若 xi≠yj且 zk≠yj， 則 Zk是 Xi和 Yj1的最長公共子序列。 分析：設(shè) X=“ abcbdab” Y=“ bdcdb” 最長公共子序列是： Z=“ bcdb” ① 子問題劃分及依賴關(guān)系 子問題邊界： X和 Y 起始位置為 1， X的終止位置是 i， Y 的 終止位置是 j，記作 Xi=x1,x2,…, xi， Yj=y1,y2,…, yj 依賴關(guān)系： 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的最長公共子序列。 ? 給定 2個序列 X和 Y，當另一序列 Z既是 X的子序列又是 Y的子序列時，稱 Z是序列 X和 Y的 公共子序列 。 則稱 Z是 X的子 序列 。算法所占用的空間顯然為 O(n2)。循環(huán)體內(nèi)的計算量為 O(1)，而 3重循環(huán)的總次數(shù)為 O(n3)。 ?由于每種加括號方式都可以分解為兩個子矩陣的加括號問題： (A1...Ak)(Ak+1… An)可以得到關(guān)于 P(n)的遞推式如下： 將矩陣連乘積 A1A2A3,…,An簡記為 A[i:j],這里 i≤j 考察計算 A[i:j]的最優(yōu)計算次序。如何確定計算矩陣連乘積的計算次序，使得依此次序計算矩陣連乘積需要的數(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ù)最少的計算次序。這種計算次序可以用加括號的方式來確定。 } ]}][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)。i){ x[i]=a[i][j]。 for(i=m。 實際編程時，還缺少一個東西？每個項目到底分配到多少資源量？ 定義數(shù)組 a[i][j] a[i][j]=kmax 表示前 i個項目分配資源量為 j的情況下，使得前 i個項目利潤最時，第 i個項目分配的資源量為 kmax。 下表是 n=7萬元資金分配給三個項目 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ī)劃問題。 顯而易見： f1(9)=9+max{f2(12)+f2(15)} 問題變成： f1(9)=? f2(12)=12+max{f3(10)+f3(6)} f2(15)=15+max{f3(6)+f3(8)} fi(x)=x+max{fi+1(x1)+fi+1(x2)+…… } 遞歸公式的終止條件： fN(19)=19 fN(7)=7 …… 思考： ① 請同學(xué)們手工計算一下結(jié)果？ ② 如何編程？ 如何編程與數(shù)據(jù)結(jié)構(gòu)有關(guān)：將原始數(shù)塔寫成下面的形式，用 data[i][j]表示這個矩陣 用矩陣 d[i][j]表示上面的 fi(x) 用矩陣表示的遞歸公式是什么樣子？
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1