《矩阵连乘问题》由会员分享，可在线阅读，更多相关《矩阵连乘问题（15页珍藏版）》请在金锄头文库上搜索。
1、目录：矩阵连乘问题：. 描述矩阵连乘问题2. 分析矩阵连乘问题以及对递归式的推导（1） 直接递归思路（2） 备忘录思路（3） 动态规划思路3. 伪代码的方式描述算法：(）直接递归算法（2）备忘录算法(3)动态规划算法4. 把算法转换成程序实现的过程及成果(1)直接递归算法程序（2)备忘录算法程序()动态规划算法程序.描述矩阵连乘问题:给定n个矩阵，其中和是可乘的，i=,2,，-。考察这n个矩阵的连乘积。由于矩阵乘法具有结合律,故计算矩阵的连乘积可以有许多不同的计算顺序。这种计算顺序可以用加括号的方式来拟定。若一种矩阵连乘积的计算顺序完全拟定，也就是说连乘积已完全加括号，则可依顺序反复调用个矩阵
2、相乘的原则算法计算出矩阵连乘积。完全加括号的矩阵连乘可递归地定义为:(1)单个矩阵是完全加括号的；（2)矩阵连乘积A是完全加括号的,则A可表达为2个完全加括号的矩阵连乘B和C的乘积并加括号,即A（C)。矩阵和B可乘的条件是矩阵A的列数等于矩阵B的行数。若是一种p的矩阵,B是一种r的矩阵,那么C=B就是一种pr矩阵。它的计算是三重循环的，计算量是p。如果加括号后矩阵的量是不同的，因此我们的问题就是要讨论如何给连乘的矩阵加括号才干使矩阵的计算量至少。穷举搜索法:对于个矩阵的连乘积,设有不同的计算顺序P（n)。由于可以先在第k个和第k+个矩阵之间将原矩阵序列分为两个矩阵子序列，k=1,.,n-;然后
3、分别对这两个矩阵子序列完全加括号；最后对所得的成果加括号，得到原矩阵序列的一种完全加括号方式。由此可得P(）的递归式如下： 1 =（n）= n 解此递归方程可得，P(n)=C(n1),而C（n)是一种指数增长的函数。因此穷举搜索法不是一种有效的算法。如下将用三种措施来解决矩阵连乘问题的最优加括号方式以及最优解。2. 分析矩阵连乘问题以及对递归式的推导将矩阵连乘积简记为Ai:j。考察计算A1：n的最优计算顺序。这个问题的一种核心特性是:计算A:n的最优顺序涉及的计算矩阵子链A:k和Ak+1：n的顺序也是最优的。这是由于：定义矩阵Ai的维数为i-1pi，则Ai:k的计算次数为pi-1k，A+1，的
4、计算次数为pkpj,而这两个总的矩阵最后相乘时的计算量是固定的，为pi-1pkpj。因此,矩阵连乘计算顺序问题的最优解涉及着其子问题的最优解。这种性质称为最优子构造性质。(1）、直接递归的思路:记计算i：j，1in,所需至少数乘次数为ij,则原问题的最优质为1n。由分析得知：m可以递归的定义为： jij= 1因此，当n1时,T(n）n2据此,可用数学归纳法证明T()2n-=。直接递归法的计算时间随的增长指数增长。(2）、备忘录措施的思路：备忘录措施为每个子问题建立一种记录项，初始化时，该记录项存入一种特殊的值,表达该问题尚未求解。在求解过程中,对每个待求的子问题，一方面查看其相应的记录项。若记
5、录项中存储的是初始化时存入的特殊值,则表达该问题第一次遇到,此时计算出该子问题的解，并保存在相应的记录项中,以备后来查看。若记录项中存储的不是初始化存入的特殊值,(例如初始化为,解答后赋值为），则表达该问题已被计算过，其相应的记录项中存储的应当是该子问题的解答。此时，只要从记录相中取出该子问题的解答即可，而不必重新计算。备忘录措施的计算量：由于是要计算ij,因此只要从n个变量中任意选出2个分别作为,j,则共有种选法，即有个子问题；当j时有种选法，因此总的子问题就为:+n=个。每填入一种记录项,就要耗费O（)的时间,因此备忘录措施的时间复杂度为O(n3)。（3)、动态规划措施的思路:（以6个矩阵
6、相乘为例）mij145602030x05xxx0xxxx0注意,在mij中，如果j是没故意义的,因此在表格中都即为x；并且，如果ij,则代表单个矩阵,因此mii=1.根据直接递归的措施的思路,如果规定ij,就必须规定mi和m1j，根据mj的矩阵,则如果规定解m12，则需要懂得m11和m1;如果规定解m1,则要懂得m1、m12和1和m23;以此类推。通过此规律可以总结出规定某一种元素,就要懂得其左方的所有元素的值和其下方的所有元素的值。mj1345610x0xx04xx5xxx06xxx动态规划就是按照上图所画的形式进行求解,从左下方求到右上方。动态规划算法的计算量重要取决于程序中对行、列和加括
7、号的位置k的三重循环。循环体内的计算量为O(）,而三重循环的总次数为O(n3)。因此该算法的计算时间上界为O(3)。和备忘录的算法的时间复杂度同样，都比直接递归的穷举搜索法有效得多。.伪代码的方式描述算法:（1） 直接递归算法: int RcurMtixCha(ini,int j)if(i=j） return 0;i u=RecurMarxChi(,i)+RcurtrixChn(+1，j)pi-1i*j;/递归， 为维数i=i;/记录加括号的位置o(int =i+;kj;k+)int t=eurMatrihan（,k)+RecuMariChain（k+1,j)+p*pkpj；递归f（tu） =
8、t; sijk;/判断哪个值更小，选用哪个retur ；（2） 备忘录算法：ntemoizdMatriCain（int n,int * * m,int * )fo(inti=；=;i+)o（nt j=i；)turn mi; /如果是已经解决的问题，则标记记录项mi已有值,且不小于,避免反复计算。if(i=j） return 0；it u=oouhain（，i)LookpChain(i+1,)pi-1*pi*pj；/递归sij=i;fr(int k=i+;j;k+）in t=ookupChan（i，)LookupChai(k+,j)p-*pj;/递归 f(t) u=t;sij=k; /找最小值i
9、=;retun u;（3） 动态规划算法：voi arixChin(i *p,nt ,int *m,i * *)for(int i1;i=;i+) mii=；(nr=2;r=n;r+) for(int i1；i=r+;i+）in j=i+r-1;/具体推导由来见下图mij=mi+1j+i-*pi*p;si=;for(ink=+;kj;+) int t=mik+k+1j+i1*p*pj; i(tj）m=; ijk;/sij记录加括号的位置下面的算法Tracebac按算法aixhin计算出的断点矩阵s批示的加括方式输出计算:的最优计算顺序:oi Tacba(int i，int j，int * *s
10、)i(i=j) ret；Traebac（i,sj,s)；/递归地对左边进行加括号 Tacebak(s+1,j，s)；/递归地对右边进行加括号outMultipl isij；ouandA(ij+1),jendl;/输出最优值和最优解。4. 把算法转换成程序实现的过程及成果程序源代码：mx.#nclue usignamepace td；#defineNU 100int mUMUM,sMNUM,NUM;/m代洙?表括?最?小？数簓乘?次？数簓的?矩?阵；?s记?录?的?是?最?佳?加括?号?的？位?置?;？p表括？示?矩?阵的？维?数簓,Ai的?维?数簓为api1pi.int n;/备?忘？录?方?法？iLoupin（nti,intj)if（ij)rtrn m;i (i =j)eturn 0；intu=LokupChin（i, )+LooChain（i+1,j)+pi-1pi*pj；sij=i;o (in k=+1;kj;k+)nt=LookpChai（i,k)okupChain(k+,j）i-1*k*pj;
