矩阵连乘备忘录算法.doc

湖南涉外经济学院 计算机科学与技术专业
《算法设计与分析》课程

矩阵连乘备忘录算法

实 验 报 告

班级：
学号：
姓名：
教师：
成绩：

2012年5月

【实验目的】
1 掌握动态规划算法和备忘录方法；
2 利用动态规划备忘录思想实现矩阵连乘；
3 分析实验结果，总结算法的时间和空间复杂度。思考是否能将算法的时间复杂度提高到O(nlgn)
【系统环境】
Windows 07 平台
【实验工具】
VC++6.0中文企业版
【问题描述】
描述： 给定n个矩阵{A1，A2，…，An}，其中Ai与Ai+1可乘的，i=1,2，…，n-1。找出这个n个矩阵的连乘A1A2…An所需相乘的最少次数的方式。
例：矩阵连乘积A1A2A3A4可以有一下五种不同的完全加括号方式：
（A1（A2（A3A4）））
（A1（（A2A3）A4））
（（A1A2）（A3A4））
（（A1（A2A3））A4）
（（（A1A2）A3）A4）
【实验原理】
原理：1、矩阵连乘满足结合律，且不同的结合方式，所需计算的次数不同。
2、利用备忘录方法，用表格保存以解决的子问题答案，降低重复计算，提高效率。
思路：m初始化为0，表示相应的子问题还位被计算。在调用LookupChain时，若m[i][j]>0，则表示其中储存的是所要求子问题的计算结果，直接返回此结果即刻。否则与直接递归算法一样，自顶而下的递归计算，并将计算结果存入m[i][j]后返回。因此，LookupChain总能返回正确的值，但仅在它第一次被调用时计算，以后调用就直接返回计算结果。
方法：用MemorizedMatrixChain函数将已经计算的数据存入表中，用LookupChain函数配合MemorizedMatrixChain函数递归调用计算。

【源程序代码】
#include<stdio.h>
#include<stdlib.h>
#include<ctime>
#define N 10
int p[N],m[N][N],s[N][N];
int LookupChain(int i,int j);
//备忘录算法函数
int MemorizedMatrixChain(int n,int **m,int **s)
{
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
m[i][j]=0;
return LookupChain(1,n);
}
//递归调用函数
int LookupChain(int i,int j)
{
if(m[i][j]>0)
return m[i][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;
}
}
m[i][j]=u;
return u;

}
//输出格式函数
void Print(int s[][N],int i,int j)
{
if(i==j)
{
printf("A");
printf("%d",i);
}
else
{
printf("(");
Print(s,i,s[i][j]);
Print(s,s[i][j]+1,j);
printf(")");
}
}
//主函数
int main()
{
srand(time(NULL));
for(int i=0;i<N;i++)
p[i]=rand()%100;//随机生成；
for(i=0;i<N;i++)
printf("%4d",p[i]);
printf("\n");
int result=LookupChain(1,N-1);
printf("最少次数：\n");
printf("%d\n\n\n",result);
printf("最优次序：\n");
Print(s,1,N-1);
printf("\n");
return 0;
}

【实验结果】
运行结果图

【时间复杂度】
备忘录算法MemorizedMatrixChain耗时O（n^3）。