动态规划-矩阵链相乘

《动态规划-矩阵链相乘》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、超人的能量项链超人有一串能量项链，每棵能量珠Ui的头部和尾部分别具有能量pi和pi+1,前一能量珠的尾部能量等于后一能量珠的尾部能量，靠相邻两棵能量珠聚合为一棵能量珠释放能量，如能量珠Ui（pi*pi+1）和能量珠Ui（pi+1*pi+2）可聚合为新能量珠，头部能量为pi尾部能量为pi+2，释放能量为pi*pi+1*pi+2。已知该项链的头部能量数组为p[1…n],请计算该项链所能释放的最大能量例如：项链有四个能量珠，能量数组p如下：p1=4,p2=5,p3=2,p4=8则这四颗能量珠头尾部能量分别为（4，5）、（5，2）、（2，8）、（8，4）（（U1⊙U2）⊙U3

2、）⊙U4释放能量为4*5*2+4*2*8+4*8*4=232（U1⊙U2）⊙（U3⊙U4）释放能量为4*5*2+2*8*4+4*2*4=136（U1⊙（U2⊙U3））⊙U4释放能量为5*2*8+4*5*8+4*8*4=368U1⊙（（U2⊙U3）⊙U4）释放能量为5*2*8+5*8*4+4*5*4=320U1⊙（U2⊙（U3⊙U4））释放能量为2*8*4+5*2*4+4*5*4=184p1=4,p2=5,p3=2,p4=8得到项链的最大能量了吗？还没有，因为这仅仅是项链在从U4和U1之间断开的情况，项链还有其它三个可能的断开位置：从U1和U2之间断开；从U2和U3之间

3、断开；从U3和U4之间断开。另外，当n达到10时，就有上百万种组合方法，如何计算？7.4矩阵链相乘问题：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少两个矩阵相乘若A是一个p*q矩阵，B是一个q*r矩阵，则其乘积C=AB是一个p*r矩阵。for(i=1;i<=p;i++)for(j=1;j<=r;j++){c[i][j]=0;for(k=1;k<=q;k++)c[i][j]+=a[i][k]*b[k][j];}总共需要pqr次数乘。三个矩阵相乘现有三

4、个矩阵相乘：Dp☓s=Ap☓qBq☓rCr☓s我们知道矩阵相乘满足结合率，即(AB)C=A(BC)不同结合方法得到的结果是一样的，然而计算量却可能有很大差别。是否让你吃惊？如：A50☓5B5☓100C100☓10按(AB)C计算，所需乘法次数为：50☓5☓100+50☓100☓10=75000按A(BC）计算，所需乘法次数为：5☓100☓10+50☓5☓10=7500可见如何结合十分影响计算的效率，自然提出了矩阵链相乘的最优计算次序问题完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积是完全加括号的，则可表示为2个完全加括号的矩阵连乘

5、积和的乘积并加括号，即16000,10500,36000,87500,34500完全加括号的矩阵连乘积设有四个矩阵，它们的维数分别是：则有五种完全加括号方式：矩阵连乘问题给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积矩阵连乘问题问题：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算

6、矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少矩阵连乘问题穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：矩阵连乘问题穷举法动态规划将矩阵连乘积简记为A[i:j]，这里i≤j考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak-1和Ak之间将矩阵链断开，i

7、计算量：的计算量加上的计算量，再加上A[i:k-1]和A[k:j]相乘的计算量关于计算量如：A10☓100B100☓5C5☓50D50☓100按(AB)(CD)计算，所需乘法次数为：1、计算AB所需乘法次数：10☓100☓5=50002、计算CD所需乘法次数：5☓50☓100=250003、以上两个结果矩阵(AB)10☓5和(CD)5☓100再相乘的乘法次数:10☓5☓100=5000故按(AB)(CD)计算，所需乘法次数为：5000+25000+5000=35000规模为4的情况如：A15☓10A210☓4A34☓6A46☓10请给出计算A1A2A