矩阵连乘.doc

矩阵连乘一、 问题描述给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积。由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序。这种计算次序可以用加括号的方式确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可依此次序反复调用2个矩阵相乘的标准算法计算出矩阵的连乘积。完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号。即（）。例如，矩阵连乘积可以有以下种不同加括号方式：、每一种完全加括号方式对应于一种矩阵连乘积的计算次序，而矩阵连乘积的计算次序与计算量有密切关系。用动态规划法确定加括号次序，使得数乘次数最少。二问题分析 利用动态规划方法解问题的重要特征就是：问题具有最优子结构的性质。分析最优解的结构设计求解具体问题的动态规划算法的第一步是刻画该问题的最优解的结构特征。为方便起见，将矩阵连乘积简记为。考察计算的最优计算次序。设这个计算次序在矩阵和之间将矩阵断开，则相应的完全加括号方式为。依此次序，先计算和，然后将计算结果相乘得到，依此计算顺序总计算量为的计算量加上的计算量，再加上和相乘的计算量。 这个问题的关键特征是：计算的最优次序所包含的计算矩阵子链和的次序也是最优的。事实上，若有一个计算的次序需要的计算量更少，则用此次序替换原来计算的次序，得到的计算的计算量将比最优次序所需计算量更少，这是一个矛盾。同理可知，计算的最优次序所包含的计算矩阵子链的次序也是最优的。因此，矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。三、概要设计1、建立递归关系 设计动态规划算法的第二步是递归得定义最优值。对于矩阵连乘积的最优计算次序问题，设计算，所需最少数乘次数为，则原问题的最优值为。 当时，为单一矩阵，无需计算，因此=0，。当时，可利用最优子结构性质来计算。事实上，若的最优次序在和之间断开，则。由于在计算时并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i个可能，即。因此k是这j-i个位置中使计算量达到最小的那个位置。从而可以递归的定义为 给出了最优值，即计算所需的最少数乘次数。同时还确定了计算的最优次序中的断开位置，也就是说，对于这个有若将对应于的断开位置记为，在计算出最优值后，可递归地由构造出相应的最优解。2、计算最优值根据计算的递归式，写递归算法计算。简单的递归计算将消耗指数计算空间。注意到在递归计算过程中，不同的子问题个数只有个。事实上，对于，不同的有序对，对应于不同的子问题。因此，不同子问题的个数最多只有个。由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决了的子问题的答案。每个子问题只计算一次，而在后面计算时只要简单检查一下，从而避免了大量的重复计算。最终得到多项式时间的算法。下面所给出的动态规划算法MatrixChain中，输入参数存储于数组中。算法输出最有数组外还记录了最优断开位置的数组。void MatrixChain(int *p,int n,int m77,int s77)int i,j,r,k,t;for(i=0;in;i+)for(j=0;jn;j+)mij = 0;sij=0;for(r=2;r=n;r+)for(i=1;in-r+1;i+)j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(k=i+1;kj;k+)t=mik+mk+1j+pi-1*pk*pj;if(tmij)mij=t;sij=k; for(i=1;in;i+)for(j=1;jn;j+)printf(t%d ,mij);printf(n);算法MatrixChain首先计算出，然后，再根据递归式，按矩阵链长递增的方式依次计算，（矩阵链长度为2）；，（矩阵链长度为3）；。在计算时，只用到已计算出的和。3、构造最优解算法MatrixChain只是计算出了最优值，并为给出最优解。即通过算法MatrixChain的计算，只知道最少数乘次数，还不知道应按什么次序来做矩阵乘法才能达到最少的数乘次数。事实上MatrixChain算法已记录了构造最优解所需的全部信息。中的数表明，计算矩阵的最佳方式应在矩阵和之间断开，即最优的加括号方式为。因此，从记录的信息可知计算的最优加括号方式为。而的最优加括号方式为。同理可以确定的最优加括号方式在处断开照此递推下去，最终可以确定的最优完全加括号方式，即构造出问题的一个最优解。下面的Traceback按算法MatrixChain计算出的断点矩阵s指示的加括号方式输出计算的最优计算次序。void TraceBack(int m,int n,int s77)if(m = n) printf( A%d ,m); else if(m+1 = n) printf( A%d A%d),m,n); else printf( ( ); TraceBack(m,smn,s); TraceBack(smn+1,n,s); printf( ) ); 要输出的最优计算次序只要调用即可。四、详细设计与编码#include#includevoid MatrixChain(int *p,int n,int m77,int s77);void TraceBack(int m,int n,int s77);int main()int p8 = 30,35,15,5,10,20,25;int m77,s77,n=7;int i,j;printf(各矩阵的阶数依次为:n);for(i=0;i8;i+)printf(%dn,pi);printf(最少数乘次数mij如下:n);MatrixChain(p,n,m,s);printf(断开位置sij如下:n);for(i=1;in;i+)for(j=1;jn;j+)printf(t%d ,sij);printf(n);printf(最优计算次序为:n);TraceBack(1,6,s);printf(n);return 0;void MatrixChain(int *p,int n,int m77,int s77)int i,j,r,k,t;for(i=0;in;i+)for(j=0;jn;j+)mij = 0;sij=0;for(r=2;r=n;r+)for(i=1;in-r+1;i+)j=i+r-1;mij=mi+1j+pi-1*pi*pj;sij=i;for(k=i+1;kj;k+)t=mik+mk+1j+pi-1*pk*pj;if(tmij)mij=t;sij=k; for(i=1;in;i+)for(j=1;jn;j+)printf(t%d ,mij);printf(n);void TraceBack(int m,int n,int s77)if(m = n) printf( A%d ,m); else if(m+1 = n) printf( A%d A%d),m,n); else printf( ( ); TraceBack(m,smn,s); TraceBack(smn+1,n,s); printf( ) ); 五、 数据测试与分析1、数据测试各矩阵的阶数依次为:30351551020250最少数乘次数mij如下: 0 15750 7875 9375 11875 15125 0 0 2625 4375 7125 10500 0 0 0 750 2500 5375 0 0 0 0 1000 3500 0 0 0 0 0 5000 0 0 0 0 0 0断开位置sij如下: 0 1 1 3 3 3 0 0 2 3 3 3 0 0 0 3 3 3 0 0 0 0 4 5 0 0 0 0 0 5 0 0 0 0 0 0最优计算次序为: ( ( A1 ( A2 A3) ) ( ( A4 A5) A6 ) )Press any key to continue