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

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(

3、i) 的维数为p(i-1)*(i)( 注： 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)

4、;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 - 1) ;/ 使用普通方法进行计算void calculate () int n = count - 1; / 矩阵的个数/ r

5、表示每次宽度/ 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 的位置切割，前半部分为 0 mcij = 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 mci

6、j) mcij = temp ; sij = k ; / for 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

7、temp = _lookup_chain(i, k) + _lookup_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:vector cols ; / 列数int count ; / 矩阵

8、个数 + 1vectorvector mc; / 从第 i 个矩阵乘到第 j 个矩阵最小数乘次数 vectorvector s; / 最小数乘的切分位置int min_count ; / 最小数乘次数 ;int main()/ 初始化const int MATRIX_COUNT = 6 ;vector c(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)(A4A