动态的规划-矩阵链相乘

动态的规划-矩阵链相乘第一页，编辑于星期六：十三点三十七分。例如：项链有四个能量珠，能量数组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=184p1=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☓r

Cr☓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个完全加括号的矩阵连乘积和的乘积并加括号，即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+1…An)可以得到关于P(n)的递推式如下：第十二页，编辑于星期六：十三点三十七分。矩阵连乘问题穷举法动态规划将矩阵连乘积简记为A[i:j]，这里i≤j

考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak-1和Ak之间将矩阵链断开，i<k≤j，则其相应完全加括号方式为计算量：的计算量加上的计算量，再加上A[i:k-1]和A[k:j]相乘的计算量第十三页，编辑于星期六：十三点三十七分。关于计算量如：A

10☓100B100☓5

C5☓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☓4

A34☓6

A46☓10请给出计算A1A2A3A4的最优计算次序1、计算规模为2的子问题计算A1A2所需乘法次数：5☓10☓4=200计算A2A3所需乘法次数：10☓4☓6=240计算A3A4所需乘法次数：4☓6☓10=240第十五页，编辑于星期六：十三点三十七分。A1

5☓10A210☓4

A34☓6

A46☓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=540第十六页，编辑于星期六：十三点三十七分。A1

5☓10A210☓4

A34☓6

A46☓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=640

A2(A3A4):计算量：640第十七页，编辑于星期六：十三点三十七分。A1

5☓10A210☓4

A34☓6

A46☓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：A1

5☓10A210☓4

A34☓6

A46☓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]=240第十九页，编辑于星期六：十三点三十七分。A1

5☓10A210☓4

A34☓6

A46☓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]=320第二十页，编辑于星期六：十三点三十七分。A1

5☓10A210☓4

A34☓6

A46☓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]=640第二十一页，编辑于星期六：十三点三十七分。A1

5☓10A210☓4

A34☓6

A46☓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]=620第二十二页，编辑于星期六：十三点三十七分。A15☓10A210☓4

A34☓6

A46☓10

d=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当i<j时，需找到一个分割点k,在Ak前断开：(Ai…Ak-1)(Ak…Aj),使C[i,j]达到最小这里的维数为第二十六页，编辑于星期六：十三点三十七分。

的位置只有种可能可以递归地定义C[i,j]为：第二十七页，编辑于星期六：十三点三十七分。计算最优值对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。第二十八页，编辑于星期六：十三点三十七分。动态规划--自底向上进行计算

用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法第二十九页，编辑于星期六：十三点三十七分。课堂练习(1)请给出计算M1M2M3M4M5乘积所需的最少数乘次数（即C[1][5]）。（2）请给出一个括号化表达式，使在这种次序下达到乘法的次数最少。M1M2M3M4M54☓55☓33☓66☓44☓5p1=4,p1=5,p3=3,p4=6,p5=4,p6=5第三十页，编辑于星期六：十三点三十七分。C[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=5第三十一页，编辑于星期六：十三点三十七分。C[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=5第三十二页，编辑于星期六：十三点三十七分。C[1:1]=0C[1:2]=60C[1:3]=132k=3C[1:4]=180k=3C[2:2]=0C[2:3]=90C[2:4]=132k=3C[2:5]=207k=3C[3:3]=0C[3:4]=72C[3:5]=132k=5C[4:4]=0C[4:5]=120C[5:5]=0p1=4,p1=5,p3=3,p4=6,p5=4,p6=5C[1:5]=252k=3第三十三页，编辑于星期六：十三点三十七分。C[1:1]=0C[1:2]=60C[1:3]=132k=3C[1:4]=180k=3C[1:5]=252k=3C[2:2]=0C[2:3]=90C[2:4]=132k=3C[2:5]=207k=3C[3:3]=0C[3:4]=72C[3:5]=132k=5C[4:4]=0C[4:5]=120C[5:5]=0最优计算次序：(M1M2)((M3M4)M5)第三十四页，编辑于星期六：十三点三十七分。用动态规划法求最优解voidMatrixChain(int*p，intn，int**c，int**s){for(inti=1;i<=n;i++)c[i][i]=0;//填充对角线d=0for(intd=1;d<=n-1;d++)//填充对角线d，,d=1,…n-1for(inti=1;i<=n–d;i++){填充对角线d上第i个元素intj=i+d;//以下几行计算C[I][j]

c[i][j]=Max;for(k=i+1,k<=j;k++){c[i][j]=min{c[i][j],c[i][k-1]+c[k][j]+r[i]r[k]r[j]);s[i][j]=使c[I][j]达到最小的k;｝}}m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//从i+1位置断开s[i][j]=i+1;for(intk=i+2;k<=j;k++){//从k(k=i+2,…j)断开intt=m[i][k-1]+m[k][j]+p[i-1]*p[k]*p[j];if(t<m[i][j]){m[i][j]=t;s[i][j]=k;}}}第三十五页，编辑于星期六：十三点三十七分。讨论有关数组的使用：1、一维数组的声明和指针的使用2、一维数组和指针作参数3、二维数组的声明和双重指针的使用第三十六页，编辑于星期六：十三点三十七分。程序1：程序没有任何通用性voidLCSlength(intm,intn,charx[],chary[],intc[][7]){……}main(){charA[8]={'0','A','B','C','B','D','A','B'};charB[7]={'0','A','B','A','B','D',‘C'};intc[8][7];LCSlength(7,6,A,B,c);}第三十七页，编辑于星期六：十三点三十七分。程序2（先开辟一个较大的存储空间）#defineN100voidLCSlength(intm,intn,charx[],chary[],intc[][N]){……}main(){charA[N]={'0','A','B','C','B','D','A','B'};charB[N]={'0','A','B','A','B','D',‘C'};

intm=7,n=6,c[N][N];LCSlength(m,n,A,B,c);}第三十八页，编辑于星期六：十三点三十七分。程序3：用函数测出字符串的长度#defineN100#include”stdio.h”voidLCSlength(intm,intn,charx[],chary[],intc[][N]){……}main(){charA[N]=“0ABCBDAB”;charB[N]=“0ABABDC”;intc[N][N];

intm=strlen(A),n=strlen(B);LCSlength(m,n,A,B,c);}第三十九页，编辑于星期六：十三点三十七分。程序4：字符串由用户输入#defineN100voidLCSlength(intm,intn,charx[],chary[],intc[][N]){……}main(){charA[N],B[N];intc[N][N];

gets(A);gets(B);//cin>>A;cin>>B;intm=strlen(A),n=strlen(B);LCSlength(m,n,A,B,c);}第四十页，编辑于星期六：十三点三十七分。程序5:动态分配存储空间(推荐）#defineN100voidLCSlength(intm,intn,charx[],chary[],int*c){……}main(){charA[N],B[N];int*c;gets(A);get