动态规划-矩阵链相乘

单击此处编辑母版标题样式,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,超人的能量项链,超人有一串能量项链，每棵能量珠,U,i,的头部和尾部分别具有能量,p,i,和,p,i+1,前一能量珠的尾部能量等于后一能量珠的尾部能量，靠相邻两棵能量珠聚合为一棵能量珠释放能量，如能量珠,Ui,（,p,i,*p,i+1,）和能量珠,U,i,（,p,i+1,*p,i+2,）可聚合为新能量珠，头部能量为,pi,尾部能量为,p,i+2,，释放能量为,p,i,*p,i+1,*p,i+2,。,已知该项链的头部能量数组为,p1n,请计算该项链所能释放的最大能量,例如：项链有四个能量珠，能量数组,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,个矩阵,A,1,A,2,A,n,，,其中,A,i,与,A,i+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,次数乘。,三个矩阵相乘,现有三个,矩阵,相乘：,D,p,s,=,A,p,q,B,q,r,C,r,s,我们知道矩阵相乘满足结合率，即,(AB)C=A(BC),不同结合方法得到的结果是一样的，然而计算量却可能有很大差别。,是否让你吃惊？,如：,A,50,5,B,5,100,C,100,10,按,(AB)C,计算，所需乘法次数为：,50 5 100+50 100 10=,75000,按,A(BC,）,计算，所需乘法次数为：,5 100 10+505 10=,7500,可见如何结合十分影响计算的效率，自然提出了矩阵链相乘的最优计算次序问题,完全加括号的矩阵连乘积可递归地定义为：,（,1,）单个矩阵是完全加括号的；,（,2,）矩阵连乘积 是完全加括号的，则 可,表示为,2,个完全加括号的矩阵连乘积 和,的乘积并加括号，即,16000,10500,36000,87500,34500,完全加括号的矩阵连乘积,设有四个矩阵 ，它们的维数分别是：,则有五种完全加括号方式：,矩阵连乘问题,给定,n,个矩阵 ，其中 与 是可乘的，。考察这,n,个矩阵的连乘积,由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。,若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用,2,个矩阵相乘的标准算法计算出矩阵连乘积,矩阵连乘问题,问题：给定,n,个矩阵,A,1,A,2,A,n,，,其中,A,i,与,A,i+1,是可乘的，,i=1,，,2,，,n-1,。,如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少,矩阵连乘问题,穷举法,：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：,对于,n,个矩阵的连乘积，设其不同的计算次序为,P(n),。,由于每种加括号方式都可以分解为两个子矩阵的加括号问题：,(A,1,.A,k,)(A,k+1,A,n,),可以得到关于,P(n),的递推式如下：,矩阵连乘问题,穷举法,动态规划,将矩阵连乘积 简记为,Ai:j,，,这里,i,j,考察计算,Ai:j,的最优计算次序。设这个计算次序在矩阵,A,k-1,和,A,k,之间将矩阵链断开，,i,kj,，,则其相应完全加括号方式为,计算量：的计算量加上,的计算量，再加上,Ai:k-1,和,Ak:j,相乘的计算量,关于计算量,如：,A,10100,B,100,5,C,5,50,D,50,100,按,(AB)(CD),计算，所需乘法次数为：,1,、计算,AB,所需乘法次数：,10100 5=,5000,2,、计算,CD,所需乘法次数：,550 100=,25000,3,、以上两个结果矩阵,(AB),105,和,(CD),5,100,再相乘的乘法次数,:,105,100=,5000,故按,(AB)(CD),计算，所需乘法次数为：,5000+25000+5000=35000,规模为,4,的情况,如：,A1,510,A2,10,4,A3,4,6,A4,6,10,请给出计算,A1A2A3A4,的最优计算次序,1,、计算规模为,2,的子问题,计算,A1A2,所需乘法次数：,510,4=200,计算,A2A3,所需乘法次数：,104 6=,240,计算,A3A4,所需乘法次数：,4610=,240,A1,510,A2,10,4,A3,4,6,A4,6,10,2,、,计算规模为,3,的子问题,(1),计算,A1A2A3,所需乘法次数，有两种结合方法,:(A1A2)A3,和,A1(A2A3),选最好的一种：,(A1A2)A3:,计算量：,320,(A1A2)A3:,计算,A1A2,的计算量,+,计算,A1:2,乘,A3,的计算量：,200+5 4 6=,320,A1(A2A3):,计算,BC,的计算量,+,计算,A1,乘,A2:3,的计算量：,240+5 10 6=,540,A1,510,A2,10,4,A3,4,6,A4,6,10,(2),计算,A2A3A4,所需乘法次数，有两种结合方法,:(A2A3)A4,和,A2(A3A4),，,选最好的一种：,计算,A2A3,的计算量,+,计算,A2:3,乘,A4,的计算量：,240+10 6 10=840,A2(A3A4):,计算,A3A4,的计算量,+,计算,A2,乘,A3:4,的计算量：,240+10 4 10=640,A2(A3A4):,计算量：,640,A1,510,A2,10,4,A3,4,6,A4,6,10,3,计算规模为,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=640,A1(A2A3A4):640+5 10 10=1140,(A1A2A3)A4:,计算量：,620,用数组元素,Cij,来存储计算,Ai:j,的最少数乘次数,例,7.1,：,A1,510,A2,10,4,A3,4,6,A4,6,10,请给出计算,A1,：,4,的最优计算次序,1,、计算规模为,2,的子问题,计算,A1,：,2,所需乘法次数：,510 4,=200,计算,A2,：,3,所需乘法次数：,104 6=,240,计算,A3,：,4,所需乘法次数：,4610=,240,将,计算,Ai:j,所需最小数乘次数存入数组,cij,中,C12=200 C23=240 C34=240,A1,510,A2,10,4,A3,4,6,A4,6,10,2,、,计算规模为,3,的子问题,计算,A1:3,所需乘法次数，有两种结合方法，选最好的一种：,(A1:2)A3:,计算,A1:2,的计算量,+,计算（,A1:2,）乘,A3,的计算量：,200,+5 4 6=,320,A1(A2:3):,计算,A2:3,的计算量,+,计算,A1,乘,(A2:3),的计算量：,240,+5 10 6=,540,C13=320,A1,510,A2,10,4,A3,4,6,A4,6,10,计算,A2:4,所需乘法次数，有两种结合方法，选最好的一种：,840,(A2:3)A4:,计算,A2:3,的计算量,+,计算,A2:3,乘,A4,的计算量：,240,+10 6 10=,840,A2(A3:4):,计算,A3:4,的计算量,+,计算,A2,乘,(A3:4),的计算量：,240,+10 4 10=,640,C24=640,A1,510,A2,10,4,A3,4,6,A4,6,10,3,计算规模为,4,的原问题,A1:4,所需乘法次数，有三种结合方法，选最好的一种：,(A1:3)A4:,计算,A1:3,的,最小,计算量,+,计算（,A1:3,）乘,A4,的计算量：,320,+5 6 10=,620,(A1:2)(A3:4):,200,+,240,+5 4 10=,640,A1(A2:4):,640,+5 10 10=1140,C14=620,A1,510,A2,10,4,A3,4,6,A4,6,10,d=0,d=1,d=2,d=3,C1:1=0,C1:2=200,C1:3=320,C2:2=0,C2:3=240,C2:4=640,C3:3=0,C3:4=240,C4:4=0,将例,7.1,中的中间结果存入数组,C1:1=0,C1:2=200,C1:3=320,C1:4=620,C2:2=0,C2:3=240,C2:4=640,C3:3=0,C3:4=240,C4:4=0,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,在,A,k,前断开：,(A,i,A,k-1,)(A,k,A,j,),使,Ci,j,达到最小,这里 的维数为,的位置只有,种,可能,可以递归地定义,Ci,j,为：,计算最优值,对于,1ijn,不同的有序对,(i,j),对应于不同的子问题。因此，不同子问题的个数最多只有,由此可见，在递归计算时，,许多子问题被重复计算多次,。这也是该问题可用动态规划算法求解的又一显著特征。,动态规划,-,自底向上进行计算,用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法,课堂练习,(1),请给出计算,M1M2M3M4M5,乘积所需的最少数乘次数,（即,C15,）。,（,2,）,请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。,M1,M2,M3,M4,M5,45,53,36,64,45,p,1,=4,p,1,=5,p,3,=3,p,4,=6,p,5,=4,p,6,=5,C