首页 > 代码库 > 矩阵连乘最优结合 动态规划求解
矩阵连乘最优结合 动态规划求解
1.引言 多矩阵连乘
对于一般的矩阵乘法来说，如矩阵A(m,n)与矩阵B(n,p)相乘需要进行的加法次数为m*n*p次乘法。
由于矩阵乘法满足结合律，因此矩阵相乘的结合性，会影响整个计算表达式的乘法执行次数。
如下面的例子，其中A(10,5)、B(5,20)、C(20,3)：
(1) ((AB)C) 执行乘法次数为1300次
(2) (A(BC)) 执行乘法次数为450次
2.求最优的矩阵结合表达式
(1)设矩阵连乘积AiAi+1…Aj简记为A[i:j]，设最优计算次序在Ak和Ak+1之间断开，则加括号方式为：
((AiAi+1…Ak) (Ak+1…Aj) )
则依照这个次序，先计算A[i:k]和A[k+1:j]然后再将计算结果相乘，计算量是：
A[i:k]的计算量+A[K+1:j]的计算量+它们两者相乘的计算量
这里的关键是：计算A[i:j]的最优次序所包含的两个子过程（计算A[i:k]和A[K+1:j]）也是最优次序
(2)具体计算
设计算A[i,j]需要的乘法次数记为m[i,j]。
M[i,j] = 0; (i == j，表示一个矩阵，当然不需要乘法运算)
M[i,j] = min(M[i,k]+M[k+1,j]+pi*pk*pj); (k在[i,j)之间取值，表示分割点的位置，求最适合的分割点使得乘法次数最少)
下面是使用动态规划计算6个矩阵连乘的示意图。可以使用自底向上计算，这样矩阵的分割点好计算。如先计算01两个矩阵乘积，在计算02三个矩阵乘积，在计算03四个矩阵乘积：
01 12 23 34 45
02 13 24 35
03 14 25
04 15
05
3.程序实例
程序可以根据给出的多个矩阵的行、列，生成最优结合的相乘表达式。
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <limits.h> 5 #include <string> 6 using namespace std; 7 ///计算M矩阵 8 int calculate_M(vector<vector<int> >&num,vector<pair<int,int> > &data,vector<vector<int> > &points){ 9 int len = data.size();10 for(int span = 1;span<len;span++){ ///间隔距离11 for(int col=0;col<len-span;col++){ ///操作起始列12 13 for(int i=col;i<col+span;i++){14 int tmp = num[col][i] + num[i+1][col+span] + data[col].first*data[i].second*data[col+span].second;15 if(tmp < num[col][col+span]){16 points[col][col+span] = i; ///记录分割点17 num[col][col+span] = tmp; ///记录最少乘法次数18 }19 }20 }21 }22 return 0;23 }24 25 ///根据记录的分割点，生成最后的矩阵相乘表达式26 string make_result(vector<vector<int> > &points,int t1,int t2){27 if(t1 == t2)28 return string(1,‘A‘+t1);29 int split = points[t1][t2];30 return "("+make_result(points,t1,split)+"*"+make_result(points,split+1,t2)+")";31 }32 33 int main()34 {35 vector<pair<int,int>> data; ///保存矩阵的行、列36 data.push_back(make_pair(10,100)); //A37 data.push_back(make_pair(100,5)); //B38 data.push_back(make_pair(5,25)); //C39 data.push_back(make_pair(25,15)); //D40 data.push_back(make_pair(15,20)); //E41 42 43 int len = data.size();44 vector<vector<int> > num(len,vector<int>(len)); ///定义二维向量，并预先分配空间，记录乘法次数45 vector<vector<int> > points(len,vector<int>(len)); ///定义二维向量，并预先分配空间，记录分割点46 for(int i=0;i<len;i++){47 for(int j=0;j<len;j++){48 points[i][j] = -1;49 if(i == j)50 num[i][j] = 0; ///自己和自己相乘，所以为051 else52 num[i][j] = INT_MAX; ///否则，记为最大整数值53 }54 }55 56 calculate_M(num,data,points);57 cout<<make_result(points,0,len-1)<<"\t最少乘法次数为:"<<num[0][len-1]<<endl;58 return 0;59 }
输入矩阵，表示每个矩阵的行、列：
输出最优的结合表达式：
矩阵连乘最优结合 动态规划求解