2023年矩阵连乘实验报告

华北电力大学科技学院实验报告实验名称矩阵连乘问题课程名称计算机算法设计与分析专业班级:。软件12K188。学生姓名:吴旭学号：，成绩：指导老师：。刘老师实验日期：指导老师：。刘老师实验日期：2023.11.14环节。完毕实验后，我认为建立递归关系是很关键的一步，同时也是整个动态规划算法的精髓。掌握了递归的思想，就可以完毕很多不必要的反复计算。具体到矩阵连乘问题，关键是解决断开点k的位置和最少数乘次数。总体来说,这次实验不仅让我基本掌握递归的思想，并且进一步提高了自己的自学能力和编程能力，代码运用C语言写出，可以很好的体会C语言和C++的不同点和相同点。我也体会到,想要理解一个新的算法，必须要通过自己不断的编写程序，不断的思考才干真正的领悟,因此我会不断朝着这个方向努力。一、实验内容矩阵连乘问题，给定〃个矩阵{AiA,...,An},其中Ai与Ai+I是可乘的，i=l,2,3...,n・l。考察这〃个矩阵的连乘Ai,A2,…，二、重要思想由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算顺序。这种计算顺序可以用加括号的方式来拟定。若一个矩阵连乘积的计算顺序完全拟定，也就是说该连乘积已经完全加括号，则可依此顺序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归的定义为：(1)单个矩阵是完全加括号的；(2)矩阵连乘积A是完全加括号的，则A可表达为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)。运用动态规划法解矩阵连乘积的最优计算顺序问题。按以下几个环节进行分析最优解的结构设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特性。为方便起见，将矩阵连乘积简记为A[i:j]。考察计算A[1:n]的最优计算顺序。设这个计算顺序矩阵在Ak和Ak+i之间将矩阵链断开，l〈kWn,则其相应的完全加括号方式为((Ai…Ak)(Ak+i...An))o依此顺序,先计算A[l:k]和A[k+1:n],然后将计算结果相乘得到A[l:n]0建立递归关系设计动态规划算法的第二步是递归定义最优值。对于矩阵连乘积的最优计算顺序问题，设计算A[i:j],iWiMjMn,所需的最少数乘次数为mEi][j],原问题的最优值为当i=j时，A[i:j]=Ai为单一矩阵，无需计算，因此m[i][i]=0,i=l,2,...no当ivj时，可运用最优子结构性质来计算mm[i][j]=m[i][k]+m[k+l][j]+pi-ipkPjo由于在计算时并不知道断开点k的位置，所以k尚未定。计算最优值根据计算m[i][j]的递归式，容易写一个递归算法计算m[l][n]o动态规划法解决此问题，可依据递归式以自底向上的方式进行计算,在计算过程中保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简朴查一下，从而避免大量的反复计算，最终得到多项式时间的算法matrixChain。(见实验代码部分)构造最优解算法matrixChain只计算出最优值，并没有给出最优解。但是matrixChain已经记录了构造最优解所需的所有信息。S[i][j]中的数表白，计算矩阵链A[i:j]的最佳方式应在矩阵Ak和Ak+i之间断开，最优加括号方式为(A[i:k])(A[k+l:j])o依次构造最优解。(算法见实验代码部分）三、实验结果输入矩阵的个数＜注：小于100〉：4”输入A1的件35嘛入A2的彳彳：15端入A3的牛5XXMWX*歹|J：10卜输入A4的件10*-M*M**-M*^||：20其子如下：<<Alfi2XA3A4>>最少技乘次数为7125Pressanykeytocontinue四、结果验证对实验结果进行验证,4个矩阵分别是Ai[35*l5],A2[15*5],A3[5*10],A4[10*20]。依递归式有：0+2500+35x15x20=M[l][4]=min+1000+35x5x20=7125.4375+0+35x10x20=11375=7125且k=3o计算结果对的，证明所编写的程序可对的算出最优解。五、实验代码#include<stdio.h>#dcfincN100//定义最大连乘的矩阵个数是100voidmatrixChain(intp[],intm[N+1][N+1],ints[N+1][N+1])/*用二维数组来存储Ai*.....Aj的最少数乘次数，用来存储使Ai.....Aj获得最少数乘次数相应的断开位置k,需要注意的是此处的N+1非常关键，虽然只用到的行列下标只从1到N,但是下标。相应的元素默认也属于该数组，所以数组的长度就应当为N+1*/(Antn=N;//定义m,s数组的都是n*n的.不用行列下标为()的元素，但涉及在该数组中for(inti=1；iV=n;i++)m/*将矩阵m的对角线位置上元素所有置0,此时应是r=1的情况，表达先计算第一层对角线上个元素的值切for(intr=2;r<=n；r++)//r表达斜对角线的层数，从2取到n(gfor(inti=l;i<=n-r+1;i++)//i表达计算第r层斜对角线上第i行元素的值00|-intj=i+r-l;//j表达当斜对角线层数为r,行下标为i时的列下标am[i][j]=m[i+1]|j]+p[i-1]*p[i]*pU]；〃计算当断开位置为i时相应的数乘次数°s[i][j]=i；//断开位置为i。for(intk=i+l;k<j;k++)00(。“intt=m[i][kj+m[k+1J[jj+p[k；/*计算断开位置k为从i至Ijj(不涉及i和j)的所有取值相应的。。(Ai*.....*Ak)*(Ak+1*.....Aj)的数乘次数*/:t；//将Ai*....Aj的最少数乘次数存入m[i][将s[i][j]=k;//将相应的断开位置k存入s[i][j]00000。}000}。}}voidtraceback(inti,intj,ints[][N+l])//用递归来实现输出得到最小数乘次数的表达式(if(i==j){。叩rintf(“A%d"，i)；oeIse。printf("(");traceback(i,s[i][j],s);®»traceback(s[i][j]+l,j,s);printf(H)");))voidmain()(intn;//用来存储矩阵的个数Mntq[2*N];/*用q数组来存储最原始的输入(各矩阵的行和列)，重要目的是为了检查这N个矩阵是否满足连乘的条件*/intp[N+l],flag=14用p[i-1],p[i]数组来存储A的阶数,flag用来判断这N个矩阵是否满足连乘*/intm[N+l][N+1];//用m[i][j]二维数组来存储Ai*……Aj的最小数乘次数ints[N+l][N+l];//用s来存储使AiAj获得最小数乘次数相应的断开位置kOprinlf("输入矩阵的个数(注：小于100):“);scant("％d”,&n);for(inti=0;i<=2*n—I;i++)//各矩阵的阶数的输入先存入数组q中接受检查ooif(i%2==0)00|oprintf("\nM);。printf("*输入A%d的行:”,(i/2)+1);00|。空Ise°{。oprintf(”********列:”)；}oscanf(H%d';&q[i])；}for(i=1;i<=2*n—2；i++)//矩阵连乘条件的检查。if(i%2!=0&&q[i]!=q[i+1])00|flag=0;。break；0)0)®fbr(intj=l;j<=n-1;j++)if(flag!=O)P[0]=q[()];。叩[n]=qf2*n-l];matrixCha