实训二
矩阵连乘问题的动态规划算法与实现
任务分配 编 码 测 试 陈健翔 朱敏 成绩 成绩 综合分数 一、 设计目的
1） 掌握动态规划算法思想；
2） 掌握矩阵相乘问题的动态规划,得到矩阵相乘问题的最优解； 3） 进一步掌握动态规划法的基本思想和算法设计方法；
二、 设计内容
1． 任务描述
给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1,2 ,…,n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。
A1 30?35 A2 35?15 A3 15?5 A4 5?10 A5 10?20 A6 20?25
2． 主要数据类型与变量
int p[MAX+1]//如任务描述记录30,35,15,5,10,20,25 m[MAX][MAX]//记录存储相乘次数的
s[MAX][MAX]; //记录从哪里断开的才可得到该最优解 int matrixCount;//矩阵个数
3． 算法或程序模块
void matrixChain(int p[21],int n,int m[20][20],int s[20][20]) 功能: 得到矩阵相乘问题的最优解
void Trackback(int i,int j,int s[20][20])
功能: 按算法MatrixChain 计算出的断点矩阵s指示的加括号方式输出计算A[i:j] 的最优计算次序。
三、 测试
找不到好的数据,呼呼就拿书上的例子测试吧！我把二维数组m也输出了看了一下,应该是可以的。检查下断开的点,也是正解。
测试多组数据：
四、 总结与讨论
对于这个实训二，主要是为了得到矩阵相乘的最少次数。
所以我们引进了一个k值，把一个矩阵链分解成多个矩阵链，可以分成长度为2或者长度为3的矩阵链，当然分开后还要
+（第一个矩阵的行数*Ak矩阵的行或列*最后一个矩阵的列）
J=1 j=2 ........... j=n
上图其实很清楚的可以看出程序的流程。
因为对角线上i=j 所以值为0 当j-i=1 为长度为2的矩阵链, 就一个解
另外有多个解的时候 k从i+1到j-1循环找m[i][j]的最小值，查找的同时替换掉大的数 最后使用Tranceback根据s[][]记录的各个子段的最优解，将其输出。
其最优解为：m[1][matrixCount]
附：程序模块的源代码
#include
int p[MAX+1],m[MAX][MAX],s[MAX][MAX]; int matrixCount;//矩阵个数
void matrixChain(int p[21],int n,int m[20][20],int s[20][20]) {
for(int i=1;i<=n;i++)m[i][i]=0;
//填充对角线的所有数据,因为i=j,所以只有1个矩阵所以计算0次 for(int r=2;r<=n;r++)
for(int i=1;i<=n-r+1;i++) {
int j = r+i-1;//列始终比行大(r-1),j=2,3...,matrixCount-1 m[i][j]=m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i;
for(int k = i+1;k int temp=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j]; if(temp { m[i][j]=temp; s[i][j]=k; } } } } void Trackback(int i,int j,int s[20][20]) { if(i==j)return; Trackback(i,s[i][j],s); Trackback(s[i][j]+1,j,s); printf(\} int main() { printf(\ scanf(\ printf(\ printf(\ printf(\ for(int i=0;i<=matrixCount;i++) scanf(\ matrixChain(p,matrixCount,m,s); Trackback(1,matrixCount,s); for(int i=0;i< matrixCount;i++) { for(int j=matrixCount;j>0;j--) { printf(\ } printf(\ } printf(\ system(\ return 0; }