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

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

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

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

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

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

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

7、13000 m23+m45+p1p3p5=7125 m24+m55+p1p4p5=11375 最小值為最小值為7125，斷點(diǎn)的位置為，斷點(diǎn)的位置為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動(dòng)態(tài)規(guī)劃算法：動(dòng)態(tài)規(guī)劃算法：計(jì)算計(jì)算sij（斷點(diǎn)（斷點(diǎn)K的位置）的位置）m25=min m22+m35+p1p2p5=13000 m23+m45+p1p3p5=7125 m24+m55+p1p4p5=11375 最小值為最小值為7125，斷點(diǎn)的位置為，斷點(diǎn)的位置為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