动态规划 矩阵链相乘ppt课件.ppt

超人的能量项链,超人有一串能量项链，每棵能量珠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）,（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=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=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与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 ps=A pq B qr C rs我们知道矩阵相乘满足结合率，即(AB)C=A(BC)不同结合方法得到的结果是一样的，然而计算量却可能有很大差别。,是否让你吃惊？,如：A 505 B 5100 C 10010 按(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个矩阵A1,A2,An，其中Ai与A i+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少,矩阵连乘问题,穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：,矩阵连乘问题,穷举法动态规划,将矩阵连乘积 简记为Ai:j，这里ij,考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak-1和Ak之间将矩阵链断开，i kj，则其相应完全加括号方式为,计算量：的计算量加上 的计算量，再加上Ai:k-1和Ak:j相乘的计算量,关于计算量,如：A 10100 B 1005 C 550 D 50100 按(AB)(CD)计算，所需乘法次数为：1、计算AB 所需乘法次数：10100 5=50002、计算CD 所需乘法次数：550 100=250003、以上两个结果矩阵(AB)105和(CD)5100再相乘的乘法次数:105 100=5000故按(AB)(CD)计算，所需乘法次数为：5000+25000+5000=35000,规模为4的情况,如：A1510 A2104 A346 A4 610 请给出计算A1A2A3A4的最优计算次序1、计算规模为2的子问题计算A1A2 所需乘法次数：510 4=200计算A2A3 所需乘法次数：104 6=240计算A3A4所需乘法次数：4610=240,A1 510 A2 104 A3 46 A4 610 2、计算规模为3的子问题(1)计算A1A2A3所需乘法次数，有两种结合方法:(A1A2)A3和A1(A2A3),选最好的一种：,(A1A2)A3:计算量：320,(A1A2)A3:计算A1A2的计算量+计算A1:2乘A3的计算量：200+5 4 6=320A1(A2A3):计算BC的计算量+计算A1乘A2:3的计算量：240+5 10 6=540,A1 510 A2 104 A3 46 A4 610(2)计算A2A3A4所需乘法次数，有两种结合方法:(A2A3)A4和A2(A3A4)，选最好的一种：,计算A2A3的计算量+计算A2:3乘A4的计算量：240+10 6 10=840A2(A3A4):计算A3A4的计算量+计算A2乘A3:4的计算量：240+10 4 10=640,A2(A3A4):计算量：640,A1 510 A2 104 A3 46 A4 610 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=640A1(A2A3A4):640+5 10 10=1140,(A1A2A3)A4:计算量：620,用数组元素Cij来存储计算Ai:j的最少数乘次数,例7.1：A1 510 A2 104 A3 46 A4 610 请给出计算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 104 A3 46 A4 610 2、计算规模为3的子问题计算A1:3所需乘法次数，有两种结合方法，选最好的一种：(A1:2)A3:计算A1:2的计算量+计算（A1:2）乘A3的计算量：200+5 4 6=320A1(A2:3):计算A2:3的计算量+计算A1乘(A2:3)的计算量：240+5 10 6=540,C13=320,A1 510 A2 104 A3 46 A4 610 计算A2:4所需乘法次数，有两种结合方法，选最好的一种：840(A2:3)A4:计算A2:3的计算量+计算A2:3乘A4的计算量：240+10 6 10=840A2(A3:4):计算A3:4的计算量+计算A2乘(A3:4)的计算量：240+10 4 10=640,C24=640,A1 510 A2 104 A3 46 A4 610 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=640A1(A2:4):640+5 10 10=1140,C14=620,A1 510 A2 104 A3 46 A4 610,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),用动态规划法求最优解,void MatrixChain(int*p，int n，int*c，int*s)for(int i=1;i=n;i+)cii=0;/填充对角线d=0 for(int d=1;d=n-1;d+)/填充对角线d，,d=1,n-1 for(int i=1;i=n d;i+)填充对角线d上第i个元素 int j=i+d;/以下几行计算CIj cij=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(int k=i+2;k=j;k+)/从k(k=i+2,j)断开 int t=mik-1+mkj+pi-1*pk*pj;if(t mij)mij=t;sij=k;,讨论,有关数组的使用：1、一维数组的声明和指针的使用2、一维数组和指针作参数3、二维数组的声明和双重指针的使用,程序1：程序没有任何通用性,void LCSlength(int m,int n,char x,char y,int c7)main()char A8=0,A,B,C,B,D,A,B;char B7=0,A,B,A,B,D,C;int c87;LCSlength(7,6,A,B,c);,程序2（先开辟一个较大的存储空间）,#define N 100void LCSlength(int m,int n,char x,char y,int cN)main()char AN=0,A,B,C,B,D,A,B;char BN=0,A,B,A,B,D,C;int m=7,n=6,cNN;LCSlength(m,n,A,B,c);,程序3：用函数测出字符串的长度,#define N 100#include”stdio.h”void LCSlength(int m,int n,char x,char y,int cN)main()char AN=“0ABCBDAB”;char BN=“0ABABDC”;int cNN;int m=strlen(A),n=strlen(B);LCSlength(m,n,A,B,c);,程序4：字符串由用户输入,#define N 100void LCSlength(int m,int n,char x,char y,int cN)main()char AN,BN;int cNN;gets(A);gets(B);/cinA;cinB;int m=strlen(A),n=strlen(B);LCSlength(m,n,A,B,c);,程序5:动态分配存储空间(推荐）,#define N 100void LCSlength(int m,int n,char x,char y,int*c)main()char AN,BN;int*c;gets(A);gets(B);int m=strlen(A),n=strlen(B);c=new intm*n;LCSlength(m,n,A,B,c);,用ci*n+j来代替cij,程序6:双重指针1,#define N 100void LCSlength(int m,int n,char x,char y,int*c)main()char AN,BN;int*c;gets(A);gets(B);int m=strlen(A),n=strlen(B);c=new int*m;for(int i=0;im;i+)ci=new intn;LCSlength(m,n,A,B,c);,int*c;,c,1010,1050,2030,1050,1010,2030,for(int i=0;im;i+)ci=new intn;,c=new int*m;,程序7:双重指针2,#define N 100void LCSlength(int m,int n,char x,char y,int*c)main()char AN,BN;int*cN;gets(A);gets(B);int m=strlen(A),n=strlen(B);for(int i=0;im;i+)ci=new intn;LCSlength(m,n,A,B,c);,int*cN;与int(*c)N的区别,int*cN;c是一个数组，它有N个元素，每个元素都是一个指针，可存一个整型数据的地址。int(*c)N；c是一个指针变量，它不是指向某一个整型数据，它可以指向一个有N个元素组成的一行数据，也可以称它为行指针。,