矩阵连乘问题算法分析与设计.doc

《矩阵连乘问题算法分析与设计.doc》由会员分享，可在线阅读，更多相关《矩阵连乘问题算法分析与设计.doc（9页珍藏版）》请在三一文库上搜索。

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

2、,A，其中，A1与A1十1是可乘的，i=l,2, n-lo考查这n 个矩阵的连乘积AbA2,.,Ano由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许 多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计 算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵 相乘的标准算法计算出矩阵连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积 B和C的乘积并加括号，即人=（BC） o三、实验步骤卜面考虑矩阵连乘积的最优计算次序问题的动态规划方法。（1）分析最

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

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

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

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

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

8、首先计算出mi i二0, i二1, 2,. . . . , n。然后，根据递归式,按矩阵链长递 增的方式依次计算mi i+1, i=l, 2,. , n-1,(矩阵链长度为2)；mii+2,i=l, 2,. n-2,(矩阵链长为3);。在计算mi j时，只用到已计算出的mi k和 mk+l j o(4) 构造最优解动态规划算法的第四步屎构造问题的最优解。算法niatrixCham只是计算出了最优值，并未给出 最优解。也就是说，通过算法niatrixCham的计算，只知道最少数乘次数，还不知道具体应按什么次 序做矩阵乘法才能达到最少的数乘次数。事实上，算法matrixCham已记录了构造最优解所

9、需要的全部信息。Si|j中的数k表明计算矩 阵链Ai:j的最佳方式应在矩阵Ak和Ak+1之间断开，即最优的加括号方式应为(Ai:k)( Ak+l:j)。 因此从是ln记录的信息可知计算Al:n的最优加括号方式为(Al:sln) (Asln+l:n). 而 Al： sln的最优加括号方式为(Al:slslnJ) (Aslsln+l:slsln).同理可知确定Asln+l:n的最优加括号方式为是ssln+ln出断开,，照此递推下去,最终可以确定Al:n的最优完全加括号方式，即构造出问题的一个最优解。下面的算法tiaceback按算法matiixChain计算出的断点矩阵s指示的加扌舌号方式输出计算

10、Ai:j 的最优计算次序。void tiaceback (int i,mt j,mt sN+l)用递归来实现输出得到最小数乘次数的表达式if(i=j)pmitf (” A%d”,i);elsepnntf (-(');tiaceback (i,sij,s);traceback(si j+l j,s);pnntf要输出Al:n的最优计算次序只要调用上面的tiaceback (l,n,s)即可。对于上面所举得例子， 通过调用算法traceback (1,6, s),可输出最优计算次序(A1(A2A3)(A4A5)A6)。四、实验实施的条件计算机机房，微型计算机，Visual C卄6.0软件或

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

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

13、j;k+)mt t=mik+mk+l+pi-l*pk*pj;/* 计算当断开位置 k 为从 1 至 lj (不包 扌舌i和J)的所有取值对应的(Ai*.*Ak)*(Ak+l*.Aj)的数乘次数*/if(t<mij)mij=t；/将Ai*.Aj的最小数乘次数存入mijsij=V/W对应的断开位置k存入sijvoid traceback (int i,intj,mt sN+l)用递归来实现输出得到最小数乘次数的表达式if(i=j)pmitf (” A%d”,i);elsepnntfCC);traceback (i,si|j,s);traceback(si |j+l ,j,s);pmitf (

14、”)”)；void main Qmtn;/用来存储矩阵的个数int q2*N;/*用q数组来存储最原始的输入(各矩阵的行和列)，主要目的是为了检验这N 个矩阵是否满足连乘的条件*/int pN+l,flag=l;/*用pi-l,pi数组来存储A的阶数，flag用来判断这N个矩阵是否满足 连乘*/intmN+lN+l;/用mi|j _.维数组来存储Ai*.Aj的最小数乘次数int sN+lN+l;/用来存储使Ai.Aj获得最小数乘次数对应的断开位置k pnntfC请输入矩阵的个数(小于100)鋼； scanfC%d；&n);for (mt i=0;i<=2*n-l；1+)/各矩阵的

15、阶数的输入先存入数组q中接受检验if(i%2=0)prmtf(M* * *nn ) printff1*请输入 A%d 的行:”,(i/2)+l); elseprintff '列 *：-)；scanf ("%d'；&qi);for (1= 1 ;i<=2 *n-2 ;i+)矩阵连乘条件的检验if(i%2!=0&&q i!=qi+l)flag=0;break;for (mt j=l ;j<=n-l J+)pj=q2*j;if (flag!=0)p0=q0； pn=q2*n-l;niatrixChain (p,m,s); pnntf (”

16、式子如 FAn”); tiaceback(14KS);pnntfpnntf (”最小数乘次数为%dn",mln); elsepnntf S%d个矩阵不能连乘!n»实验结果：一、输入正确的情况:XJ<XXXXXXXXXXXX>CXX>CXX 玩靑输入"的行：30 fT I Iy 1 y y d LV 11 Jn n n Jn n n Jn n n Jn n n . J Iji>HWWHWWHWWHWWHW»HW»Hf琉靑输入呕的行：35列*«(*«(* 二 15>HWWHWWHWWHWWHW

17、87;HW»Hf琉靑输入的的行江5夕| *«(*«(*二 5>HWWHWWHWWHWWHW»HW»Hf琉靑输入肌的行：5|«-*-*-*-*-*-*-*-*： 10>HWWHWWHWWHWWHW»HW»Hf琉靑输入朋的行江07 I I y y y y y y y /*>HWWHWWHWWHWWHW»HW»Hf琉靑输入恥的行梧07 I I y y y y y y y ITy 11J|式子如卩«fil<fi2A3>X<A4fi5>fit)>二

18、、输入有误的情况:S?SmHwcw006X:M WXXK XXX M XX M XXM XM?>R< 卜革输入曲的行：30 rjy 11n Jn n n Jn n n Jn n n . J Iji|x-M?KX M?KX M?KX M?KXXXXXXXX入A2的行江535 pwwe>e«e>e«e>e«e>e«e>e«e>e* 卜请输入A3的行：35卜苹输入A4的行：20 片 |: 15卜苹输入白5的行卜涓输入恥的行：24 tew不能軽r<> .：六、编程体会经过了几天的连续研究，终于

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

20、题的答案，不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。 这就是动态规划的基本思想。具体的动态规划算法是多种多样的，但它们具有相同的填表格式。动态规划算法适用于解最优化问题。通常可以按以下步骤设计动态规划算法：（1）找出最优解的性质，并刻画其结构特征；（2）递归地定义最优值；（3）以自底向上的方式计算出最优值：（4）根据计算最优值时得到的信息，构造最优解。虽然已经了解了动态规划算法的基本思想，而且也参考了书上的算法，但是实际的情况却并不 是那么顺利，我按照书上编写程序之后，发现有很多逻辑错误，应该是编写坏境不同，所以出现了 一系列的问题，最后经过自己的多番研究发现了许多c语言

21、有许多默认的规则：就拿数组来讲，在 计算数组m和数组s时，虽然我们不用到卞标为零的元素，所以我一开始定义用长度为N*N的m 数组和s数组来分别存储矩阵的最小数乘次数和其对应的断开位置，但经过多次调试之后，发现总 是在求m*N和s*N时就会出错，后来才知道c语言的默认规则：不管我们用不用数组的零卞 标元素，卞标为零的元素都默认在该数组中，因此，必须把m和s数组的行列长度都必须加一才行, 经过这次程序设计之后，我懂得了一个道理，做程序设计，不仅要弄透解决这个问题的基本思想和 算法，而且要注意编程过程中的一些细节性问题，例如一些特定编程环境的默认规则，而且还要要 求我的逻辑思路一定要清晰，不然的话，很难发现自己先前所犯卞的逻辑错误，这样就很容易造成 事倍功半，效率低下。以上就是我这次的程序设计编程体会。七、成绩评定根据学习态度，任务完成质量（应用程序的难易程度、界面的友好性、程序的正确程度）和实 验报告质量进行打分，满分100分。项目成员 姓名、学号学习态度（25%）任务完成质（50%）实验报吿质量（25%）合计组长：成员一：成员二：成员三：