動態(tài)規(guī)劃法解矩陣連乘問題

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

2、開，i = k j,則其相應(yīng)完全加括號方式為 (a(i)a(i+1) a(k) * (a(k+1)a(k+2) a(j)。特征：計算 ai:j 的最優(yōu)次序所包含的計算矩陣子鏈ai:k和 ak+1:j 的次序也是最優(yōu)的。矩陣連乘計算次序問題的最優(yōu)解包含著其子問題的最優(yōu)解。設(shè)計算 ai:j ， 1 = i = j = n，所需要的最少數(shù)乘次數(shù)mi,j，則原問題的最優(yōu)值為m1,n當 i = j時， ai:j=ai，因此， mi,i = 0，i = 1,2, ,n當 i j時， 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ù) )實驗實驗代碼#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 ;./ 記錄每次子問題的結(jié)果void lookup_chain () _lookup_chain (1, count - 1) ;min_count = mc1count - 1 ;cout min_multi_count = min_count endl ;/ 輸出最優(yōu)計算次序_trackback (1, count - 1) ;/ 使用普通方法進行計算void calculate () int n = count - 1; /矩陣的個數(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 ;/ 不需要計算，直接返回/ 下面兩行計算從 i 到 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 ;/ 矩陣個數(shù)+ 1vectorvector mc;/ 從第 i 個矩陣乘到

8、第j 個矩陣最小數(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 ;實驗結(jié)果實驗驗證連乘矩陣假如為：計算過程為：.從 m可知最小連乘次數(shù)為 m16 = 15125從 s 可知計算順序為 (a1(a2a3)(a4