矩阵连乘问题《算法分析与设计》

设计性实验报告课程名称：《算法分析与设计》实验题目：矩阵连乘问题组长：成员一：成员二：成员三：系别：数学与计算机科学系专业班级：指导教师：实验日期：1-一、实验目的和要求实验目的熟悉动态规划算法设计思想和设计步骤，掌握基本的程序设计方法，培养学生用计算机解决实际问题的能力。实验要求1、根据实验内容，认真编写源程序代码、上机调试程序，书写实验报告。2、本实验项目考察学生对教材中核心知识的掌握程度和解决实际问题的能力。3、实验项目可以采用集中与分散实验相结合的方式进行，学生利用平时实验课时间和课外时间进行实验，要求在学期末形成完整的项目程序设计报告。二、实验内容提要矩阵连乘问题给定n个矩阵{A1,A2,…,An}，其中，Ai与Ai+1是可乘的，i=1,2，…，n-1。考查这n个矩阵的连乘积A1（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）。三、实验步骤下面考虑矩阵连乘积的最优计算次序问题的动态规划方法。（1）分析最优解的结构（最优子结构性质）设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解结构特征。对于矩阵乘积的最优计算次序问题也不例外。首先，为方便起见，降矩阵乘积AiAi+1…Aj简记为A[i:j]。考查计算A[1：n]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1<=k<n,则其相应的完全加括号方式为（（A1…Ak）（Ak+1…An））即依此次序，先计算A[1：k]和A[k+1：n]，然后将计算结果相乘得到A[1：n]。依此计算次序，总计算量为A[1：k]的计算量加上A[k+1:n]的计算量，再加上A[1:k]和A[k+1:n]相乘的计算量。这个问题的一个关键特征是：计算A[1:n]的最优次序所包含的计算矩阵子链A[1:k]和A[k+1:n]的次序也是最优的。事实上，若有一个计算A[1:k]的次序需要的计算量更少，则用此次序替换原来计算A[1:k]的次序，得到的计算A[1:n]的计算量将比按最优次序计算所需计算量更少，这是一个矛盾。同理可知，计算A[1:n]的最优次序所包含的计算矩阵子链A[k+1:n]的次序也是最优的。因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。（2）建立递归关系 for(inti=1;i<=n-r+1;i++)//i表示计算第r层斜对角线上第i行元素的值 { intj=i+r-1;//j表示当斜对角线层数为r，行下标为i时的列下标 m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//计算当断开位置为i时对应的数乘次数 s[i][j]=i;//断开位置为i for(intk=i+1;k<j;k++) { intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];/*计算当断开位置k为从i到j（不包括i和j）的所有取值对应的(Ai**Ak)*(Ak+1*Aj)的数乘次数*/ if(t<m[i][j]) { m[i][j]=t;//将Ai*Aj的最小数乘次数存入m[i][j] s[i][j]=k;//将对应的断开位置k存入s[i][j] } } } }}voidtraceback(inti,intj,ints[][N+1])//用递归来实现输出得到最小数乘次数的表达式{ if(i==j) { printf("A%d",i); } else { printf("("); traceback(i,s[i][j],s); traceback(s[i][j]+1,j,s); printf(")"); }}voidmain(){ intn;//用来存储矩阵的个数 intq[2*N];/*用q数组来存储最原始的输入（各矩阵的行和列），主要目的是为了检验这N个矩阵是否满足连乘的条件*/ intp[N+1],flag=1;/*用p[i-1],p[i]数组来存储A的阶数，flag用来判断这N个矩阵是否满足连乘*/ intm[N+1][N+1];//用m[i][j]二维数组来存储Ai*Aj的最小数乘次数 ints[N+1][N+1];//用s[i][j]来存储使AiAj获得最小数乘次数对应的断开位置k printf("请输入矩阵的个数（小于100）:"); scanf("%d",&n); for(inti=0;i<=2*n-1;i++)//各矩阵的阶数的输入先存入数组q中接受检验 { if(i%2==0) { printf("********************\n"); printf("*请输入A%d的行:",(i/2)+1); } else { printf("列************:"); } scanf("%d",&q[i]); } for(i=1;i<=2*n-2;i++)//矩阵连乘条件的检验 {if(i%2!=0&&q[i]!=q[i+1]) { flag=0; break; } } for(intj=1;j<=n-1;j++) { p[j]=q[2*j]; } if(flag!=0) { p[0]=q[0]; p[n]=q[2*n-1]; matrixChain(p,m,s); printf("式子如下:\n"); traceback(1,n,s); printf("\n"); printf("最小数乘次数为%d\n",m[1][n]); } else { printf("这%d个矩阵不能连乘!\n",n); } }实验结果：一、输入正确的情况：二、输入有误的情况：六、编程体会经过了几天的连续研究，终于小有收获，也渐渐理解了动态规划的基本思想，动态规划算法与分治法类似，其基本思想也是将待解问题分解成若干个子问题，先求解子问题，，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指数时间。然而，不同子问题的数目常常只有多项式量级。在分治法求解时，有些子问题被重复计算了多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划的基本思想。具体的动态规划算法是多种多样的，但它们具有相同的填表格式。动态规划算法适用于解最优化问题。通常可以按以下步骤设计动态规划算法：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造最优解。虽然已经了解了动态规划算法的基本思想，而且也参考了书上的算法，但是实际的情况却并不是那么顺利，我按照书上编写程序之后，发现有很多逻辑错误，应该是编写环境不同，所以出现了一系列的问题，最后经过自己的多番研究发现了许多c语言有许多默认的规则：就拿数组来讲，在计算数组m和数组s时，虽然我们不用到下标为零的元素，所以我一开始定义用长度为N*N的m数组和s数组来分别存储矩阵的最小数乘次数和其对应的断开位置，但经过多次调试之后，发现总是在求m[*][N]和s[*][N]时就会出错，后来才知道c语言的默认规则：不管我们用不用数组的零下标元素，下标为零的元素都默认在该数组中，因此，必须把m和s数组的行列长度都必须加一才行，经过这次程序设计之后，我懂得了一个道理，做程序设计，不仅要弄透解决这个问题的基本思想和算法，而且要注意编程过程中的一些细节性问题，例如一些特定编程环境的默认规则，而且还要要求我的逻辑思路一定要清晰，不