动态规划法解矩阵连乘问题

1、动态规划法解矩阵连乘问题实验内容给定n个矩阵A1,A2, ,An,其中 Ai与Ai+1是可乘的，i=1,2,3 。一,n-1。我们要计 算这n个矩阵的连乘积。由于矩阵乘法满足结合性，故计算矩阵连乘积可以有许多不同的计 算次序。这种计算次序可以用加括号的方式确定。若一个矩阵连乘积的计算次序完全确定， 也就是说该连乘积已完全加括号，则我们可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。解题思路将矩阵连乘积 A(i)A(i+1)A(j)简记为Ai:j,这里i <= j 。考察计算 Ai:j 的最优计算次序。设这个计算次序在矩阵 A(k)和A(k+1)之间将矩阵链断开，i <=

2、k < j, 则其相应 完全加括号方式为(A(i)A(i+1)A(k) * (A(k+1)A(k+2)A(j)。特征：计算Ai:j的最优次序所包含的计算矩阵子链Ai:k和Ak+1:j的次序也是最优的。矩阵连乘计算次序问题的最优解包含着其子问题的最优解。设计算Ai:j ,1 <= i <= j <= n，所需要的最少数乘次数mi,j，则原问题的最优值为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)的维数为p(i-1)*

3、(i)( 注：p(i-1)为矩阵A(i)的行数，p(i)为矩阵Ai的列数) 实验实验代码#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 ;/记录每次子问题的结果void lookup_chain () _lookup_chain (1, count - 1);min_count = mc1count - 1;cout << "min_multi_count = "<< min_count << endl ;/输出最优计算次序_trackback (1, count -

5、 1);)/使用普通方法进行计算void calculate () int n = count - 1; /矩阵的个数/ 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 ;/输出最优计算次序_trackback (1, n);private:int _lookup_chain (int i, int j) /该最优解已求出，直接返回if (mcij &g

7、t; 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) + _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 ;/ 列数intcount ;/ 矩阵个数 + 1vector<vector<int> > mc; /从第i个矩阵乘到第j个矩阵最小数乘次数vector<vector<int> > s;/最小数乘的切分位置intmin_count ;/最小数乘次数 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 ;实验结果|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可知最小连