• 计算机算法分析与设计(4)---矩阵连乘问题(含C++代码)



    一、概述

    1.1 矩阵乘法

     1. 矩阵相乘,前一个矩阵的列数需等于后一个矩阵的行数。相乘得到的新矩阵,其行数由前一个矩阵决定,其列数由后一个矩阵决定。

     2. 完全加括号的矩阵连乘积可递归地定义为:

    • 单个矩阵是完全加括号的。
    • 矩阵连乘积X是完全加括号的,则X可表示为2个完全加括号的矩阵连乘积,即Y和Z的乘积并加括号,即 X=(YZ) ,Y和Z也是完全加括号的。
    • 例如四个矩阵连乘积ABCD:(A((BC)D))、(A(B(CD)))、((AB)(CD))、(((AB)C)D)、((A(BC))D)。

     3.(1)由于矩阵乘法满足结合律,所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。(2)若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已完全加括号,则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。

     4. 如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。

    在这里插入图片描述
    在这里插入图片描述

    1.2 穷举法

     1. 穷举法:列举出所有可能的计算次序,并计算出每一种计算次序相应需要的数乘次数,从中找出一种数乘次数最少的计算次序。

     2. 算法复杂度分析:n个矩阵的连乘积,设不同的计算次序为P(n)。因每种加括号方式都可以分解为两个子矩阵的加括号问题:(A1…Ak)(Ak+1…An),故P(n)的递推式如下:

    在这里插入图片描述
     3. 穷举法:计算量非常大,这种方案不可行。

    1.3 动态规划

     1. 将矩阵连乘积Ai Ai+1 … Aj,简记为A[i:j] ,这里i≤j。考察计算A[i:j]的最优计算次序,设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开,i≤k

    在这里插入图片描述
    结论:计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k+1:j]的次序也是最优的。

     2. 建立递归关系:

    • 设计算A[i:j],1≤i≤j≤n,所需的最少数乘次数m[i,j],则原问题的最优值为m[1,n]。
    • 当i=j时,A[i:j]=Ai,因此,m[i,i]=0,i=1,2,…,n。
    • 当i

    综述,递推关系如下:

    在这里插入图片描述

    二、代码编写

    2.1 例题分析

    在这里插入图片描述
    在这里插入图片描述

    2.2 代码

    #include
    using namespace std;
    #define N 7
    
    //计算最优值 
    void MatrixChain(int *p,int n,int m[][N],int s[][N]){
    	for(int i=1;i<=n;i++){  //矩阵链中只有一个矩阵时,次数为0
    		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; //矩阵链的末尾矩阵,注意r-1,因为矩阵链为2时,实际是往右+1
    			m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j]; 
    			s[i][j]=i;
    			
    			for(int k=i+1;k < j;k++){  //这里面将断链点从i+1开始,可以断链的点直到j-1为止
                    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;
                    }
                }
    		}
    		
    	}
    	
    }
    
    //构造最优解 
    void Traceback(int i,int j,int s[][N]){
        if(i==j)       //回归条件
        {
            cout<<"A"<<i;
        }
        else       //按照最佳断点一分为二,接着继续递归
        {
            cout<<"(";
            Traceback(i,s[i][j],s);
            Traceback(s[i][j]+1,j,s);
            cout<<")";
        }
    }
    int main(){
    	int p[N]={30,35,15,5,10,20,25};
    	int m[N][N],s[N][N];
     
    	MatrixChain(p,N-1,m,s); //N-1因为只有六个矩阵
    	cout<<"矩阵的最佳乘积方式为: "; 
        Traceback(1,6,s);
    	return 0;
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
  • 相关阅读:
    Grafana安装后web打开报错
    神舟电脑怎么清理缓存文件?介绍几种简单有效方法
    如何在 Jenkins CI/CD 流水线中保护密钥?
    PerfView专题 (第一篇): 如何寻找热点函数
    [附源码]java毕业设计农村留守儿童帮扶系统
    破局 NFT 困境:实用型 NFT 是什么?
    D2. Dances (Hard Version) Codeforces Round 905 (Div. 2)
    TAO 训练时遇到 docker报错
    网站攻击技术,一篇打包带走!
    30m退耕还湿空间数据集(2000-2010年,西南地区)
  • 原文地址:https://blog.csdn.net/m0_62881487/article/details/133241319