矩阵连乘积问题

《矩阵连乘积问题》由会员分享，可在线阅读，更多相关《矩阵连乘积问题（3页珍藏版）》请在金锄头文库上搜索。

1、矩阵连乘问题 By Aillo on May 13, 2008 4:32 PM | 0 Comments | Previous | Next | EDIT 【问题问题】：矩阵链乘问题矩阵链乘问题：给定 n 个矩阵A1,A2,.,An，其中 Ai 与 Ai+1 是可乘的，i=1，2.，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。【解题解题】：这里我采用的是动态划分算法：设计动态规划算法动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解(由

2、子结构的最优解得到原先大问题的最优解)。【解题关键解题关键】：将一系列相乘的矩阵（Ai.Aj）划分为两部分;即（AiAi+1.Ak）(Ak+1Ak+2.Aj)，k 的位置要保证左边括号和右边括号相乘的消耗最小。 【思路思路】：这里我采用两种方法来实现：（1）用三重 for 循环来实现：根据主对角线的方向及其右边与之平行的对角线方向，由上至下，从左到右分别求出 Cij的值，后面要求的值都可以根据前面所求的的值来求。Cij代表矩阵链 Ai.Aj 相乘的最小消耗。其中：cii=0，i=1,2,.n求解的顺序如下：C12,C23,C23,.,CN-1N,C13,C24.CN-2N.CNN最后得到的 C

3、NN的值就是我们所求的。（2）备忘录方法（即递归算法）：将整个矩阵链分成两部分，然后在分别对两边的子矩阵链递归调用算法。【程序代码程序代码】：两种方法都在其中：#include#include#include#include#define MAX_VALUE 100#define N 201 /连乘矩阵的个数(n-1)#define random() rand()%MAX_VALUE /控制矩阵的行和列的大小int cNN, sNN, pN;int matrixchain(int n) /3 个 for 循环实现 for(int k=1;k0)return cij;if(i=j)return

4、0;int u=lookupchain(i,i)+lookupchain(i+1,j)+pi-1*pi*pj;sij=i;for(int k=i+1;kj;k+)int t=lookupchain(i,k)+lookupchain(k+1,j)+pi-1*pk*pj;if(tu)u=t;sij=k;cij=u;return u;void main()srand(int)time(NULL);for(int i=0;iN;i+) / 随机生成数组 p，各个元素的值的范围：1MAX_VALUEpi=random()+1;clock_t start,end; double elapsed;start

5、=clock();/cout“Count: “matrixchain(N-1)endl; /3 重 for 循环实现cout“Count: “lookupchain(1,N-1)endl; /备忘录方法end=clock();elapsed=(double)(end-start);/CLOCKS_PER_SEC; cout“Time: “elapsedendl;Print(s,1,N-1); /输出矩阵连乘积的计算次序coutendl;【总结总结】：两种算法的时间复杂度均为 o(n3)，,随着数据量的增多，备忘录方法消耗的时间越长；我觉得是由于递归算法，随着数据量增大，调用函数的次数也增大，语句被执行的时间也越多，因此调用函数消耗的时间也增多。