矩阵连乘问题.doc

目录：矩阵连乘问题：1. 描述矩阵连乘问题2. 分析矩阵连乘问题以及对递归式的推导（1）直接递归思路（ 2）备忘录思路（ 3）动态规划思路3. 伪代码的方式描述算法：（1）直接递归算法（ 2）备忘录算法（ 3）动态规划算法4. 把算法转换成程序实现的过程及结果（1）直接递归算法程序（2）备忘录算法程序（3）动态规划算法程序1. 描述矩阵连乘问题:给定n个矩阵{ A1 A2, An},其中Ai和Ai i是可乘的，i=1,2,…,n-1考察这n个矩阵的连 乘积Ai, A2, An由于矩阵乘法具有结合律，故计算矩阵的连乘积可以有许多不同的计算 次序这种计算次序可以用加括号的方式来确定若一个矩阵连乘积的计算次序完全确定， 也就是说连乘积已完全加括号，则可依次序反复调用 2个矩阵相乘的标准算法计算出矩阵连 乘积完全加括号的矩阵连乘可递归地定义为： (1)单个矩阵是完全加括号的；(2)矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘 B和C的乘积并加括号，即 A=( BC)矩阵A和B可乘的条件是矩阵 A的列数等于矩阵 B的行数若A是一个p X q的矩阵， B是一个q X r的矩阵，那么 C=A X B就是一个pX r矩阵。

它的计算是三重循环的，计算量 是pqr如果加括号后矩阵的量是不同的，所以我们的问题就是要讨论如何给连乘的矩阵加 括号才能使矩阵的计算量最少穷举搜索法：对于 n个矩阵的连乘积，设有不同的计算次序 P(n)由于可以先在第 k个和第k+1个矩阵之间将原矩阵序列分为两个矩阵子序列， k=1,2，…,n-1 ;然后分别对这两个矩阵子序列完全加括号；最后对所得的结果加括号， 得到原矩阵序列的一种完全加括号方式由此可得P(n)的递归式如下：1 n=1P (n) = Y^n 1P(k)P(n k) n>1k 1解此递归方程可得，P(n)=C(n-1),而C(n)是一个指数增长的函数因此穷举搜索法不是 一个有效的算法以下将用三种方法来解决矩阵连乘问题的最优加括号方式以及最优解2. 分析矩阵连乘问题以及对递归式的推导将矩阵连乘积 Ai,Ai 1, Aj简记为A[i:j]考察计算 A[1:n]的最优计算次序这个问题的一个关键特征是： 计算A[1:n]的最优次序包含的计算矩阵子链 A[1:k]和A[k+1:n]的次序也是最优的这是因为：定义矩阵Ai的维数为pi-1 X pi,则A[i:k]的计算次数为pi-1 X pk,A[k+1,j] 的计算次数为PkX pj，而这两个总的矩阵最后相乘时的计算量是固定的，为 pi-1 X pkX 口。

所以，矩阵连乘计算次序问题的最优解包含着其子问题的最优解 这种性质称为最优子结构性质1) 、直接递归的思路： 记计算A[i:j] , K i w jw n,所需最少数乘次数为 m[i][j],则原问题的最优质为m[1][n]由分析得知：m[i][j]可以递归的定义为：0 i=jm[i][j]= ^iri{m[i][k] m[k 1][ j] pi 1pkpj} i1k 1n 1因此，当 n>1 时，T(n) >n+2 T(k)k 1据此，可用数学归纳法证明 T(n) >2n-1= (2n)直接递归法的计算时间随 n的增长指数增长。

2) 、备忘录方法的思路：备忘录方法为每个子问题建立一个记录项， 初始化时，该记录项存入一个特殊的值， 表示该问题尚未求解在求解过程中，对每个待求的子问题， 首先查看其相应的记录项若记录项中存储的是初始化时存入的特殊值，则表示该问题第一次遇到， 此时计算出该子问题的解，并保存在相应的记录项中，以备以后查看若记录项中存储的不 是初始化存入的特殊值，(比如初始化为-1，解答后赋值为 0),则表示该问题已被计算过， 其相应的记录项中存储的应该是该子问题的解答 此时，只要从记录相中取出该子问题的解答即可，而不必重新计算备忘录方法的计算量：因为是要计算 m[i][j],因此只要从n个变量中任意选出2个分别作为i，j，则共有C；种选法，即有C2个子问题；当i=j时有n种选法，所以总的子问题就为：C2+门=亜卫 个每填入一个记录项，就要花费 O( n)的时间，所以备忘录方法的时间复2杂度为O(n3)3)、动态规划方法的思路：(以6个矩阵相乘为例)m[i][j]123456102x03xx04xxx05xxxx06xxxxx0注意，在m[i][j]中，如果i>j是没有意义的，因此在表格中都即为 x;而且，如果i=j，则代表单个矩阵，所以 m[i][i]=1.根据直接递归的方法的思路， 如果要求m[i][j],就必须要求m[i][k]和m[k+1][j],根据m[i][j]的矩阵，则如果要求解 m[1][2]，则需要知道 m[1][1]和m[1][2];如果要求解 m[1][3]，则要知 道m[1][1]、m[1][2]和m[1][1]和m[2][3];以此类推。

通过此规律可以总结出要求某一个元素，就要知道其左方的所有元素的值和其下方的所有元素的值m[i][j]12345610. 2x0■3xx04xxx05xxxx06xxxxx0动态规划就是按照上图所画的形式进行求解，从左下方求到右上方动态规划算法的计算量主要取决于程序中对行、 列和加括号的位置 k 的三重循环 循环体内的计算量为0(1),而三重循环的总次数为 0(n3)因此该算法的计算时间上界为 0(n3)和备忘录的算法的时间复杂度一样，都比直接递归的穷举搜索法有效得多3. 伪代码的方式描述算法：1 )直接递归算法：int RecurMatrixChain(int i,int j){if(i==j) return 0;递归，p[]为维递归int u=RecurMatrixChain(i,i)+RecurMatrixChain(i+1,j)+p[i-1]*p[i]*p[j];// 数s[i][j]=i;// 记录加括号的位置for(int k=i+1;k

return LookupChain(1,n);}int LookupChain(int i,int j){if(m[i][j]>0) return m[i][j]; // 如果是已经解决的问题，则标记记录项 m[i][j] 已经有值 ,且 大于 0，避免重复计算if(i==j) return 0;int u=LookupChain(i,i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j];// 递归s[i][j]=i;for(int k=i+1;k

}4. 把算法转换成程序实现的过程及结果程序源代码：matrix.h#in clude using n amespace std;#defi ne NUM 100int m[NUM][NUM],s[NUM][NUM],p[NUM];//m[][] 代洙？表括？最？小？数簓乘？次？数簓的？矩？阵o;?s[][] 记？录？的？是？最？佳？加6括鬲？号？的？位？置？ ； ?p[]表括？示？矩？阵6的?维？数簓,A[i]的？维？数簓为 即[i-1] Xdp[i],int n;//备?忘 ?录？方？法鬲?int LookupCha in (i nt i,i nt j){if (m[i][j]>0){return m[i][j];} if (i == j)return 0;int u=LookupChain(i, i)+LookupChain(i+1,j)+p[i-1]*p[i]*p[j]; s[i][j]=i;for (int k=i+1; k