矩阵连乘问题《算法分析与设计》(共8页)

1、精选优质文档-倾情为你奉上设计性实验报告 课程名称：算法分析与设计实验题目：矩阵连乘问题组 长：成 员 一：成 员 二：成 员 三：系 别：数学与计算机科学系专业班级：指导教师：实验日期： 专心-专注-专业一、实验目的和要求实验目的熟悉动态规划算法设计思想和设计步骤，掌握基本的程序设计方法，培养学生用计算机解决实际问题的能力。实验要求1、根据实验内容，认真编写源程序代码、上机调试程序，书写实验报告。2、本实验项目考察学生对教材中核心知识的掌握程度和解决实际问题的能力。3、实验项目可以采用集中与分散实验相结合的方式进行，学生利用平时实验课时间和课外时间进行实验，要求在学期末形成完整的项目程序设计

2、报告。二、实验内容提要矩阵连乘问题给定n个矩阵A1,A2,An， 其中，Ai与Ai+1是可乘的，i=1,2，n-1。考查这n个矩阵的连乘积A1,A2,An。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=（BC）。三、实验步骤下面考虑矩阵连乘积的

3、最优计算次序问题的动态规划方法。（1）分析最优解的结构（最优子结构性质） 设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解结构特征。对于矩阵乘积的最优计算次序问题也不例外。首先，为方便起见，降矩阵乘积Ai Ai+1Aj简记为Ai:j。考查计算A1：n的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1<=k<n,则其相应的完全加括号方式为（A1Ak）（Ak+1An）即依此次序，先计算A1：k和 Ak+1：n，然后将计算结果相乘得到A1：n。依此计算次序，总计算量为A1：k的计算量加上Ak+1:n的计算量，再加上A1:k和Ak+1:n相乘的计算量。这个问题

4、的一个关键特征是：计算A1:n的最优次序所包含的计算矩阵子链A1:k和Ak+1:n的次序也是最优的。事实上，若有一个计算A1:k的次序需要的计算量更少，则用此次序替换原来计算A1:k的次序，得到的计算A1:n的计算量将比按最优次序计算所需计算量更少，这是一个矛盾。同理可知，计算A1:n的最优次序所包含的计算矩阵子链Ak+1:n的次序也是最优的。因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。（2）建立递归关系对于矩阵连乘积的最优计算次序问题，设计算Ai:j,1=<i=<n,所需的最少

5、数乘次数为mij,则原问题的最优值为吗m1n。当i=j时，Ai:j=Ai为单一矩阵，无需计算，因此，mii=0,i=1,2,.,n 。当i<j时，可利用最优子结构性质计算mij。事实上，若计算Ai:j的最优次序在Ak和Ak+1之间断开，i=<k<j,则mij=mik+mk+1j+pi-1*pk*pj。由于在计算时并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i种可能，即k属于i，i+1，.，j-1。因此，k是这j-i个位置中使计算量达到最小的那个位置。从而mij可以递归地定义为当i=j，mij=0;当i<j，mij=minmik+mk+1j+pi-1*pk*

6、pj,i=<k<jmij给出了最优值，即计算Ai:j所需的最少数乘次数。同时还确定了计算Ai:j的最优次序中的断开位置k，也就是说，对于这个k有mij=mik+mk+1j+pi-1*pk*pj若将对应于mij的断开位置k记为sij,在计算出最优值mij后，可递归地有sij构造出相应的最优解。（3）计算最优值根据计算mij的递归式，容易写一个递归算法计算min。.稍后将看到，简单的递归计算将耗费指数计算时间。注意到在递归计算过程中，不同的子问题个数只有（n2）个。事实上，对于1<=i<=j<=n不同的有序对（i,j）对应于不同的子问题。因此，不同的子问题的个数最多只

7、有n*(n-1)/2+n=（n2）个。由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可以动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面计算时只需简单查一下，从而避免大量重复计算，最终得到多项式时间的算法。下面给出的动态规划算法matrixChain中，输入参数p0,p1,p2.,pn存储于数组p中。算法除了输出最优值数组m外还输出记录最优断开位置的数组s。算法matrixChain，首先计算出mii=0,i=1,2,.,n。然后，根据递归式，按矩阵链长递增的方式

8、依次计算mii+1,i=1,2,.,n-1,(矩阵链长度为2)；mii+2,i=1,2,.n-2,(矩阵链长为3)；.。在计算mij时，只用到已计算出的mik和mk+1j。（4）构造最优解动态规划算法的第四步屎构造问题的最优解。算法matrixChain只是计算出了最优值，并未给出最优解。也就是说，通过算法matrixChain的计算，只知道最少数乘次数，还不知道具体应按什么次序做矩阵乘法才能达到最少的数乘次数。事实上，算法matrixChain已记录了构造最优解所需要的全部信息。Sij中的数k表明计算矩阵链Ai:j的最佳方式应在矩阵Ak和Ak+1之间断开，即最优的加括号方式应为（Ai:k）（

9、Ak+1:j）。因此，从是1n记录的信息可知计算A1:n的最优加括号方式为（A1:s1n）（As1n+1:n）.而A1：s1n的最优加括号方式为（A1:s1s1n）(As1s1n+1:s1s1n).同理可知确定As1n+1:n的最优加括号方式为是ss1n+1n出断开，······，照此递推下去，最终可以确定A1:n的最优完全加括号方式，即构造出问题的一个最优解。下面的算法traceback按算法matrixChain计算出的断点矩阵s指示的加括号方式输出计算Ai:j的最优计算次序。void traceback (int i,int j

10、,int sN+1)/用递归来实现输出得到最小数乘次数的表达式if (i=j)printf ("A%d",i);elseprintf ("("); traceback (i,sij,s); traceback(sij+1,j,s); printf (")");要输出A1:n的最优计算次序只要调用上面的traceback（1,n,s）即可。对于上面所举得例子，通过调用算法traceback（1,6，s），可输出最优计算次序(A1(A2A3)(A4A5)A6)。四、实验实施的条件计算机机房，微型计算机，Visual C+ 6.0软件或C#

11、。五、程序代码下面是算法的完整程序代码。版本：c语言版本； 开发人员：王东亮、唐浩、陶胜、赵强#include <stdio.h>#define N 100/定义最大连乘的矩阵个数为100个void matrixChain (int p,int mN+1N+1,int sN+1N+1)/*用mij二维数组来存储Ai*.Aj的最小数乘次数，用sij来存储使Ai.Aj获得最小数乘次数对应的断开位置k，需要注意的是此处的N+1非常关键，虽然只用到的行列下标只从1到N但是下标0对应的元素默认也属于该数组，所以数组的长度就应该为N+1*/int n=N;/定义m,s数组的都是n*n的，不用行

12、列下标为0的元素，但包括在该数组中for (int i=1;i<=n;i+)mii=0; /*将矩阵m的对角线位置上元素全部置0，此时应是r=1的情况，表示先计算第一层对角线上个元素的值*/for (int r=2;r<=n;r+)/r表示斜对角线的层数，从2取到nfor (int i=1;i<=n-r+1;i+)/i表示计算第r层斜对角线上第i行元素的值int j=i+r-1;/j表示当斜对角线层数为r，行下标为i时的列下标mij=mi+1j+pi-1*pi*pj;/计算当断开位置为i时对应的数乘次数sij=i;/断开位置为ifor (int k=i+1;k<j;k+

13、)int t=mik+mk+1j+pi-1*pk*pj;/*计算当断开位置k为从i到j（不包括i和j）的所有取值对应的(Ai*.*Ak)*(Ak+1*.Aj)的数乘次数*/if (t<mij)mij=t;/将Ai*.Aj的最小数乘次数存入mijsij=k;/将对应的断开位置k存入sijvoid traceback (int i,int j,int sN+1)/用递归来实现输出得到最小数乘次数的表达式if (i=j)printf ("A%d",i);elseprintf ("("); traceback (i,sij,s); traceback(si

14、j+1,j,s); printf (")");void main ()int n;/用来存储矩阵的个数int q2*N;/*用q数组来存储最原始的输入（各矩阵的行和列），主要目的是为了检验这N个矩阵是否满足连乘的条件*/int pN+1,flag=1;/*用pi-1,pi数组来存储A的阶数，flag用来判断这N个矩阵是否满足连乘*/int mN+1N+1;/ 用mij二维数组来存储Ai*.Aj的最小数乘次数int sN+1N+1;/ 用sij来存储使Ai.Aj获得最小数乘次数对应的断开位置kprintf ("请输入矩阵的个数（小于100）:");scan

15、f ("%d",&n);for (int i=0;i<=2*n-1;i+)/各矩阵的阶数的输入先存入数组q中接受检验if (i%2=0)printf ("*n");printf ("*请输入A%d的行:",(i/2)+1);elseprintf ("列*:"); scanf ("%d",&qi);for (i=1;i<=2*n-2;i+)/矩阵连乘条件的检验 if (i%2!=0&&qi!=qi+1)flag=0;break;for (int j=1;

16、j<=n-1;j+)pj=q2*j;if (flag!=0) p0=q0; pn=q2*n-1; matrixChain (p,m,s); printf ("式子如下:n"); traceback(1,n,s); printf ("n"); printf ("最小数乘次数为%dn",m1n);elseprintf ("这%d个矩阵不能连乘!n",n);实验结果：一、输入正确的情况：二、输入有误的情况：六、编程体会经过了几天的连续研究，终于小有收获，也渐渐理解了动态规划的基本思想，动态规划算法与分治法类似，其基

17、本思想也是将待解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划法求解的问题，经分解得到的子问题往往不是相互独立的。若用分治法解这类问题，则分解得到的子问题数目太多，以至于最后解决原问题需要耗费指数时间。然而，不同子问题的数目常常只有多项式量级。在分治法求解时，有些子问题被重复计算了多次。如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规

18、划的基本思想。具体的动态规划算法是多种多样的，但它们具有相同的填表格式。动态规划算法适用于解最优化问题。通常可以按以下步骤设计动态规划算法：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以自底向上的方式计算出最优值；（4）根据计算最优值时得到的信息，构造最优解。虽然已经了解了动态规划算法的基本思想，而且也参考了书上的算法，但是实际的情况却并不是那么顺利，我按照书上编写程序之后，发现有很多逻辑错误，应该是编写环境不同，所以出现了一系列的问题，最后经过自己的多番研究发现了许多c语言有许多默认的规则：就拿数组来讲，在计算数组m和数组s时，虽然我们不用到下标为零的元素，所以我一开始定义用长度为N*N的m数组和s数组来分别存储矩阵的最小数乘次数和其对应的断开位置，但经过多次调试之后，发现总是在求m*N和s*N时就会出错，后来才知道c语言的默认规则：不管我们用不用数组的零下标元素，下标为零的元素都默认在该数组中，因此，必须把m和s数组的行列长