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

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) 之间将矩阵链断

2、开，i = 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)*(i)(注：

3、 p(i-1)为矩阵 A(i) 的行数， p(i) 为矩阵 Ai的列数 )实验实验代码#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 ;./ 记录每次子问题的结果void lookup_chain () _lookup_chain (1, count - 1) ;min_count = mc1count - 1 ;cout min_multi_count = min_count endl ;/ 输出最优计算次序_trackback (1, count - 1) ;/ 使用普通方法进行计算void calculate () int n = count - 1; /矩阵的个数/ 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 ;/ 列数intcount ;/ 矩阵个数+ 1vectorvector mc;/ 从第 i 个矩阵乘到

8、第j 个矩阵最小数乘次数vectorvector s;/ 最小数乘的切分位置intmin_count ;/ 最小数乘次数 ;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 ;实验结果实验验证连乘矩阵假如为：计算过程为：.从 m可知最小连乘次数为 m16 = 15125从 s 可知计算顺序为 (A1(A2A3)(A4