动态规划+递归+备忘录 解决矩阵连乘
问题描述：
给定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;
}
运行截图
