動態(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個矩陣相乘的標(biāo)準(zhǔn)算法計算出矩陣連乘積。解題思路將矩陣連乘積 A(i)A(i+1)A(j)簡記為Ai:j,這里i <= j 。考察計算 Ai:j 的最優(yōu)計算次序。設(shè)這個計算次序在矩陣 A(k)和A(k+1)之間將矩陣鏈斷開，i <=

2、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當(dāng) i = j 時，Ai:j=Ai ,因此，mi,i = 0, i = 1,2,n當(dāng) i <j 時，mi,j = mi,k + mk+1,j + p(i-1)p(k)p(j)這里 A(i)的維數(shù)為p(i-1)*

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

4、t); si.resize (count);for (i = 0; i < count; +i) 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 -

5、 1);)/使用普通方法進行計算void calculate () int n = count - 1; /矩陣的個數(shù)/ r表示每次寬度/ i,j表示從從矩陣i到矩陣j/ 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 te

6、mp = mcik + mck + 1j +colsi-1 * colsk * colsj;if (temp < mcij) mcij = temp ;sij = k ;) / for k / for i / for rmin_count = mc1n;cout << "min_multi_count = "<< min_count << endl ;/輸出最優(yōu)計算次序_trackback (1, n);private:int _lookup_chain (int i, int j) /該最優(yōu)解已求出，直接返回if (mcij &g

7、t; 0) return mcij;)if (i = j) return 0 ;/不需要計算，直接返回)/下面兩行計算從i到j(luò)按照順序計算的情況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) + _lookup_chain(k + 1, j) + colsi - 1 * colsk * colsj;if (temp < u) u

8、 = 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:vector<int>

9、; cols ;/ 列數(shù)intcount ;/ 矩陣個數(shù) + 1vector<vector<int> > mc; /從第i個矩陣乘到第j個矩陣最小數(shù)乘次數(shù)vector<vector<int> > s;/最小數(shù)乘的切分位置intmin_count ;/最小數(shù)乘次數(shù) int main() /初始化const int MATRIX_COUNT = 6 ;vector<int> c(MA TRIX_COUNT + 1);c0 = 30 ;c1 = 35 ;c2 = 15 ;c3 = 5 ;c4 = 10 ;c5 = 20 ;c6 = 25 ;

10、matnx_chain mc (c);/ mc.calculate (); mc.lookup_chain (); return 0 ;實驗結(jié)果|nin_nult i_couLnta,23.3k.374,6Press Hny to continue實驗驗證連乘矩陣假如為:A1A2A3A4A5A630x3535x1515x55x1010x2020x25計算過程為:r jjj1 2 3 4 5 &T-f+1 1234561234 5b1 1 0 157W 用費 93T5 11S75 15135110115352O 2626的 51126 10500202331A$0 ?SO 2500 m30333_4Q 1000 WKO4045 50 5000&0&6 Ji6 06件©訶苴就序a瓶皿(C)中解從m可知最小連