算法分析之矩阵连乘问题

本是古典何须时尚 2022-12-08 14:15 183阅读 0赞

## 算法分析之矩阵连乘问题 ##

**一，问题描述**

给定n个矩阵｛A1,A2,…,An｝，其中，Ai与Ai+1是可乘的，(i=1,2 ,…,n-1)。不同的计算次序计算量（乘法次数）是不同的，要求通过输入矩阵的个数和每个矩阵的规模大小，从而确定矩阵连乘积的计算次序和最少数乘次数使得矩阵连乘的次数最小。

**分析：**  
矩阵连乘的条件：第一个矩阵的列等于第二个矩阵的行，此时两个矩阵是可乘的；  
多个矩阵连乘的结果矩阵，其行列等于第一个矩阵的行和最后一个矩阵的列；  
两个矩阵相乘的计算量：

**例如**：![在这里插入图片描述][20200919185135152.png_pic_center]

可知总执行次数为：3*2*4=24.

所以矩阵Am*n和Bn*k的乘法运算次数为：m*n*k；

矩阵连乘AiAi+1Ai+2……Aj的最优解问题

假设在第k位置上找到最优解，则问题变成了两个子问题：（AiAi+1……Ak），（Ak+1……Aj），用m\[i\]\[j\]表示矩阵连乘的最优值，那么两个子问题对应的最优值变成m\[i\]\[k\],m\[k+1\]\[j\];，设矩阵Am的行数为Pm，列数为qm，矩阵是可连乘的，即相邻矩阵qm=Pm+1，所以（AiAi+1……Ak）可表示为Pi \* qk，（Ak+1……Aj）可表示为Pk+1 \* qj，qk = Pk+1.则两个矩阵连乘的乘法次数为Pi \* Pk+1 \* qj。

5.矩阵连乘最优值递归式  
![在这里插入图片描述][20200919184845778.png_pic_center]

**程序实现**

```c
    #include <stdio.h>
    #include <iostream> 
    using namespace std; 
    const int L = 7;                  //矩阵连乘的个数
    int LianCheng(int n,int **m,int **s,int *p); 
    void Traceback(int i,int j,int **s);//构造最优解
    int main()
    {
        
    	int p[L]={
        11,22,33,44,55,66,77};   
     int **s = new int *[L];
    	int **m = new int *[L];
    	//矩阵的维数为11*22,22*33,...66*77
    for(int i=0;i<L;i++)  
        {
          
    		s[i] = new int[L];
    		m[i] = new int[L];
        } 
    	cout<<"矩阵的最少计算次数为："<<LianCheng(6,m,s,p)<<endl;
    	cout<<"矩阵最优计算次序为："<<endl;
    	Traceback(1,6,s);
    	return 0;
    }
    int LianCheng(int n,int **m,int **s,int *p)
    {
        
    	for(int i=1; i<=n; i++)
    	{
        
    		m[i][i] = 0;
    	}
    	for(int r=2; r<=n; r++)         //r为当前计算的链长（子问题规模）  
    	{
        
    		for(int i=1; i<=n-r+1; i++)  //n-r+1为最后一个r链的前边界  
    		{
        
    			int j = i+r-1;      //计算前边界为r，链长为r的链的后边界  
    			m[i][j] = m[i+1][j] + p[i-1]*p[i]*p[j];
    //将链ij划分为A(i) * ( A[i+1:j] ) 
    
    			s[i][j] = i;
    			for(int k=i+1; k<j; k++)
    			{
        
    				             //将链ij划分为( A[i:k] )* (A[k+1:j])   
    				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;
    				}
    			}
    		}
    	}
    	return m[1][L-1];
    }
    void Traceback(int i,int j,int **s)
    {
        
    	if(i==j) return;           //只有一个矩阵，直接输出
    	Traceback(i,s[i][j],s);  //递归，输出从得到的最优解s[i][j]处断开之前的值
    	Traceback(s[i][j]+1,j,s);//递归，输出从得到的最优解s[i][j]处断开之前的值
    	cout<<"Cheng A"<<i<<","<<s[i][j];
    	cout<<" and A"<<(s[i][j]+1)<<","<<j<<endl;
    }
    }

**实验结果与分析**  
![在这里插入图片描述][2020091918520297.png_pic_center]

用动态规划迭代方式解决此问题，可依据其递归式自底向上的方式进行计算。在计算过程中，保存已解决的子问题的答案。每个子问题只计算一次，而在后面需要时只需简单检查一下，从而避免了大量的重复计算，最终得到多项式时间的算法。

[20200919185135152.png_pic_center]: /images/20221123/fc792a9d32044d9a9b97dabd818a4d7c.png
[20200919184845778.png_pic_center]: /images/20221123/c8d9c2b050cb4d539b40440a2fd19f6d.png
[2020091918520297.png_pic_center]: /images/20221123/3af4ed6f09b24a6e8ddbbac5832bf7e9.png