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

1、動態(tài)規(guī)劃法解矩陣連乘問題動態(tài)規(guī)劃法解矩陣連乘問題實(shí)驗(yàn)內(nèi)容給定n個矩陣A1,A2,其中Ai與Ai+1是可乘的，i=1,2,3n-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<=k<j,則其

2、相應(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)*(i)(注:p(i-1)為矩陣A(i)的行數(shù)，p(i)為矩陣Ai的列數(shù))實(shí)驗(yàn)實(shí)驗(yàn)

3、代碼#include<iostream>#include<vector>usingnamespacestd;classmatrix_chainpublic:matrix_chain(constvector<int>&c)cols=c;count=cols.size();mc.resize(count);s.resize(count);for(inti=0;i<count;+i)mci.resize(count);si.resize(count);for(i=0;i<count;+i)for(intj=0;j<count;+j)mci

4、j=0;sij=0;/記錄每次子問題的結(jié)果voidlookup_chain()_lookup_chain(1,count-1);min_count=mc1count-1;cout<<"min_multi_count="<<min_count<<endl;/輸出最優(yōu)計算次序_trackback(1,count-1);/使用普通方法進(jìn)行計算voidcalculate()intn=count-1;/矩陣的個數(shù)/r表示每次寬度/i,j表示從從矩陣i到矩陣j/k表示切割位置for(intr=2;r<=n;+r)for(inti=1;i<

5、=n-r+1;+i)intj=i+r-1;/從矩陣i到矩陣j連乘，從i的位置切割，前半部分為0mcij=mci+1j+colsi-1*colsi*colsj;sij=i;for(intk=i+1;k<j;+k)inttemp=mcik+mck+1j+colsi-1*colsk*colsj;if(temp<mcij)mcij=temp;sij=k;/fork/fori/forrmin_count=mc1n;cout<<"min_multi_count="<<min_count<<endl;/輸出最優(yōu)計算次序_trackback(

6、1,n);private:int_lookup_chain(inti,intj)/該最優(yōu)解已求出，直接返回if(mcij>0)returnmcij;if(i=j)return0;/不需要計算，直接返回/下面兩行計算從i到j(luò)按照順序計算的情況intu=_lookup_chain(i,i)+_lookup_chain(i+1,j)+colsi-1*colsi*colsj;sij=i;for(intk=i+1;k<j;+k)inttemp=_lookup_chain(i,k)+_lookup_chain(k+1,j)+colsi-1*colsk*colsj;if(temp<u)u=

7、temp;sij=k;mcij=u;returnu;void_trackback(inti,intj)if(i=j)return;_trackback(i,sij);_trackback(sij+1,j);cout<<i<<","<<sij<<""<<sij+1<<","<<j<<endl;private:vector<int>cols;/列數(shù)intcount;/矩陣個數(shù)+1vector<vector<int>

8、>mc;/從第i個矩陣乘到第j個矩陣最小數(shù)乘次數(shù)vector<vector<int>>s;/最小數(shù)乘的切分位置intmin_count;/最小數(shù)乘次數(shù);intmain()/初始化constintMATRIX_COUNT=6;vector<int>c(MATRIX_COUNT+1);c0=30;c1=35；c2=15;c3=5;c4=10;c5=20;c6=25;matrix_chainmc(c);/mc.calculate();mc.lookup_chain();return0;實(shí)驗(yàn)結(jié)果hij«i_mai111wiIl.J1JX彳AJFVk：11iLHI111-：VE.IllI：!£.HIIUK實(shí)驗(yàn)驗(yàn)證連乘矩陣假如為A1A2A3A4A5A630x3535>151555Z010x2020.25從m可知最小連乘次數(shù)為m16=15125從s可知計算順序?yàn)?A1(