动态规划-矩阵链相乘

超人的能量项链,超人有一串能量项链，每棵能量珠Ui的头部和尾部分别具有能量pi和pi+1,前一能量珠的尾部能量等于后一能量珠的尾部能量，靠相邻两棵能量珠聚合为一棵能量珠释放能量，如能量珠Ui（pi*pi+1）和能量珠Ui（pi+1*pi+2）可聚合为新能量珠，头部能量为pi尾部能量为pi+2，释放能量为pi*pi+1*pi+2。已知该项链的头部能量数组为p1n,请计算该项链所能释放的最大能量,例如：项链有四个能量珠，能量数组p如下：p1=4,p2=5,p3=2,p4=8则这四颗能量珠头尾部能量分别为（4，5）、（5，2）、（2，8）、（8，4）,（U1U2）U3）U4释放能量为4*5*2+4*2*8+4*8*4=232（U1U2）（U3U4）释放能量为4*5*2+2*8*4+4*2*4=136（U1（U2U3）U4释放能量为5*2*8+4*5*8+4*8*4=368U1（U2U3）U4）释放能量为5*2*8+5*8*4+4*5*4=320U1（U2（U3U4）释放能量为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+)cij=0;for(k=1;k=q;k+)cij+=aik*bkj;总共需要pqr次数乘。,三个矩阵相乘,现有三个矩阵相乘：Dps=ApqBqrCrs我们知道矩阵相乘满足结合率，即(AB)C=A(BC)不同结合方法得到的结果是一样的，然而计算量却可能有很大差别。,是否让你吃惊？,如：A505B5100C10010按(AB)C计算，所需乘法次数为：505100+5010010=75000按A(BC）计算，所需乘法次数为：510010+50510=7500,可见如何结合十分影响计算的效率，自然提出了矩阵链相乘的最优计算次序问题,完全加括号的矩阵连乘积可递归地定义为：（1）单个矩阵是完全加括号的；（2）矩阵连乘积是完全加括号的，则可表示为2个完全加括号的矩阵连乘积和的乘积并加括号，即,16000,10500,36000,87500,34500,完全加括号的矩阵连乘积,设有四个矩阵，它们的维数分别是：,则有五种完全加括号方式：,矩阵连乘问题,给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积,由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。,若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,矩阵连乘问题,问题：给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少,矩阵连乘问题,穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：,矩阵连乘问题,穷举法动态规划,将矩阵连乘积简记为Ai:j，这里ij,考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak-1和Ak之间将矩阵链断开，ikj，则其相应完全加括号方式为,计算量：的计算量加上的计算量，再加上Ai:k-1和Ak:j相乘的计算量,关于计算量,如：A10100B1005C550D50100按(AB)(CD)计算，所需乘法次数为：1、计算AB所需乘法次数：101005=50002、计算CD所需乘法次数：550100=250003、以上两个结果矩阵(AB)105和(CD)5100再相乘的乘法次数:105100=5000故按(AB)(CD)计算，所需乘法次数为：5000+25000+5000=35000,规模为4的情况,如：A1510A2104A346A4610请给出计算A1A2A3A4的最优计算次序1、计算规模为2的子问题计算A1A2所需乘法次数：5104=200计算A2A3所需乘法次数：1046=240计算A3A4所需乘法次数：4610=240,A1510A2104A346A46102、计算规模为3的子问题(1)计算A1A2A3所需乘法次数，有两种结合方法:(A1A2)A3和A1(A2A3),选最好的一种：,(A1A2)A3:计算量：320,(A1A2)A3:计算A1A2的计算量+计算A1:2乘A3的计算量：200+546=320A1(A2A3):计算BC的计算量+计算A1乘A2:3的计算量：240+5106=540,A1510A2104A346A4610(2)计算A2A3A4所需乘法次数，有两种结合方法:(A2A3)A4和A2(A3A4)，选最好的一种：,计算A2A3的计算量+计算A2:3乘A4的计算量：240+10610=840A2(A3A4):计算A3A4的计算量+计算A2乘A3:4的计算量：240+10410=640,A2(A3A4):计算量：640,A1510A2104A346A46103计算规模为4的原问题A1A2A3A4所需乘法次数，有三种结合方法:(A1A2A3)A4、(A1A2)(A3A4)、A1(A2A3A4)，选最好的一种：,(A1A2A3)A4:计算A1A2A3的最小计算量+计算（A1A2A3）乘A4的计算量：320+5610=620(A1A2)(A3A4):200+240+5410=640A1(A2A3A4):640+51010=1140,(A1A2A3)A4:计算量：620,用数组元素Cij来存储计算Ai:j的最少数乘次数,例7.1：A1510A2104A346A4610请给出计算A1：4的最优计算次序1、计算规模为2的子问题计算A1：2所需乘法次数：5104=200计算A2：3所需乘法次数：1046=240计算A3：4所需乘法次数：4610=240,将计算Ai:j所需最小数乘次数存入数组cij中,C12=200C23=240C34=240,A1510A2104A346A46102、计算规模为3的子问题计算A1:3所需乘法次数，有两种结合方法，选最好的一种：(A1:2)A3:计算A1:2的计算量+计算（A1:2）乘A3的计算量：200+546=320A1(A2:3):计算A2:3的计算量+计算A1乘(A2:3)的计算量：240+5106=540,C13=320,A1510A2104A346A4610计算A2:4所需乘法次数，有两种结合方法，选最好的一种：840(A2:3)A4:计算A2:3的计算量+计算A2:3乘A4的计算量：240+10610=840A2(A3:4):计算A3:4的计算量+计算A2乘(A3:4)的计算量：240+10410=640,C24=640,A1510A2104A346A46103计算规模为4的原问题A1:4所需乘法次数，有三种结合方法，选最好的一种：(A1:3)A4:计算A1:3的最小计算量+计算（A1:3）乘A4的计算量：320+5610=620(A1:2)(A3:4):200+240+5410=640A1(A2:4):640+51010=1140,C14=620,A1510A2104A346A4610,d=0,d=1,d=2,d=3,将例7.1中的中间结果存入数组,d=0,d=1,d=2,d=3,特征：计算Ai:j的最优次序所包含的计算矩阵子链Ai:k-1和Ak:j的次序也是最优的。举例矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,分析最优解的结构,建立递归关系,设计算Ai:j，1ijn，所需要的最少数乘次数ci,j，则原问题的最优值为c1,n当i=j时，Ai:j=Ai，因此，ci,i=0，i=1,2,n当ij时，需找到一个分割点k,在Ak前断开：(AiAk-1)(AkAj),使Ci,j达到最小,这里的维数为,的位置只有种可能,可以递归地定义Ci,j为：,计算最优值,对于1ijn不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。,动态规划-自底向上进行计算,用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法,课堂练习,(1)请给出计算M1M2M3M4M5乘积所需的最少数乘次数（即C15）。（2）请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。,p1=4,p1=5,p3=3,p4=6,p5=4,p6=5,p1=4,p2=5,p3=3,p4=6,p5=4,p6=5,p1=4,p1=5,p3=3,p4=6,p5=4,p6=5,p1=4,p1=5,p3=3,p4=6,p5=4,p6=5,C1:5=252k=3,最优计算次序：(M1M2)(M3M4)M5),用动态规划法求最优解,voidMatrixChain(int*p，intn，int*c，int*s)for(inti=1;i=n;i+)cii=0;/填充对角线d=0for(intd=1;d=n-1;d+)/填充对角线d，,d=1,n-1for(inti=1;i=nd;i+)填充对角线d上第i个元素intj=i+d;/以下几行计算CIjcij=Max;for(k=i+1,k=j;k+)cij=mincij,cik-1+ckj+rirkrj);sij=使cIj达到最小的k;,mij=mi+1j+pi-1*pi*pj;/从i+1位置断开sij=i+1;for(intk=i+2;kA;cinB;intm=strlen(A),n=strlen(B);LCSlength(m,n,A,B,c);,程序5:动态分配存储空间(推荐）,#defineN100voidLCSlength(intm,intn,charx,chary,int*c)main()charAN,BN;int*c;gets(A);gets(B);intm=strlen(A),n=strlen(B);c=newintm*n;LCSlength(m,n,A,B,c);,用ci*n+j来代替cij,程序6:双重指针1,#defineN100voidLCSlength(intm,intn,charx,chary,int*c)main()charAN,BN;int*c;gets(A);gets(B);intm=strlen(A),n=strlen(B);c=newint*m;for(inti=0;im;i+)ci=newintn;LCSlength(m,n,A,B,c);,int*c;,c,1010,1050,2030,1050,1010,2030,for(inti=0;im;i+)ci=newintn;,c=newint*m;,程序7:双重指针2,#defineN100voidLCSlength(intm,intn,c