动态规划法解矩阵连乘问题(5页).doc
-动态规划法解矩阵连乘问题实验内容给定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, 则其相应完全加括号方式为(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(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.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 - 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 < 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, 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) + 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<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 = 15125从s可知计算顺序为(A1(A2A3)(A4A5)A6)实验总结在这次实验中懂得了动态规划法运用方法和解题思路的重要性 ，在这个程序中如何建立动态规划的过程建立递归过程保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。-第 5 页-
