矩阵连乘(DP+递归+备忘录)

---

---

动态规划+递归+备忘录 解决矩阵连乘

问题描述：

给定n个矩阵：A1,A2,...,An，其中Ai与Ai+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。

矩阵之间相乘的公式：

矩阵相乘公式

为什么会有矩阵连乘这个问题呢？

看下面一个例子，计算三个矩阵连乘{A1，A2，A3}；维数分别为10＊100 , 100＊5 , 5＊50 按此顺序计算需要的次数((A1＊A2)＊A3):10X100X5+10X5X50=7500次，按此顺序计算需要的次数(A1＊(A2＊A3)):10＊5＊50+10＊100＊50=75000次
　　所以，确定一个最优的运算顺序，可以使计算量达到最小化。

动态规划解决：

#include<stdio.h>
#define N 6

void RecurMatrixChain(int* p,int** m){
    for(int r=2;r<N+1;r++){
        for(int i=1;i<=N-r+1;i++){
            int j=i+r-1;
            m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j];                  //先设个初始值，在i和i+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;
                }   
            }
        }
    }
}

int main(){
    int p[N+1]={30,35,15,5,10,20,25};
    
    int **m=new int*[N+1];       //m数组记录i到j的最优（最少）计算次数 
    for(int i=0;i<N+1;i++){
        m[i]=new int[N+1];
    }
    for(int i=1;i<N+1;i++){
        m[i][i]=0;
    }
    RecurMatrixChain(p,m);
    printf("少次数%d\n",m[1][N]);
    return 0;
} 

递归：

#include<stdio.h>
#define N 6

int RecurMatrixChain(int* p,int** s,int i,int j){
    if(i==j){
        return 0;
    }
    int u=32767;//代表从i到j的最少数乘次数
    for(int k=i;k<j;k++){
        int t=RecurMatrixChain(p,s,i,k)+RecurMatrixChain(p,s,k+1,j)+p[i-1]*p[k]*p[j];
        if(t<u){
            u=t;
            s[i][j]=k;
        }
    } 
    return u;
}

int main(){
    int p[N+1]={30,35,15,5,10,20,25};
    int **s=new int*[N+1];
    for(int i=0;i<N+1;i++){
        s[i]=new int[N+1];
    } 
    
    printf("最少次数%d\n",RecurMatrixChain(p,s,1,N));
    for(int i=0;i<N+1;i++){
        for(int j=0;j<N+1;j++){
            printf("%10d",s[i][j]);
        }
        printf("\n");
    } 
    
    return 0;
} 

备忘录：

#include<stdio.h>
#define N 6

int MemoMatrixChain(int* p,int** s,int** m,int i,int j){
    if(m[i][j]!=-1){
        return m[i][j];
    }
    if(i==j){
        return 0;
    }
    int u=32767;//u代表从i到j的最少数乘次数
    for(int k=i;k<j;k++){
        int t=MemoMatrixChain(p,s,m,i,k)+MemoMatrixChain(p,s,m,k+1,j)+p[i-1]*p[k]*p[j];
        s[i][j]=k;
        if(t<u){
            u=t;
            s[i][j]=k;
        }
        m[i][j]=u;
    } 
    return u;
}

int main(){
    int p[N+1]={30,35,15,5,10,20,25};
    
    int **s=new int*[N+1];        //s数组记录i到j的最优断开位置 
    for(int i=0;i<N+1;i++){
        s[i]=new int[N+1];
    }
    int **m=new int*[N+1];       //m数组记录i到j的最优（最少）计算次数 
    for(int i=0;i<N+1;i++){
        m[i]=new int[N+1];
    } 
    
    for(int i=1;i<N+1;i++){     //m数组的初始值为-1，表示问题都还没有解决 
        for(int j=1;j<N+1;j++){
            if(i==j){
                m[i][j]=0;
            }else{
                m[i][j]=-1;
            }
        }
    }
    
    printf("最少次数%d\n",MemoMatrixChain(p,s,m,1,N));
    return 0;
} 

运行截图