[矩阵连乘问题(动态规划)]矩阵连乘问题求解
时间：2020-08-06 13:08:45 来源：天一资源网 本文已影响 人 
矩阵连乘问题（动态规划）
实验目的与要求
1、明确矩阵连乘的概念。
2、利用动态规划解决矩阵连乘问题。
二、实验题：
问题描述：
给定n个矩阵｛A1,A2,...,An｝，其中Ai与Ai+1是可乘的，i=1，2...，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。
三、实验代码
#include<iostream>
using namespace std;
const int MAX = 100;
//p用来记录矩阵的行列，main函数中有说明
//m[i][j]用来记录第i个矩阵至第j个矩阵的最优解
//s[][]用来记录从哪里断开的才可得到该最优解
int p[MAX+1],m[MAX][MAX],s[MAX][MAX];
int n;//矩阵个数
int matrixChain(){
for(int i=0;i<=n;i++)
m[i][i]=0;
for(int r=2;r<=n;r++)//对角线循环
for(int i=0;i<=n-r;i++){//行循环
int j = r+i-1;//列的控制
//找m[i][j]的最小值，先初始化一下，令k=i
m[i][j]=m[i+1][j]+p[i+1]*p[i]*p[j +1];
s[i][j]=i;
//k从i+1到j-1循环找m[i][j]的最小值
for(int k = i+1;k<j;k++){
int temp=m[i][k]+m[k+1][j]+p[i]*p[k+1]*p[j+1];
if(temp<m[i][j]){
m[i][j]=temp;
//s[][]用来记录在子序列i-j段中，在k位置处
//断开能得到最优解
s[i][j]=k;
}
}
}
return m[0][n-1];//最终结果
}
//根据s[][]记录的各个子段的最优解，将其输出
void traceback(int i,int j){
if(i==j){
cout<<'A'<<i;
return ;
}
if(i<s[i][j])
cout<<'(';
traceback(i,s[i][j]);
if(i<s[i][j])
cout<<')';
if(s[i][j]+1<j)
cout<<'(';
traceback(s[i][j]+1,j);
if(s[i][j]+1<j)
cout<<')';
}
void traceback(){
cout<<'(';
traceback(0,n-1);
cout<<')';
cout<<endl;
}
int main(){
cout<<"请输入矩阵的个数："<<endl;
cin>>n;
cout<<"输入矩阵（形如a*b,中间用空格隔开）:"<<endl;
for(int i=0;i<=n;i++)
cin>>p[i];
//测试数据可以设为六个矩阵分别为
//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}
cout<<"输出结果如下："<<endl;
matrixChain();
traceback(0,n-1);
//最终解值为m[0][n-1];
cout<<endl;
return 0;
}
?四、实验结果
相关关键词： 矩阵乘法 二阶逆矩阵简便算法 一个数乘以一个矩阵 矩阵 matlab解矩阵方程
