还剩4页未读,继续阅读
文本内容:
实验报实验名称矩阵连乘问题_____________课程名称计算机算法设计与分析专业班级学生姓名:学号成绩指导老师:实验日期:
一、实验内容矩阵连乘问题,给定n个矩阵{Al,A2,…,An},其中Ai与Ai+1是可乘的,i=l,2,3-,n-lo考察这n个矩阵的连乘Al,A2,…,An
二、实验基本思想由于矩阵乘法满足结合律,故计算矩阵的连乘积可以有许多不同的计算次序设计求解矩阵连乘问题的动态规划算法的第1步是刻画该问题的最优解的结构特征为方便起见,将矩阵连乘积简记为A[i:j]o考察计算A[l:n]的最优计算次序设这个计算次序矩阵在Ak和Ak+i之间将矩阵链断开,,则其相应的完全加括号方式为((A「・Ak)(Ag…AO)依此次序,先计算A[l:k]和A[k+l:n],然后将计算结果相乘得到
三、算法设计
1、分析最优解的结构设计求解具体问题的动态规划算法的第1步是刻画该问题的最优解的结构特征为方便起见,将矩阵连乘积简记为A[i:j]o考察计算A[1:n]的最优计算次序设这个计算次序矩阵在Ak和Ak”之间将矩阵链断开,,则其相应的完全加括号方式为((A…Ak)(Ag…A)依此次序,先计算A[1:k]和A[k+1:n],然后将计算结果相乘得到A[l:n]o
2、建立递归关系设计动态规划算法的第二步是递归定义最优值对于矩阵连乘积的最优计算次序问题,设计算,所需的最少数乘次数为m[i][j],原问题的最优值为当i=j时,A[i:j]=Ai为单一矩阵,无需计算,因此i=l,2,-no当ij时,可利用最优子结构性质来计算m[i][j]o m[i][k]+m[k+l][j]+pi-iPkPjo由于在计算时并不知道断开点k的位置,所以k还未定
3、计算最优值根据计算的递归式,容易写一个递归算法计算动态规划法解决此问题,可依据递归式以自底向上的方式进行计算,在计算过程中保存已解决的子问题答案每个子问题只计算一次,而在后面需要时只要简单查一下,从而避免大量的重复计算,最终得到多项式时间的算法matrixChain如下void matrixChain{forint i=l;i=n;i++m[i][i]=0;for intr=2;r=n;r++//r表示矩阵连乘中的矩阵个数forint i=l;i=n-r+l;i++{int j=r+iT;〃列的控制//找的最小值,先初始化一下,令k=i m[i][j]=m[i][i]+m[i+l][j]+p[i-l]*p[i]*p[j];s[i]//k从i+1到j-1循环找m[i][j]的最小值forint k=i+1;kj;k++{int t=m[i][k]+m[k+l][j]+p[i-l]*p[k]*p[j];iftm[i][j]{m[i][j]=t;//s□□用来记录在子序列i-j段中,在k位置处〃断开能得到最优解s[i][j]=k;
4、构造最优解算法matrixChain只计算出最优值,并没有给出最优解但是matrixChain已经记录了构造最优解所需的全部信息中的数表明,计算矩阵链的最佳方式应在矩阵AMD Ag之间断开,最优加括号方式为A[i:k]A[k+l:j]依次构造最优解算法设计void Tracebackinti,int j{if i=j return;Tracebacki,s[i][j];Tracebacks[i]j;cout«zr MultiplyA,/«i«z,,z«s[i][j]«z,andA z,«s[i][j]+l«/z,,z«j«encll;}
四、实验结果■C:\Users\yxy\Documents\Visual Studio2010\Projects\制去实验董阵…3035155102025Multiply A2,2and A3,3Multiply Al,land A2,3Multiply A4,4and A5,5Multiply A4,5and A6,6Multiply Al,3and A4,615125请按任意键继续..
五、实验代码#includeiostream usingnamespace std;const intMAX=100;//p用来记录矩阵的行列,main函数中有说明〃加i][j]用来记录第i个矩阵至第J个矩阵的最优解//s□□用来记录从哪里断开的才可得到该最优解int p[MAX+l],m[MAX][MAX],s[MAX][MAX];int n;〃矩阵个数void matrixChainOforint i=l;i=n;i++m[i][i]=0;for intr=2;r=n;r++〃r表示矩阵连乘中的矩阵个数forint i=l;i〈=n-r+l;i++{int j=r+iT;〃列的控制//找的最小值,先初始化一下,令k=i m[i][j]=m[i][i]+m[i+l][j]+p[i-l]*p[i]*p[j];s[i]//k从i+1到j-1循环找m[i][j]的最小值forint k=i+1;kj;k++{int t=m[i][k]+m[k+l][j]+p[i-l]*p[k]*p[j];iftm[i][j]{m[i]//s□□用来记录在子序列i-j段中,在k位置处〃断开能得到最优解s[i][j]=k;}〃根据s[]□记录的各个子段的最优解,将其输出void Tracebackinti,int j{ifi==j return;Tracebacki,s[i][j];Traceback s[i]j;cout,,Multiply A,,i//,[j]/z and,z A«s[i]+«j«endl;void main{cinn;for inti=0;i=n;i++cin»p[i];〃测试数据可以设为六个矩阵分别为//A1[30*35],A2[35*15],A3[15*5],A4[5*10],A5[10*20],A6[20*25]〃则P[0-6]={30,35,15,5,10,20,25〃输入63035155102025matrixChain;Traceback1,n;〃最终解值为m[l][n];coutm[l][n]«endl;systempause;
六、实验心得通过本次实验,我较为透彻的理解了动态规划算法的几个基本步骤完成实验后,我认为建立递归关系是很关键的一步,同时也是整个动态规划算法的精髓掌握了递归的思想,就可以完成很多不必要的重复计算具体到矩阵连乘问题,关键是解决断开点k的位置和最少数乘次数总体来说,这次实验不仅让我基本掌握递归的思想,而且进一步提高了自己的自学能力和编程能力想要理解一个新的算法,必须要通过自己不断的编写程序,不断的思考才能真正的领悟,因此在以后的生活中,我会更加努力,时刻学习,不断朝着这个方向前进。