欢迎来到天天文库
浏览记录
ID:50130506
大小:35.01 KB
页数:7页
时间:2020-03-05
《矩阵连乘实验报告.docx》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、南京信息工程大学实验(实习)报告院计算机与软件学院专业软件工程年级2013班次3姓名魏开阳学号20131344105一、实验内容矩阵连乘问题,给定n个矩阵{A1,A2,…,An},其中Ai与Ai+1是可乘的,i=1,2,3…,n-1。考察这n个矩阵的连乘A1,A2,…,An。二、主要思想由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定,也就是说该连乘积已经完全加括号,则可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为:(1)单个矩阵
2、是完全加括号的;(2)矩阵连乘积A是完全加括号的,则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号,即A=(BC)。运用动态规划法解矩阵连乘积的最优计算次序问题。按以下几个步骤进行1、分析最优解的结构设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征。为方便起见,将矩阵连乘积简记为A[i:j]。考察计算A[1:n]的最优计算次序。设这个计算次序矩阵在Ak和Ak+1之间将矩阵链断开,,则其相应的完全加括号方式为((A1…Ak)(Ak+1…An))。依此次序,先计算A[1:k]和A[k+1:n],然后将计算结果相乘得到A[1:n]。1、建立递归
3、关系设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积的最优计算次序问题,设计算A[i:j],,所需的最少数乘次数为m[i][j],原问题的最优值为m[1][n]。当i=j时,A[i:j]=Ai为单一矩阵,无需计算,因此m[i][i]=0,i=1,2,…n。当i4、行计算,在计算过程中保存已解决的子问题答案。每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法matrixChain。(见实验代码部分)3、构造最优解算法matrixChain只计算出最优值,并没有给出最优解。但是matrixChain已经记录了构造最优解所需的全部信息。S[i][j]中的数表明,计算矩阵链A[i:j]的最佳方式应在矩阵Ak和Ak+1之间断开,最优加括号方式为(A[i:k])(A[k+1:j])。依次构造最优解。(算法见实验代码部分)一、实验代码#include#defineN100v5、oidmatrixChain(intp[],intm[N+1][N+1],ints[N+1][N+1])/*用m[i][j]二维数组来存储Ai*.....Aj的最少数乘次数,用s[i][j]来存储使Ai.....Aj获得最少数乘次数对应的断开位置k,需要注意的是此处的N+1非常关键,虽然只用到的行列下标只从1到N,但是下标0对应的元素默认也属于该数组,所以数组的长度就应该为N+1*/{intn=N;for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++){for(inti=1;i<=n-r+1;i++){intj=i+r-16、;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k7、}}voidmain(){intn;intq[2*N];intp[N+1],flag=1;intm[N+1][N+1];ints[N+1][N+1];printf("输入矩阵的个数(注:小于100):");scanf("%d",&n);for(inti=0;i<=2*n-1;i++){if(i%2==0){printf("————————");printf("*输入A%d的行:",(i/2)+1);}else{printf("********列:");}scanf("%d",&q[i]);}for(i=1;i<=2*n-2;i++)//矩阵连乘条
4、行计算,在计算过程中保存已解决的子问题答案。每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法matrixChain。(见实验代码部分)3、构造最优解算法matrixChain只计算出最优值,并没有给出最优解。但是matrixChain已经记录了构造最优解所需的全部信息。S[i][j]中的数表明,计算矩阵链A[i:j]的最佳方式应在矩阵Ak和Ak+1之间断开,最优加括号方式为(A[i:k])(A[k+1:j])。依次构造最优解。(算法见实验代码部分)一、实验代码#include#defineN100v
5、oidmatrixChain(intp[],intm[N+1][N+1],ints[N+1][N+1])/*用m[i][j]二维数组来存储Ai*.....Aj的最少数乘次数,用s[i][j]来存储使Ai.....Aj获得最少数乘次数对应的断开位置k,需要注意的是此处的N+1非常关键,虽然只用到的行列下标只从1到N,但是下标0对应的元素默认也属于该数组,所以数组的长度就应该为N+1*/{intn=N;for(inti=1;i<=n;i++)m[i][i]=0;for(intr=2;r<=n;r++){for(inti=1;i<=n-r+1;i++){intj=i+r-1
6、;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];s[i][j]=i;for(intk=i+1;k7、}}voidmain(){intn;intq[2*N];intp[N+1],flag=1;intm[N+1][N+1];ints[N+1][N+1];printf("输入矩阵的个数(注:小于100):");scanf("%d",&n);for(inti=0;i<=2*n-1;i++){if(i%2==0){printf("————————");printf("*输入A%d的行:",(i/2)+1);}else{printf("********列:");}scanf("%d",&q[i]);}for(i=1;i<=2*n-2;i++)//矩阵连乘条
7、}}voidmain(){intn;intq[2*N];intp[N+1],flag=1;intm[N+1][N+1];ints[N+1][N+1];printf("输入矩阵的个数(注:小于100):");scanf("%d",&n);for(inti=0;i<=2*n-1;i++){if(i%2==0){printf("————————");printf("*输入A%d的行:",(i/2)+1);}else{printf("********列:");}scanf("%d",&q[i]);}for(i=1;i<=2*n-2;i++)//矩阵连乘条
此文档下载收益归作者所有