问题描述
给定n个矩阵{A1A2…An}，其中Ai和Ai+1是可乘的，考察这n个矩阵的连乘积A1A2…An。由于矩阵的乘法满足结合律，故计算矩阵的连乘积有许多不同的计算次序，而不同的计算次序，所需要计算的连乘次数也是不同的，求解连乘次数最少的矩阵连乘最优次序。 **
递归实现：
#include "stdafx.h"
int p
[100],s
[100][100],n
;
int LookupChain(int i
, int j
,)
{
if (i
== j
) return 0;
int u
= LookupChain(i
,i
) + LookupChain(i
+1,j
) + p
[i
-1]*p
[i
]*p
[j
];
s
[i
][j
] = i
;
for (int k
= i
+1; k
< j
; k
++) {
int t
= LookupChain(i
,k
) + LookupChain(k
+1,j
) + p
[i
-1]*p
[k
]*p
[j
];
if (t
< u
) { u
= t
; s
[i
][j
] = k
;}
}
return u
;
}
void Traceback(int i
, int j
, int s
[100][100]){
if(i
==j
) return;
Traceback(i
, s
[i
][j
], s
);
Traceback(s
[i
][j
]+1, j
, s
);
printf("Multiply A%d,%d",i
,s
[i
][j
]);
printf("and A%d,%d\n",s
[i
][j
]+1,j
);
}
int main(){
printf("请输入矩阵个数：\n");
scanf("%d",&n
);
printf("请输入矩阵各维数值：\n");
for(int i
=0;i
<n
+1;i
++){
scanf("%d",&p
[i
]);
}
printf("最优值为:%d\n",LookupChain(1,n
));
printf("最优解为:\n");
Traceback(1,n
,s
);
printf("\n");
return 0;
}
动态规划实现：
#include "stdafx.h"
void matrixChain(int* p
, int n
,int m
[100][100],int s
[100][100]) {
for (int i
= 1; i
<= n
; i
++) {
m
[i
][i
]=0;
}
for (int r
= 2; r
<= n
; r
++) {
for (int i
= 1; i
<= n
-r
+1; i
++){
int j
=i
+r
-1;
m
[i
][j
]=m
[i
+1][j
]+p
[i
-1]*p
[i
]*p
[j
];
s
[i
][j
]=i
;
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
;
s
[i
][j
] = k
;
}
}
}
}
}
void Traceback(int i
, int j
, int s
[100][100]){
if(i
==j
) return;
Traceback(i
, s
[i
][j
], s
);
Traceback(s
[i
][j
]+1, j
, s
);
printf("Multiply A%d,%d",i
,s
[i
][j
]);
printf("and A%d,%d\n",s
[i
][j
]+1,j
);
}
int main(int argc
, char* argv
[])
{
int p
[100],m
[100][100],s
[100][100];
int n
;
printf("请输入矩阵个数：\n");
scanf("%d",&n
);
printf("请输入矩阵各维数值：\n");
for(int i
=0;i
<n
+1;i
++){
scanf("%d",&p
[i
]);
}
matrixChain(p
,n
+1,m
,s
);
printf("最优值为:%d\n",m
[1][n
]);
printf("最优解为:\n");
Traceback(1,n
,s
);
return 0;
}
测试
测试递归程序： 测试过程：输入矩阵个数3，然后输入矩阵的行和列之后回车，系统输出最优值和最优解。
测试动态规划程序： 测试过程：输入矩阵个数5，然后输入矩阵的行和列之后回车，系统输出最优值和最优解。
讨论
根据计算m[ i ][ j ]的递归式，容易写一个递归算法计算m[1][n]。但是简单地递归将耗费指数计算时间。在递归计算时，许多子问题被重复计算多次。这也是该问题可以用动态规划算法求解的又一显著特征。 用动态规划算法解决此问题，可依据其递归是以自底向上的方式进行计算。在计算的过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算。
