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

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 <= k < j, 则

2、其相应完全加括号方式为(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)(注：p(i-1)为矩阵A(

3、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 (count) ; si.res

4、ize (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, coun

5、t - 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的位置切割，前半部分为0 mcij = mci+1j + colsi-1 * colsi * colsj ; sij = i ; for (int k = i + 1; k

6、< j; + k) int temp = mcik + mck + 1j + colsi-1 * colsk * colsj ; if (temp < mcij) mcij = temp ; sij = k ; / for k / for i / for r min_count = mc1n ; cout << "min_multi_count = "<< min_count << endl ; / 输出最优计算次序 _trackback (1, n) ; private: int _lookup_chain (int i,

7、int j) / 该最优解已求出，直接返回 if (mcij > 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) + co

8、lsi - 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 << "," &

9、lt;< j << endl; private: vector<int> cols ; / 列数 int count ; / 矩阵个数 + 1 vector<vector<int> > mc; / 从第i个矩阵乘到第j个矩阵最小数乘次数 vector<vector<int> > s; / 最小数乘的切分位置 int min_count ; / 最小数乘次数 ;int main() / 初始化 const int MATRIX_COUNT = 6 ; vector<int> c(MATRIX_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 =