矩阵连乘（动态规划算法）

问题提出：

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

问题分析：

由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。

例如，计算三个矩阵连乘{A1，A2，A3}；维数分别为10×100 , 100×5 , 5×50 按此顺序计算需要的次数((A1A2)A3):10X100X5+10X5X50=7500次，按此顺序计算需要的次数(A1(A2A3)):10550+1010050=52500次。

所以问题是：如何确定运算顺序，可以使计算量达到最小化。

算法思路：

• m[i][j] 表示A[i:j]的计算量 ；
• A[i:k]的计算量为m[i][k];
• A[k+1 : j]的计算量为m[k+1][j]

因此，m[i][j] = m[i][k] + m[k+1][j] + p[i-1] * p[i] * p[j];

（p[i-1] * p[i] * p[j]：最后两个矩阵的计算量）

动态规划算法代码：

#include<iostream>
#include<vector>
using namespace std;

const int L = 7;

int matrixMultiple(int n, vector< vector<int> > &m, vector< vector<int> > &s, int p[]){

    for(int i = 1; i < n; i++){  
        //对角线设为0，没有自己和自己乘
        m[i][i] = 0;
    }

    for(int r = 2; r <= n; r++){ //r为规模

        for(int i = 1; i <= n-r+1; i++){  //i:首矩阵编号

            int j = i + r - 1;  //尾矩阵编号
            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++){  //k:断开的位置
                //将链ij划分为(A[i:k] + A[k+1 : j])
                int temp = m[i][k] + m[k + 1][j] + p[i-1]*p[k]*p[j];
                if(temp < m[i][j]){
                    m[i][j] = temp;
                    s[i][j] = k;
                }
            }
        }
    }
    return m[1][L-1];
}

void traceBack(int i, int j, vector< vector<int> > &s){

    if(i == j)
        return ;

    traceBack(i, s[i][j], s);
    traceBack(s[i][j] + 1, j, s);
    cout << "Multiple A[" << i << ", " << s[i][j] << "]";
    cout << " and A[" << (s[i][j] + 1) << ", " << j << "]" << endl;
}

int main(){
    
//A1:30*35 A2:35*15 A3:15*5 A4:5*10 A5:10*20 A6:20*25
//p[0-6]={30,35,15,5,10,20,25}

	int p[L]={30, 35, 15, 5, 10, 20, 25};
    
    vector< vector<int> > m(L, vector<int>(L));
    vector< vector<int> > s(L, vector<int>(L));
 
	cout<<"矩阵的最少计算次数为："<<matrixMultiple(6,m,s,p)<<endl;
	cout<<"矩阵最优计算次序为："<<endl;
	traceBack(1,6,s);  //输出A[1:6]的最优计算此序 
	return 0;
}

算法运行过程：

运行结果：