矩阵连乘最优结合 动态规划求解分析

熊孩纸 阅读:347 2020-10-19 15:34:55 评论:0

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));  //A 
37     data.push_back(make_pair(100,5));   //B 
38     data.push_back(make_pair(5,25));    //C 
39     data.push_back(make_pair(25,15));   //D 
40     data.push_back(make_pair(15,20));   //E 
41  
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;  ///自己和自己相乘,所以为0 
51             else 
52                 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 }
View Code

输入矩阵,表示每个矩阵的行、列:

输出最优的结合表达式:

  

声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
排行榜
关注我们

一个IT知识分享的公众号