动态规划矩阵连乘算法

1、实用标准文档问题描述：给定n个矩阵：Ai,A2,A n,其中A与A+1是可乘的，i=1 , 2，n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵 连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输 出结果为计算矩阵连乘积的计算次序和最少数乘次数。问题解析：由于矩阵乘法满足结合律，故计算矩阵的连乘积可 以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括 号，则可以依此次序反复调用2个矩阵相乘的标准 算法计算出矩阵连乘 积。完全加括号的矩阵连乘积可递归地定义为：(1)单个矩阵是完全加括号的；(2)矩阵

2、连乘积A是完全加括号的，则 A可表示为2个完全 加括号的矩阵连乘积B和C的乘积并加括号，即 A=(BC)例如，矩阵连乘积AA2AsA有5种不同的完全加括号的方式： (Al(A2(A3A4) , (Al(A 2A3)A4) , (A lA2)(A 3A4) , (A 1(A2A3)A 4), (A 1A2)A3)A4) o每一种完全加括号的方式对应于一个矩阵连乘积的计算 次序，这决定着作乘积所需要的计算量。看下面一个例子，计算三个矩阵连乘 A1, A2, Ab；维数分别 为10*100 , 100*5,5*50按此顺序计算需要的次数(A i*A2)*A 3):10X100X5+10X5X50=7

3、500次，按此顺序计算需要的次数 (Ai*(A 2*A3):10*5*50+10*100*50=75000 次所以问题是：如何确定运算顺序，可以使计算量达到最小 化。算法思路：例：设要计算矩阵连乘乘积 AAA3A4A5A5,其中各矩阵的维数 分别是：A1： 30*35;A2： 35*15;A3： 15*5;A4：5*10;A5： 10*20;A6： 20*25递推关系：设计算Ai:j ,1<i <j <n,所需要的最少数乘次数 mi,j, 则原问题的最优值为 m1,n。当 i=j 时，Ai:j=A i,因此，mii=0, i=1,2,n当i<j时，若Ai:j的最优次序在

4、A和A+1之间断开，i<=k<j,则：mij=mik+mk+1j+pi-1 PkP °由于在计算是并不知道断开点k的位置，所以k还未定。不过k的位置只有j-i个可能。因此，k 是这j-i个位置使计算量达到最小的那个位置。综上，有递推关系如下:°i = j吧in机艮打+掰附4】J + PiP也 i < ji<k<jJ构造最优解：若将对应mij的断开位置k记为sij,在计算出最优值mij后，可递归地由sij构造出相应的最优解。sij 中的数表明，计算矩阵链Ai:j的最佳方式应在矩阵 A和A+1之间断开，即最优的加括号方式应为(Ai:k)(Ak+1:

5、j) 。因此，从s1n记录的信息可知计算A1:n的最优加括号方式为(A1:s1n)(As1n+1:n),进一步递推，A1:s1n 的最优加括号方式为(A1:s1s1n)(As1s1n+1:s1s1n)。同理可以确定As1n+1:n的最优加括号方式在ss1n+1n 处断开照此递推下去，最终可以确定A1:n的最优完全加括号方式，及构造出 问题的一个最优解。1、穷举法列举出所有可能的计算次序，并计算出每一种计算次序相应 需要的数乘次数，从中找出一种数乘次数最少的计算次序。对于n个矩阵的连乘积，设其不同的计算次序为 P(n)。每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.A k)(A k+

6、i4)可以得到关于P(n)的递推式如下：产=1g网t'n-储:;卜尸® = GC比2)以上递推关系说明，P(n)是随n的增长呈指数增长的。因此， 穷举法不是一个多项式时间复杂度算法。2、重叠递归从以上递推关系和构造最优解思路出发，即可写出有子问题重叠性的递归代码实现：/3d1-1 重叠子问题的递归最优解/A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25/p0-6=30,35,15,5,10,20,25#include "stdafx.h"#include <iostream>using na

7、mespace std;const int L = 7;int RecurMatrixChain(int i,int j,int *s,int *p);/递归求最优解void Traceback(int i,int j,int *s);/构造最优解int main()int pL尸30,35,15,5,10,20,25;int *s = new 时 *L；for(int i=0;i<L;i+)si = new intL;cout<<"矩阵的最少计算次数为："<<RecurMatrixChain(1,6,s,p)<<endl;cout

8、<<"矩阵最优计算次序为："<<endl;Traceback(1,6,s);return 0;int RecurMatrixChain(int i,int j,int *s,int *p)if(i=j) return 0;int u =RecurMatrixChain(i,i,s,p)+RecurMatrixChain(i+1,j,s,p)+pi-1*pi*pj;s皿=i；for(int k=i+1; k<j; k+)int t = RecurMatrixChain(i,k,s,p) + RecurMatrixChain(k+1,j,s,p)

9、+ pi-1*pk*pj;if(t<u)u=t;sij=k；return u;void Traceback(int i,int j,int *s)if(i=j) return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout<<"Multiply A"<<i<<","<<sij;cout<<" and A"<<(s皿+1)<<","<<j<<endl;1.用算法R

10、ecurMatrixChain(1,4,s,p) 计算a1:4的计算递归树如下图所示:4.从上图可以看出很多子问题被重复运算。可以证明,该算法的计算时间T(n)有指数下界。设算法中判断语句和赋值语句为常数时间，则由算法的递归部分可得关于 T(n)的递归不等式:H-1£ (T(k) +- Jt)+O(l) m > 1“吟之- ©= o+这 “ ©5.6. 用数学归纳法可以证明丁之尸，因此，算法RecurMatrixChain的计算时间也随n指数增长。7. 3、备忘录递归算法8. 备忘录方法用表格保存已解决的子问题答案，在下次需要解决此子问题时，只要简单查看该子

11、问题的解答，而不必 重新计算。备忘录方法为每一个子问题建立一个记录项，初始 化时，该记录项存入一个特殊的值，表示该子问题尚未求解。 在求解的过程中，对每个带求的子问题，首先查看其相应的记 录项。若记录项中存储的是初始化时存入的特殊值，则表示该 问题是第一次遇到，此时计算出该子问题的解，并将其保存在 相应的记录项中，以备以后查看。若记录项中存储的已不是初 始化时存入的特殊值，则表示该子问题已被计算过，相应的记 录项中存储的是该子问题的解答。此时从记录项中取出该子问 题的解答即可，而不必重新计算。/3d1-2 矩阵连乘备忘录递归实现/A1 30*35 A2 35*15 A3 15*5 A4 5*1

12、0 A5 10*20 A6 20*25p0-6=30,35,15,5,10,20,25#include "stda仅.h”#include <iostream>using namespace std;const int L = 7;int LookupChain(int i,int j,int *m,int *s,int *p);int MemoizedMatrixChain(int n,int *m,int *s,int *p);void Traceback(int i,int j,int *s);/构造最优解int main()文案大全实用标准文档int pL=30,

13、35,15,5,10,20,25;int *s = new int *L;int *m = new int *L;for(int i=0;i<L;i+)si = new intL;mi = new intL;cout<<" 矩阵的最少计算次数为："<<MemoizedMatrixChain(6,m,s,p)<<endl;cout<<" 矩阵最优计算次序为："<<endl;Traceback(1,6,s);return 0;int MemoizedMatrixChain(int n,int

14、*m,int *s,int *p)for(int i=1; i<=n; i+)for(int j=1; j<=n; j+)mij=0;return LookupChain(1,n,m,s,p);int LookupChain(int i,int j,int *m,int *s,int *p)if(mij>0)return mij;if(i=j)return 0;int u = LookupChain(i,i,m,s,p) + LookupChain(i+1,j,m,s,p)+pi-1*pi*pj;sij=i;for(int k=i+1; k<j; k+)int t =

15、LookupChain(i,k,m,s,p) + LookupChain(k+1,j,m,s,p) + pi-1*pk*pj; if(t<u) u=t; sij = k；mij = u； return u;void Traceback(int i,int j,int *s)if(i=j) return;Traceback(i,sij,s);Traceback(sij+1,j,s);cout<<"Multiply A"<<i<<","<<sij； cout<<" and A&quo

16、t;<<(sij+1)<<","<<j<<endl;算法通过数组m记录子问题的最优值，m初始化为0,表明相应的子问题还没有被计算。在调用 LookupChain时，若mij>0,则表示其中存储的是所要求子问题的计算结果，直接返回即可。否则与直接递归算法一样递归计算，并将计算结果存入mij中返回。备忘录算法耗时O(nA3),将直接递归算法的计算时间从2M降至O(nA3)。3、动态规划迭代实现用动态规划迭代方式解决此问题， 可依据其递归式自底向上的 方式进行计算。在计算过程中，保存已解决的子问题的答案。每个子问 题只计算一次

17、，而在后面需要时只需简单检查一下，从而避免了大量的 重复计算，最终得到多项式时间的算法。/3d1-2 矩阵连乘动态规划迭代实现/A1 30*35 A2 35*15 A3 15*5 A4 5*10 A5 10*20 A6 20*25/p0-6=30,35,15,5,10,20,25#include "stdafx.h"#include <iostream>using namespace std;const int L = 7;int MatrixChain(int n,int *m,int *s,int *p);void Traceback(int i,int j

18、,int *s);/构造最优解int main()int pL=30,35,15,5,10,20,25;int *s = new int *L;int *m = new int *L;for(int i=0;i<L;i+)si = new intL;mi = new intL;cout<<" 矩阵的最少计算次数为："<<MatrixChain(6,m,s,p)<<endl;cout<<" 矩阵最优计算次序为："<<endl;Traceback(1,6,s);return 0;int Mat

19、rixChain(int n,int *m,int *s,int *p)for(int i=1; i<=n; i+)mii = 0;for(int r=2; r<=n; r+) /r为当前计算的链长(子问题规模)for(int i=1; i<=n-r+1; i+)/n-r+1为最后一个r 链的前边界int j = i+r-1;/计算前边界为r,链长为r的链的后边界mij= mi+1j+ pi-1*pi*pj;/将 链 ij 划 分 为 A(i) *(Ai+1：j)sij = i；for(int k=i+1; k<j; k+)/ 将链 ij 划分为(Ai:k )* (Ak+1:j)int t = mik + mk+1j + pi-1*pk*pj; if(t<mij)m皿=t；sij = k；return m1L-1; void Traceback(int i,int j,int *s)if(i=j) return;Traceback(i,sij,s);Traceback(si