内容纲要
最优矩阵连乘问题
问题描述
题意
给定n个矩阵 {A1,A2,……,An},其中Ai与Ai+1是可乘的,i = 1,2,……,n-1。
如何确定计算矩阵连乘积的计算次序,使得依此次序计算矩阵连乘积需要的数乘次数最少。
给定三个矩阵A1,A2,A3,维数分别为 10*100 , 100*5 , 5*50
根据题意,可以有下列连乘情况:
- 按(A1A2)A3的结合顺序进行连乘
乘的次数为10*100*5 + 10*5*50 = 7500 次
- 按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;
}