算法设计——矩阵连乘问题

时间:2024-03-09 14:50:34

白天什么也没学,晚上才终于拿着笔,对着代码,写写画画,终于看明白是怎么计算的了。


 

以这6个矩阵连乘作为例子

A1 A2 A3 A4 A5 A6
30*35 35*15 15*5 5*10 10*20 20*25

 

 

 

1 首先,要明白两个矩阵相乘所需要做的乘法次数:

2 由于连乘的矩阵必须满足,前一个矩阵的列数=后一个矩阵的行数,所以可以使用一个数组来存储连乘矩阵的行列数:

p[7]={30,35,15,5,10,20,25};

3 分析最优解的结构:

A[i:j]表示矩阵i到矩阵j的连乘,那么A[i:j]=A[i:k]+A[k+1:j]+p[i-1]*p[k]*p[j](这两个矩阵相乘所需的乘法次数);

如果A[i:j]的所需要的乘法次数是最少的,那么A[i:k]和A[k+1:j]所需要的乘法次数也应该是最少的,否则A[i:j]就不是最优的,所以满足最优子结构性质;

4 建立递归关系:

m[i][j]表示矩阵i连乘到矩阵j的最少乘次数,那么原问题的最优值是m[1,n];

当i=j时,为单个矩阵,m[i][i]=0;

当i<j时,利用最优子结构性质来计算;

获得以下递归定义: 

m[i][j]=0;    i=j

m[i][j]=mini<=k<j{m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]};  i<j

如果需要得出最优解的加括号结果,需要另一个二维数组s[i][j],用于记录使m[i][j]获得最优解的断点,k值;

5 分析代码

 1 int m[8][8]={0},s[8][8]={0};
 2 
 3 void MaxtrixChain(int *p,int n){
 4     for(int i=1;i<=n;i++) m[i][i]=0;
 5     for(int r=2;r<=n;r++)
 6         for(int i=1;i<=n-r+1;i++){
 7             int j=i+r-1;
 8             m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
 9             s[i][j]=i;
10             
11             for(int k=i+1;k<j;k++){
12                 int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
13                 if(t<m[i][j]){
14                     m[i][j]=t;
15                     s[i][j]=k;
16                 }
17             }
18         }
19 }

书上写了“依据其递归式自底向上的方式进行计算”,没拿出笔画之前,我真的没看懂这句话到底是怎么自底向上的,于是我要开始写写画画了;

我们先暂时只看下面这部分代码:

void MaxtrixChain(int *p,int n){
    for(int i=1;i<=n;i++) m[i][i]=0;
    for(int r=2;r<=n;r++){
        for(int i=1;i<=n-r+1;i++){
            int j=i+r-1;
            m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];
        }
} }

 

具体用数据分析一下

把右图补充完整,将得到以下结果:这是我理解的自底向上地计算;

接下来看另一部分代码:

    for(int r=2;r<=n;r++){
        for(int i=1;i<=n-r+1;i++){
            int j=i+r-1;
            
            for(int k=i+1;k<j;k++){
                int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];
                if(t<m[i][j]){
                    m[i][j]=t;
                    s[i][j]=k;
                }
            }
        }
    }

所以我们需要把这两部分代码结合起来使用:

那么对于m[1][4]我们是枚举了所有加括号的可能情况,并存储了其中最小的一个,获得了最优值;

那么对于m[2][5]、m[3][6]也能得到最优值;并且没有做任何重复计算;

当r=5时,m[1][5]、m[2][6]也能得到最优值;

当r=6时,m]1][6]也能得到最优值;如此就得到了原问题的最优解;

 每一次得到更小值的时候,s[i][j]=k,记录(更新)这个断点情况;最后可以用来帮助构造最优解的加括号形式;

6 以下给出完整源代码:

 1 #include<iostream>
 2 using namespace std;
 3 
 4 //矩阵连乘:完全加括号问题
 5 //A1(p1*p2),A2(p2*p3),两个矩阵相乘,总乘法次数为p1*p2*p3,其中p2表示结果的每个元素所需要的乘法次数
 6 //m[i][j]表示,第i个矩阵到第j个矩阵的连乘,所需要的乘法次数
 7 //对于多个矩阵连乘,可以得出以下递推式
 8 //m[i][j]=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]
 9 //问题是如何找到这个k,使乘法次数最少
10 int m[7][7]={0};    //m[i][j]用于存储,第i个矩阵连乘到第j个矩阵的乘法次数,那么m[1][n]为最终结果
11 int s[7][7]={0};    //s[i][j]用于存储,矩阵i和矩阵j之间所取的断点,k值,用于构造结果的加括号情况
12 
13 void MatrixChain(int n,int p[]){
14     for(int i=1;i<=n;i++)   m[i][i]=0;      //单个矩阵乘法次数为0
15     
16     //采用自底向上的方式实现递推式
17     for(int r=2;r<=n;r++){       //表示r个矩阵的连乘
18         for(int i=1;i<=n-r+1;i++){  //从第i个矩阵开始,作为连乘的起点,有r个矩阵连乘,所以要<=n-r+1
19             int j=i+r-1;        //j-i=r-1,表示j是r个矩阵连乘中的终点
20             m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; 
21                 //相当于m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j],显然m[i][i]=0
22                 //即表示Ai……Aj=Ai(Ai+1……Aj),从最后一个开始加括号
23             s[i][j]=i;
24             
25             for(int k=i+1;k<j;k++){
26                 int t=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];   //在i~j中寻找k
27                 if(t<m[i][j]){
28                     m[i][j]=t;      //记录t历史上的最小值,最终结果即为连乘中的最优值
29                     s[i][j]=k;      //记录断点k值
30                 }
31             }
32 
33         }
34     }
35 }
36 
37 //利用s[i][j]进行构造连乘的加括号情况
38 void TraceBack(int i,int j){
39     if(i==j) return;
40     TraceBack(i,s[i][j]);   //以s[i][j]记录的k为分界点,找左边,i~k
41     TraceBack(s[i][j]+1,j); //找右边,k+1~j
42     cout<<"Matrix A"<<i<<","<<s[i][j];
43     cout<<" and A"<<s[i][j]+1<<","<<j<<endl;
44 }
45 
46 int main(){
47     int arr[7]={30,35,15,5,10,20,25};
48     int n=6;
49     MatrixChain(n,arr);
50     TraceBack(1,n);
51     cout<<m[1][n]<<endl;
52     system("pause");
53     return 0;
54 }

 

哇本渣终于弄清楚矩阵连乘了!!