動態(tài)規(guī)劃 (矩陣連乘)

1、1實驗三實驗三 動態(tài)規(guī)劃算法動態(tài)規(guī)劃算法矩陣連乘問題2動態(tài)規(guī)劃的應用動態(tài)規(guī)劃的應用：矩陣連乘矩陣連乘例例:A1A2相乘，設這相乘，設這2個矩陣的維數(shù)分別為個矩陣的維數(shù)分別為10*5，5*3運運算次數(shù)算次數(shù)10*5*3=150。問題：問題：給定給定n個矩陣個矩陣A1,A2,An，其中，其中Ai與與Ai+1是可乘的，是可乘的，i=1，2，n-1。如何確定計算矩陣連乘積的。如何確定計算矩陣連乘積的計算次序計算次序，使得依此次序計算矩陣，使得依此次序計算矩陣連乘積需要的連乘積需要的數(shù)乘次數(shù)數(shù)乘次數(shù)最少。最少。3假設：假設：給定給定n n個矩陣個矩陣 ， 其中其中 與與 是是可乘可乘 的，的， ?？疾爝@

2、?？疾爝@n n個矩陣的連乘積個矩陣的連乘積 n矩陣乘法滿足矩陣乘法滿足結(jié)合律結(jié)合律，計算矩陣的連乘可以有許多不同的計，計算矩陣的連乘可以有許多不同的計算次序，這種計算次序可以用算次序，這種計算次序可以用加括號加括號的方式來確定的方式來確定n若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已若一個矩陣連乘積的計算次序完全確定，也就是說該連乘積已完全加括號，則可以依此次序反復調(diào)用完全加括號，則可以依此次序反復調(diào)用2 2個矩陣相乘的標準算個矩陣相乘的標準算法計算出矩陣連乘積法計算出矩陣連乘積,.,21nAAAiA1iA1,.,2 , 1ninAAA.21動態(tài)規(guī)劃的應用動態(tài)規(guī)劃的應用：矩陣連乘矩陣

3、連乘4u完全加括號的矩陣連乘積可完全加括號的矩陣連乘積可遞歸遞歸定義為：定義為：單個單個矩陣是完全加括號的矩陣是完全加括號的矩陣連乘積矩陣連乘積A是完全加括號的，則是完全加括號的，則A可表示為可表示為2個完個完全加括號的矩陣連乘積全加括號的矩陣連乘積B和和C的乘積并加括號，即的乘積并加括號，即A=(BC)矩陣連乘矩陣連乘5)(DBCA)(DCAB)(DBCA)(CDBA)(CDAB16000, 10500, 36000, 87500, 34500例如：表格中有四個矩陣及相應維數(shù)例如：表格中有四個矩陣及相應維數(shù)u總共有五種完全加括號的方式總共有五種完全加括號的方式矩陣連乘矩陣連乘矩陣ABCD維數(shù)

4、501010404030 3056矩陣連乘問題矩陣連乘問題將矩陣連乘積將矩陣連乘積 簡記為簡記為Ai:j ，這里，這里ij jiiAAA.1考察計算考察計算Ai:j的最優(yōu)計算次序。設這個計算次序在矩陣的最優(yōu)計算次序。設這個計算次序在矩陣Ak和和Ak+1之間將矩陣鏈斷開，之間將矩陣鏈斷開，ikj，則其相應完全，則其相應完全加括號方式為加括號方式為).)(.(211jkkkiiAAAAAA計算量：計算量：Ai:k的計算量的計算量加上加上Ak+1:j的計算量的計算量，再加上，再加上Ai:k和和Ak+1:j相乘的計算量相乘的計算量7設計算Ai:j，1ijn，所需要的最少數(shù)乘次數(shù)mij，則原問題的最優(yōu)值

5、為m1n 當i=j時，Ai:j=Ai，因此，mii=0，i=1,2,n當ij時，可以遞歸地定義mij為：jkipppjkmkimjim11這里 的維數(shù)為 iAiipp1jipppjkmkimjijimjki1min01jki （斷點）的位置只有 種可能kij 8矩陣A1A2A3A4A5A6數(shù)組pp0p1p1p2p2p3p3p4p4p5p5p6維數(shù)值3035351515551010202025根據(jù)MatrixChain動態(tài)規(guī)劃算法：計算次序（如圖）9矩陣A1A2A3A4A5A6數(shù)組pp0p1p1p2p2p3p3p4p4p5p5p6維數(shù)值3035351515551010202025根據(jù)Matrix

6、Chain動態(tài)規(guī)劃算法：計算mij數(shù)乘次數(shù)計算A1、A2、A3、A4、A5、A6計算(A1A2)(A2A3)(A3A4)(A4A5)(A5A6)計算(A1A2A3)(A2A3A4)(A3A4A5)(A4A5A6)計算(A1A2A3A4)(A2A3A4A5)(A3A4A5A6)計算(A1A2A3A4A5)(A2A3A4A5A6)計算(A1A2A3A4A5A6)10矩陣A1A2A3A4A5A6數(shù)組pp0p1p1p2p2p3p3p4p4p5p5p6維數(shù)值3035351515551010202025根據(jù)MatrixChain動態(tài)規(guī)劃算法：計算mij數(shù)乘次數(shù)m25=min m22+m35+p1p2p5=

7、13000 m23+m45+p1p3p5=7125 m24+m55+p1p4p5=11375 最小值為最小值為7125，斷點的位置為，斷點的位置為3jipppjkmkimjijimjki1min01jkiA2 (A3 A4 A5)中的兩種情況：1. A2(A3(A4A5):m25=m22+m33+m45+p2p3p5+p1p2p5 2. A2 (A3 A4) A5)m25=m22+m34+m55+p2p4p5+p1p2p5(A2 A3)(A4 A5)(A2 A3A4) A511矩陣A1A2A3A4A5A6數(shù)組pp0p1p1p2p2p3p3p4p4p5p5p6維數(shù)值303535151555101

8、0202025根據(jù)根據(jù)MatrixChain動態(tài)規(guī)劃算法：動態(tài)規(guī)劃算法：計算計算sij（斷點（斷點K的位置）的位置）m25=min m22+m35+p1p2p5=13000 m23+m45+p1p3p5=7125 m24+m55+p1p4p5=11375 最小值為最小值為7125，斷點的位置為，斷點的位置為312int MatrixChain:MChain() /求求A0:n-1的最優(yōu)解值的最優(yōu)解值 for (int i=0;in; i+) mii=0; for (int r=2; r=n; r+) for (int i=0; i=n-r; i+) int j=i+r-1; mij=mi+1j+pi*pi+1*pj+1; /mij 的初值的初值 sij=i; for (int k=i+1; kj; k+) int t=mik+mk+1j+pi*pk+1*pj+1;if (tmij) mij=t; sij=k; return m0n-1;13void MatrixChain:Traceback(int i, int j)if(i=j) coutAi; return;if (isij) cout(; Traceback(i, sij); i