動(dòng)態(tài)規(guī)劃法解矩陣連乘問(wèn)題

1、.動(dòng)態(tài)規(guī)劃法解矩陣連乘問(wèn)題實(shí)驗(yàn)內(nèi)容給定 n 個(gè)矩陣 A1,A2, .An ，其中Ai 與 Ai+1 是可乘的， i=1,2,3。， n-1 。我們要計(jì)算這 n 個(gè)矩陣的連乘積。 由于矩陣乘法滿足結(jié)合性， 故計(jì)算矩陣連乘積可以有許多不同的計(jì)算次序。這種計(jì)算次序可以用加括號(hào)的方式確定。若一個(gè)矩陣連乘積的計(jì)算次序完全確定，也就是說(shuō)該連乘積已完全加括號(hào)，則我們可依此次序反復(fù)調(diào)用2 個(gè)矩陣相乘的標(biāo)準(zhǔn)算法計(jì)算出矩陣連乘積。解題思路將矩陣連乘積 A(i)A(i+1) A(j) 簡(jiǎn)記為 Ai:j，這里 i = j?？疾煊?jì)算 Ai:j的最優(yōu)計(jì)算次序。設(shè)這個(gè)計(jì)算次序在矩陣A(k) 和 A(k+1) 之間將矩陣鏈斷

2、開(kāi)，i = k j,則其相應(yīng)完全加括號(hào)方式為 (A(i)A(i+1) A(k) * (A(k+1)A(k+2) A(j)。特征：計(jì)算 Ai:j 的最優(yōu)次序所包含的計(jì)算矩陣子鏈Ai:k和 Ak+1:j 的次序也是最優(yōu)的。矩陣連乘計(jì)算次序問(wèn)題的最優(yōu)解包含著其子問(wèn)題的最優(yōu)解。設(shè)計(jì)算 Ai:j ， 1 = i = j = n，所需要的最少數(shù)乘次數(shù)mi,j，則原問(wèn)題的最優(yōu)值為m1,n當(dāng) i = j時(shí)， Ai:j=Ai，因此， mi,i = 0，i = 1,2, ,n當(dāng) i j時(shí)， mi,j = mi,k + mk+1,j + p(i-1)p(k)p(j)這里 A(i) 的維數(shù)為p(i-1)*(i)(注：

3、 p(i-1)為矩陣 A(i) 的行數(shù)， p(i) 為矩陣 Ai的列數(shù) )實(shí)驗(yàn)實(shí)驗(yàn)代碼#include #include using namespace std ;class matrix_chainpublic:matrix_chain(const vector & c) cols = c ;count = cols.size () ;mc.resize (count) ;s.resize (count) ;for (int i = 0; i count; +i) mci.resize (count) ;si.resize (count) ;for (i = 0; i count; +i)

4、for (int j = 0; j count; +j) mcij = 0 ;sij = 0 ;./ 記錄每次子問(wèn)題的結(jié)果void lookup_chain () _lookup_chain (1, count - 1) ;min_count = mc1count - 1 ;cout min_multi_count = min_count endl ;/ 輸出最優(yōu)計(jì)算次序_trackback (1, count - 1) ;/ 使用普通方法進(jìn)行計(jì)算void calculate () int n = count - 1; /矩陣的個(gè)數(shù)/ r 表示每次寬度/ i,j 表示從從矩陣 i 到矩陣 j/

5、 k 表示切割位置for (int r = 2; r = n; + r) for (int i = 1; i = n - r + 1; + i) int j = i + r - 1 ;/ 從矩陣 i 到矩陣 j 連乘，從i 的位置切割，前半部分為0mcij = mci+1j + colsi-1 * colsi * colsj ;sij = i ;for (int k = i + 1; k j; + k) int temp = mcik + mck + 1j +colsi-1 * colsk * colsj ;if (temp mcij) mcij = temp ;sij = k ; / for

6、 k / for i / for rmin_count = mc1n ;cout min_multi_count = min_count 0) return mcij ;if (i = j) return 0 ;/ 不需要計(jì)算，直接返回/ 下面兩行計(jì)算從 i 到 j 按照順序計(jì)算的情況int u = _lookup_chain (i, i) + _lookup_chain (i + 1, j)+ colsi-1 * colsi * colsj ; sij = i ;for (int k = i + 1; k j; + k) int temp = _lookup_chain(i, k) + _l

7、ookup_chain(k + 1, j)+ colsi - 1 * colsk * colsj ; if (temp u) u = temp ; sij = k ;mcij = u ;return u ;void _trackback (int i, int j) if (i = j) return ;_trackback (i, sij) ;_trackback (sij + 1, j) ;cout i , sij sij + 1 , j endl;private:vectorcols ;/ 列數(shù)intcount ;/ 矩陣個(gè)數(shù)+ 1vectorvector mc;/ 從第 i 個(gè)矩陣乘到

8、第j 個(gè)矩陣最小數(shù)乘次數(shù)vectorvector s;/ 最小數(shù)乘的切分位置intmin_count ;/ 最小數(shù)乘次數(shù) ;int main()/ 初始化const int MATRIX_COUNT = 6 ;.vectorc(MA TRIX_COUNT + 1) ;c0= 30 ;c1= 35 ;c2= 15 ;c3= 5 ;c4= 10 ;c5= 20 ;c6= 25 ;matrix_chain mc (c) ;/ mc.calculate () ; mc.lookup_chain () ; return 0 ;實(shí)驗(yàn)結(jié)果實(shí)驗(yàn)驗(yàn)證連乘矩陣假如為：計(jì)算過(guò)程為：.從 m可知最小連乘次數(shù)為 m16 = 15125從 s 可知計(jì)算順序?yàn)?(A1(A2A3)(A4