最优矩阵连乘问题

问题描述

题意

给定n个矩阵 {A1，A2，……，An},其中Ai与Ai+1是可乘的，i = 1，2，……，n-1。
如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。

给定三个矩阵A1,A2,A3,维数分别为 10*100 , 100*5 , 5*50
根据题意，可以有下列连乘情况：

1. 按(A1A2)A3的结合顺序进行连乘
   

   乘的次数为10*100*5 + 10*5*50 = 7500 次

2. 按A1(A2A3)的结合顺序进行连乘
   

   乘的次数为100*5*50 + 10*100*50 = 75000 次

由此可见，矩阵连乘时，矩阵之间的结合方式对结果会产生很大影响。

分析

题意要求确定计算矩阵连乘A1，A2， …，An的一个计算次序，即矩阵连乘的最优计算次序问题。如果用分治法来求，矩阵在连乘过程中，子问题会产生重叠，无法将问题划分为互不相交的子问题，不适用分治法。因此，为了避免自顶向下的递归过程，此处采取自底向上的动态规划方法。

源代码

#include <iostream>
#include <stdio.h>
#include <string>

#define forl(i,l,r) for(int i=l;i<r;++i)
#define fore(i,l,r) for(int i=l;i<=r;++i)

//最多有1e3个矩阵相乘
const int maxn = 1e3,inf = 0x3f3f3f3f;
static int n;
static int p[maxn][maxn],m[maxn][maxn]; //p记录分割点,m记录相乘次数

struct Matrix
{
    int r,c;
}mat[maxn];

void Matrix_chain(){
    forl(k,1,n){  //间隔距离
        forl(i,0,n-k){  //操作起始列
            forl(j,i,i+k){
                //状态转移方程
                int temp = m[i][j] + m[j+1][i+k] + mat[i].c*mat[j].r*mat[i+k].r;
                if(temp < m[i][i+k]){    //如果有更少的连乘次数，更新
                    p[i][i+k] = j;  //更新分割点
                    m[i][i+k] = temp;   //记录最少乘法次数
                }
            }
        }
    }
}
//根据分割点，输出最小乘法次数的矩阵连乘方案
std::string Matrix_chain_print(int l,int r){
    if(l == r) return std::string(1,'A'+l);
    else{
        int split = p[l][r];
        return "("+Matrix_chain_print(l,split)+"*"+Matrix_chain_print(split+1,r)+")";
    }
}

void Matrix_print(){
    forl(i,0,n){
        forl(j,0,n) printf("%10d",m[i][j]);
        printf("\n");
    }
}

int main()
{
    while(~scanf("%d",&n)){
        forl(i,0,n) scanf("%d %d",&mat[i].r,&mat[i].c);
        forl(i,0,n){
            forl(j,0,n){
                p[i][j] = -1;
                if(i == j) m[i][i] = 0; //矩阵本身乘数为0
                else m[i][j] = inf; //初始化为最大值
            }
        }
        Matrix_chain();
        //用C++的string类保存递归过程，输出矩阵连乘的形式
        std::cout << Matrix_chain_print(0,n-1);
        printf("\n最少连乘次数为：%d\n",m[0][n-1]);
        Matrix_print();
    }
    return 0;
}