动态规划-矩阵链相乘

超人的能量项链超人有一串能量项链，每棵能量珠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）⊙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=368U1⊙（（U2⊙U3）⊙U4）释放能量为5*2*8+5*8*4+4*5*4=320U1⊙（U2⊙（U3⊙U4））释放能量为2*8*4+5*2*4+4*5*4=184p1=4,p2=5,p3=2,p4=8得到项链的最大能量了吗？还没有，因为这仅仅是项链在从U4和U1之间断开的情况，项链还有其它三个可能的断开位置：从U1和U2之间断开；从U2和U3之间断开；从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次数乘。三个矩阵相乘现有三个矩阵相乘：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个完全加括号的矩阵连乘积和的乘积并加括号，即AABC)(BCA)))(((DBCA)))(((DCAB)))(((DBCA)))(((CDBA)))(((CDAB16000,10500,36000,87500,34500完全加括号的矩阵连乘积1050A4010B3040C530D设有四个矩阵，它们的维数分别是：DCBA,,,则有五种完全加括号方式：矩阵连乘问题给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积},...,,{21nAAAiA1iA1,...,2,1ninAAA...21由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。•若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积矩阵连乘问题问题：给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少矩阵连乘问题穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk矩阵连乘问题穷举法动态规划将矩阵连乘积简记为A[i:j]，这里i≤jjiiAAA...1考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak-1和Ak之间将矩阵链断开，ik≤j，则其相应完全加括号方式为)...)(...(111jkkkiiAAAAAA计算量：的计算量加上的计算量，再加上A[i:k-1]和A[k:j]相乘的计算量Ai)...(11kiiAAA)...(1jkkAAA关于计算量如：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请给出计算A1A2A3A4的最优计算次序1、计算规模为2的子问题计算A1A2所需乘法次数：5☓10☓4=200计算A2A3所需乘法次数：10☓4☓6=240计算A3A4所需乘法次数：4☓6☓10=240A15☓10A210☓4A34☓6A46☓102、计算规模为3的子问题(1)计算A1A2A3所需乘法次数，有两种结合方法:(A1A2)A3和A1(A2A3),选最好的一种：(A1A2)A3:计算量：320(A1A2)A3:计算A1A2的计算量+计算A[1:2]乘A3的计算量：200+5☓4☓6=320A1(A2A3):计算BC的计算量+计算A1乘A[2:3]的计算量：240+5☓10☓6=540A15☓10A210☓4A34☓6A46☓10(2)计算A2A3A4所需乘法次数，有两种结合方法:(A2A3)A4和A2(A3A4)，选最好的一种：计算A2A3的计算量+计算A[2:3]乘A4的计算量：240+10☓6☓10=840A2(A3A4):计算A3A4的计算量+计算A2乘A[3:4]的计算量：240+10☓4☓10=640A2(A3A4):计算量：640A15☓10A210☓4A34☓6A46☓103计算规模为4的原问题A1A2A3A4所需乘法次数，有三种结合方法:(A1A2A3)A4、(A1A2)(A3A4)、A1(A2A3A4)，选最好的一种：(A1A2A3)A4:计算A1A2A3的最小计算量+计算（A1A2A3）乘A4的计算量：320+5☓6☓10=620(A1A2)(A3A4):200+240+5☓4☓10=640A1(A2A3A4):640+5☓10☓10=1140(A1A2A3)A4:计算量：620用数组元素C[i][j]来存储计算A[i:j]的最少数乘次数例7.1：A15☓10A210☓4A34☓6A46☓10请给出计算A[1：4]的最优计算次序1、计算规模为2的子问题计算A[1：2]所需乘法次数：5☓10☓4=200计算A[2：3]所需乘法次数：10☓4☓6=240计算A[3：4]所需乘法次数：4☓6☓10=240将计算A[i:j]所需最小数乘次数存入数组c[i][j]中C[1][2]=200C[2][3]=240C[3][4]=240A15☓10A210☓4A34☓6A46☓102、计算规模为3的子问题计算A[1:3]所需乘法次数，有两种结合方法，选最好的一种：(A[1:2])A3:计算A[1:2]的计算量+计算（A[1:2]）乘A3的计算量：200+5☓4☓6=320A1(A[2:3]):计算A[2:3]的计算量+计算A1乘(A[2:3])的计算量：240+5☓10☓6=540C[1][3]=320A15☓10A210☓4A34☓6A46☓10计算A[2:4]所需乘法次数，有两种结合方法，选最好的一种：840(A[2:3])A4:计算A[2:3]的计算量+计算A[2:3]乘A4的计算量：240+10☓6☓10=840A2(A[3:4]):计算A[3:4]的计算量+计算A2乘(A[3:4])的计算量：240+10☓4☓10=640C[2][4]=640A15☓10A210☓4A34☓6A46☓103计算规模为4的原问题A[1:4]所需乘法次数，有三种结合方法，选最好的一种：(A[1:3])A4:计算A[1:3]的最小计算量+计算（A[1:3]）乘A4的计算量：320+5☓6☓10=620(A[1:2])(A[3:4]):200+240+5☓4☓10=640A1(A[2:4]):640+5☓10☓10=1140C[1][4]=620A15☓10A210☓4A34☓6A46☓10d=0d=1d=2d=3C[1:1]=0C[1:2]=200C[1:3]=320C[2:2]=0C[2:3]=240C[2:4]=640C[3:3]=0C[3:4]=240C[4:4]=0将例7.1中的中间结果存入数组C[1:1]=0C[1:2]=200C[1:3]=320C[1:4]=620C[2:2]=0C[2:3]=240C[2:4]=640C[3:3]=0C[3:4]=240C[4:4]=0d=0d=1d=2d=3特征：计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k-1]和A[k:j]的次序也是最优的。举例矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。分析最优解的结构建立递归关系设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数c[i,j]，则原问题的最优值为c[1,n]当i=j时，A[i:j]=Ai，因此，c[i,i]=0，i=1,2,…,n当ij时，需找到一个分割点k,在Ak前断开：(Ai…Ak-1)(Ak…Aj),使C[i,j]达到最小这里的维数为1],[]1,[],[jkipppjkCkiCjiCiA1iippjipppjkCkiCjijiCjki}],[]1,[{min0],[1jki的位置只有种可能kij可以递归地定义C[i,j]为：计算最优值对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。)(22nnn动态规划--自底向上进行计算用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法课堂练习(1)请给出计算M1M2M3M4M5乘积所需的最少数乘次数（即C[1][5]）。（2）请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。M1M2M3M4M54☓55☓33☓66☓44☓5p1=4,p1=5,p3=3,p4=6,p5=4,p6=5C[1:1]=060132K=3180K=3C[2:2]=090132K=3C[3:3]=07272+3*4*5K=5C[4:4]=0120C[5:5]=0p1=4,p2=5,p3=3,p4=6,p5=4,p6=5C[1:1]=0C[1:2]=60C[2:2]=0C[2:3]=90C[3:3]=0C[3:4]=72C[4:4]=0C[4:5]=120C[5:5]=0p1=4,p1=5,p3=3,p4=6,p5=4,p6=5C[1:1]=0C[1:2]=60