《算法设计与分析》第07章.ppt

《《算法设计与分析》第07章.ppt》由会员分享，可在线阅读，更多相关《《算法设计与分析》第07章.ppt（122页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第7章章动态规划法动态规划法 7.17.1一般方法和基本要素一般方法和基本要素一般方法和基本要素一般方法和基本要素7.27.2每对结点间的最短路径每对结点间的最短路径每对结点间的最短路径每对结点间的最短路径 7.37.3矩阵连乘矩阵连乘矩阵连乘矩阵连乘 7.47.4最长公共子序列最长公共子序列最长公共子序列最长公共子序列7.57.5最优二叉搜索树最优二叉搜索树最优二叉搜索树最优二叉搜索树 7.60/17.60/1背包背包背包背包 7.77.7流水作业调度流水作业调度流水作业调度流水作业调度 7.1一般方法和基本要素一般方法和基本要素 动动动动态态态态规规规规划划划划法法法法的的实实质质也也是

2、是将将较较大大问问题题分分解解为为较较小小的的同同类类子子问问题题，这这一一点点上上它它与与分分治治法法和和贪贪心心法法类类似似。但但动动态态规规划划法法有有自自己己的的特特点点。分分治治法法的的子子问问题题相相互互独独立立，相相同同的的子子问问题题被被重重复复计计算算，动动态态规规划划法法解解决决这这种种种种子子子子问问问问题题题题重重重重叠叠叠叠现现现现象象象象。贪贪心心法法要要求求针针对对问问题题设设计计最最优优量量度度标标准准，但但这这在在很很多多情情况况下下并并不不容容易易。动动动动态态态态规规规规划划划划法法法法利利利利用用用用最最最最优优优优子子子子结结结结构构构构，自自自自底底

3、底底向向向向上上上上从从从从子子子子问问问问题题题题的的的的最最最最优优优优解解解解逐逐逐逐步步步步构构构构造造造造出出出出整整整整个个个个问问问问题题题题的的的的最最最最优优优优解解解解，动动态态规规划划则则可可以以处处理理不不具具备备贪贪心心准准则则的问题。的问题。引例：引例：Fibonacci数（数列）的计算其定义为其定义为F0=0,F1=1,Fn=Fn-1+Fn-2 (n2)计算此数列可由递归函数完成计算此数列可由递归函数完成 intint fibo(intfibo(int n)n)intint f;f;if(n2)f=n;if(n2)f=n;else f=fibo(n-1)+fibo

4、(n-2);else f=fibo(n-1)+fibo(n-2);return f;return f;当当n=6n=6时，函数时，函数fibofibo()()的调用过程的调用过程65443323221211021101033101012345678910111213141516171819202122232425 改进：改进：intfibo(intn)intinti,f,f0,f1;i,f,f0,f1;f0=0;f1=1;f0=0;f1=1;for(i=2;i=for(i=2;i=n;in;i+)+)f=f0+f1;f0=f1;f1=f;f=f0+f1;f0=f1;f1=f;returnf;r

5、eturnf;关键：避免了重复计算，时间代价关键：避免了重复计算，时间代价关键：避免了重复计算，时间代价关键：避免了重复计算，时间代价O(n)O(n)与贪心算法的比较与贪心算法的比较贪心算法：局部的最优性依赖于其前面各部分是贪心算法：局部的最优性依赖于其前面各部分是贪心算法：局部的最优性依赖于其前面各部分是贪心算法：局部的最优性依赖于其前面各部分是否最优；且不能保证最终解的最优性。否最优；且不能保证最终解的最优性。否最优；且不能保证最终解的最优性。否最优；且不能保证最终解的最优性。动态规划：当前决策的最优性取决于其后续决策动态规划：当前决策的最优性取决于其后续决策动态规划：当前决策的最优性取决

6、于其后续决策动态规划：当前决策的最优性取决于其后续决策系列的是否最优。动态规划方法可以保证问题求系列的是否最优。动态规划方法可以保证问题求系列的是否最优。动态规划方法可以保证问题求系列的是否最优。动态规划方法可以保证问题求解是全局最优的。解是全局最优的。解是全局最优的。解是全局最优的。生活中的实例生活中的实例生活中的实例生活中的实例.如如如如:立志十年达到人生某一目标立志十年达到人生某一目标立志十年达到人生某一目标立志十年达到人生某一目标.分析现状分析现状,制定长期与短期愿景制定长期与短期愿景.贪心策略贪心策略:动态规划策略动态规划策略:当前当前2年年810年年24年年610年年46年年410

7、年年68年年210年年810年年当前当前10年年 设设计计一一个个动动态态规规划划算算法法，通通常常可可以以按按以以下下几几个个步步骤进行：骤进行：（1 1）刻画最优解的结构特性；）刻画最优解的结构特性；（2 2）递归定义最优解值；）递归定义最优解值；（3 3）以自底向上方式计算最优解值；）以自底向上方式计算最优解值；（4 4）根据计算）根据计算得到的信息得到的信息构造一个最优解。构造一个最优解。其中，第（其中，第（1 1）至（）至（3 3）步是）步是动态规动态规划算法的基本划算法的基本步步骤骤。最。最优优解解值值是最是最优优解的目解的目标标函数的函数的值值。7.1动态规划算法的基本要素：一个

8、最优化多步决策问题适合用动态规划法求一个最优化多步决策问题适合用动态规划法求解有两个要素：解有两个要素：最优子结构特性和重叠子问题。最优子结构特性和重叠子问题。最优子结构特性和重叠子问题。最优子结构特性和重叠子问题。最优性原理最优性原理最优性原理最优性原理指出，一个问题的最优解包括了子问指出，一个问题的最优解包括了子问题的最优解时，则称该问题具有题的最优解时，则称该问题具有最优子结构特性。最优子结构特性。最优子结构特性。最优子结构特性。最优子结构特性最优子结构特性最优子结构特性最优子结构特性从较小子问题的解构造较大问题从较小子问题的解构造较大问题的最优解时只需考虑小问题的最优解。的最优解时只需

9、考虑小问题的最优解。子结构重叠性质：子结构重叠性质：子结构重叠性质：子结构重叠性质：递归算法求解问题时，每次产生递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。次。这种性质称为子问题的重叠性质。动态规划算法，动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。时间查看一下结果。通常不同的子问题个数随问题的通常不同的子问题个数随问

10、题的大小呈多项式增长。因此用动态规划算法只需要多项大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。式时间，从而获得较高的解题效率。7.1.3多段图问题多段图问题例例例例7 711多段图多段图G=(V,E)是一个带权有向图，它具有如下是一个带权有向图，它具有如下特性：图中的结点被划分成特性：图中的结点被划分成k 2个互不相交的子集个互不相交的子集Vi，1 i k。其中其中V1和和Vk分别只有一个结点，分别只有一个结点，V1包含源点包含源点（source）s，Vk包含汇点（包含汇点（sink）t。对所有边对所有边 E，多段图要求若多段图要求若u Vi，则，则v Vi1

11、，1 ik，每条边的权每条边的权值为值为c(u,v)。从从s s到到t t的路径长度是这条路径上边的权值之和，的路径长度是这条路径上边的权值之和，多段多段多段多段图问题图问题图问题图问题（multistage graph problemmultistage graph problem）是求从）是求从s s到到t t的的一条长度最短的路径。一条长度最短的路径。多段图的最优子结构多段图的最优子结构假定（假定（s,v2,v3vk-1,t)是一条从是一条从s到到t的最短路的最短路径，那么（径，那么（v2,v3vk-1,t)一定是从一定是从v2到到t的一条的一条最短路径。最短路径。多段图的向前递推关系多

12、段图的向前递推关系动态规划法每一步的决策依赖于子问题的解。在动态规划法每一步的决策依赖于子问题的解。在多段图中，一个阶段的决策与后面所要求解的子问多段图中，一个阶段的决策与后面所要求解的子问题相关，所以不能直接在某个阶段做出决定。题相关，所以不能直接在某个阶段做出决定。根据根据最优子结构特性最优子结构特性，我们可以从最后阶段开始，我们可以从最后阶段开始采用逐步向前递推的方法，由子问题的最优解计算采用逐步向前递推的方法，由子问题的最优解计算原问题的最优解。原问题的最优解。递推关系递推关系:cost(i,jcost(i,j):):从从从从i i阶段阶段阶段阶段j j结点到结点到结点到结点到t t的

13、最短路径长度，的最短路径长度，的最短路径长度，的最短路径长度，i i是阶段编号，是阶段编号，是阶段编号，是阶段编号，j j是是是是i i阶段中的结点编号，阶段中的结点编号，阶段中的结点编号，阶段中的结点编号，cost(k,tcost(k,t)=0)=0cost(i,jcost(i,j)=minc(j,p)+cost(i+1,p)=minc(j,p)+cost(i+1,p)j jV Vi i，p pV Vi+1i+1，E E例如例如例如例如:cost(2,1)=minc(1,5)+cost(3,5),:cost(2,1)=minc(1,5)+cost(3,5),c(1,6)+cost(3,6),

14、c(1,6)+cost(3,6),c(1,7)+cost(3,7)c(1,7)+cost(3,7)cost(5,11)=0,cost(5,11)=0,cost(4,10)=5,d(10)=11,cost(4,9)=2,d(9)=11,cost(4,8)=4,d(8)=11cost(4,10)=5,d(10)=11,cost(4,9)=2,d(9)=11,cost(4,8)=4,d(8)=11cost(3,7)=min6+cost(4,10)cost(3,7)=min6+cost(4,10)，5+cost(4,9)=7,d(7)=95+cost(4,9)=7,d(7)=9cost(3,6)=5,

15、d(6)=9,cost(3,5)=7,d(5)=9cost(3,6)=5,d(6)=9,cost(3,5)=7,d(5)=9cost(2,1)=min4+cost(3,5)cost(2,1)=min4+cost(3,5)，2+cost(3,6),1+cost(3,7)=7,d(1)=62+cost(3,6),1+cost(3,7)=7,d(1)=6cost(2,2)=min2+cost(3,5)cost(2,2)=min2+cost(3,5)，7+cost(3,6)=9,d(2)=57+cost(3,6)=9,d(2)=5cost(2,3)=min11+cost(3,7)=18,d(3)=7c

16、ost(2,3)=min11+cost(3,7)=18,d(3)=7cost(2,4)=min11+cost(3,6)cost(2,4)=min11+cost(3,6)，8+cost(3,7)=15,d(4)=78+cost(3,7)=15,d(4)=7cost(1,0)=min9+cost(2,1),7+cost(2,2),3+cost(2,3),cost(1,0)=min9+cost(2,1),7+cost(2,2),3+cost(2,3),2+cost(2,4)=16,d(0)=12+cost(2,4)=16,d(0)=1p(0)=0,p(k-1)=n-1=11,p(1)=d(p(0)=

17、d(0)=1;p(2)=d(p(1)=d(1)=6;p(3)=d(p(2)=d(6)=9;最短路径最短路径:(0,1,6,9,11)。一般。一般:p(i)=d(p(i-1)d(jd(j):):表示从结点表示从结点j j到终点的最到终点的最短路径上短路径上j j后的下一个结点。后的下一个结点。p(0)p(k-1):p(0)p(k-1):表示从源点表示从源点s s到到终点终点t t的最短路径上的结点。的最短路径上的结点。重叠子问题重叠子问题重叠子问题重叠子问题:cost(i,jcost(i,j)可能被反复计算。可能被反复计算。可能被反复计算。可能被反复计算。0 0 0 0 0 0 0 01 1 1

18、 12 2 2 24 4 4 45 5 5 53 3 3 3图的邻接表结构图的邻接表结构1 1 1 1 6 6 6 62 2 2 2 1 1 1 13 3 3 3 5 5 5 5 0 0 0 0 6 6 6 62 2 2 2 5 5 5 54 4 4 4 3 3 3 3 0 0 0 0 5 5 5 52 2 2 2 5 5 5 55 5 5 5 2 2 2 2 1 1 1 1 3 3 3 32 2 2 2 6 6 6 65 5 5 5 6 6 6 6 0 0 0 0 1 1 1 11 1 1 1 5 5 5 53 3 3 3 5 5 5 54 4 4 4 6 6 6 6 5 5 5 5 4 4

19、 4 42 2 2 2 4 4 4 43 3 3 3 2 2 2 24 4 4 4 6 6 6 6 0 0 0 01 1 1 12 2 2 23 3 3 34 4 4 45 5 5 5 【程序程序程序程序7 71 1】多段图的向前递推算法多段图的向前递推算法多段图的向前递推算法多段图的向前递推算法templatevoidGraph:FMultiGraph(intk,int*p)/采用程序采用程序68的邻接表存储图的邻接表存储图G。float*cost=newfloatn;intq,*d=newintn;costn-1=0,dn-1=-1;/设置向前递推的初值设置向前递推的初值cost(j)表示

20、从结点表示从结点j到终点到终点t的最短路径的最短路径d(j):表示从结点表示从结点j到终点的最短路径上到终点的最短路径上j后的下一个结点。后的下一个结点。p(0)p(k-1):表示从源点表示从源点s到终点到终点t的最短路径上的结点。的最短路径上的结点。for(for(intint j=n-2;j=0;j-)j=n-2;j=0;j-)/按按n n-2,0-2,0的次序计算的次序计算costcost和和d d float min=INFTY;/float min=INFTY;/计算最小值为计算最小值为costcostj j for(for(ENodeENode*r=*r=ajaj;r;r=r-;r

21、;r=r-nextArcnextArc)intint v=r-v=r-adjVexadjVex;if(r-if(r-w+costvw+costvw+costvw+costv;q=v;q=v;costjcostj=min;=min;djdj=q;/qq;/q是是j j在最短子路径上的后继结点在最短子路径上的后继结点 p0=0;pk-1=n-1;c=cost0;p0=0;pk-1=n-1;c=cost0;/p0/p0和和pn-1pn-1是源点和汇点是源点和汇点 for(jfor(j=1;j=k-2;j+)=1;j=k-2;j+)pjpj=dpj-1;=dpj-1;/pipi 是最短路径上第是最短路

22、径上第i i阶段的结点阶段的结点 delete cost;delete d;return c;delete cost;delete d;return c;7.1.4资源分配问题资源分配问题【例例例例7 72 2】将将n个个资资源源分分配配给给r个个项项目目，已已知知如如果果把把j个个资资源源分分配配给给第第i个个项项目目，可可以以收收益益N(i,j)，0 j n，1 i r。求总收益最大的资源分配方案。求总收益最大的资源分配方案。动态规划算法的基本要素：一个最优化多步决策问题适合用动态规划法求一个最优化多步决策问题适合用动态规划法求解有两个要素：解有两个要素：最优子结构特性和重叠子问题。最优子

23、结构特性和重叠子问题。最优子结构特性和重叠子问题。最优子结构特性和重叠子问题。最优性原理最优性原理最优性原理最优性原理指出，一个问题的最优解包括了子问指出，一个问题的最优解包括了子问题的最优解时，则称该问题具有题的最优解时，则称该问题具有最优子结构特性。最优子结构特性。最优子结构特性。最优子结构特性。最优子结构特性最优子结构特性最优子结构特性最优子结构特性从较小子问题的解构造较大问题从较小子问题的解构造较大问题的最优解时只需考虑小问题的最优解。的最优解时只需考虑小问题的最优解。设设计计一一个个动动态态规规划划算算法法，通通常常可可以以按按以以下下几几个个步步骤进行：骤进行：（1 1）刻画最优解

24、的结构特性；）刻画最优解的结构特性；（2 2）递归定义最优解值；）递归定义最优解值；（3 3）以自底向上方式计算最优解值；）以自底向上方式计算最优解值；（4 4）根据计算）根据计算得到的信息得到的信息构造一个最优解。构造一个最优解。其中，第（其中，第（1 1）至（）至（3 3）步是）步是动态规动态规划算法的基本划算法的基本步步骤骤。最。最优优解解值值是最是最优优解的目解的目标标函数的函数的值值。7.2每对结点间的最短路径每对结点间的最短路径 7.2.1问题描述问题描述设设G=(V,E)G=(V,E)是是一一个个有有n n个个结结点点的的带带权权有有向向图图，w(i,j)w(i,j)是是权权函数

25、，函数，每每对对结结点点间间的的最最短短路路径径问问题题是是指指求求图图中中任任意一意一对结对结点点i i和和j j之之间间的最短路径。的最短路径。7.2.2动态规划法求解动态规划法求解最优子结构最优子结构最优子结构最优子结构设设图图G=(V,E)是是带带权权有有向向图图，(i,j)是是从从结结点点i到到结结点点j的的最短路径长度。最短路径长度。（1）如如果果k是是这这条条路路径径上上的的一一个个结结点点，(i,k)和和(k,j)分分别别是是从从i到到k和和从从k到到j的的最最短短路路径径长长度度，则则必必有有(i,j)=(i,k)+(k,j)。因因为为若若不不然然，则则(i,j)代代表表的的

26、路路径径就就不是最短路径。不是最短路径。7.2.2动态规划法求解动态规划法求解最优子结构最优子结构最优子结构最优子结构（2）如如果果k不不是是这这条条路路径径上上的的一一个个结结点点，(i,j)就就是是不不包包括括k这这个个结结点点的的子子图图中中i与与j之之间间的的最最短短路路径径。这这表表明明每每对对结结点点之之间间的的最最短短路路径径问问题题的的最最优优解解具具有有最最优优子子结结构构特特性。性。最优解的递推关系最优解的递推关系最优解的递推关系最优解的递推关系设设d dn-1n-1ijij表示在从结点表示在从结点i i到到j j的路径上只允许包含结点的路径上只允许包含结点编号不大于编号不

27、大于n-1n-1的结点时，所有可能路径中的最短路径的的结点时，所有可能路径中的最短路径的长度。长度。（1 1）如果编号为）如果编号为n-1n-1的节点不在最短路径上，那么：的节点不在最短路径上，那么：d dn-1n-1ij=dij=dn-2n-2ij ij（2 2）如果编号为）如果编号为n-1n-1的节点在最短路径上，那么：的节点在最短路径上，那么：d dn-1n-1ij=dij=dn-2n-2in-1+din-1+dn-2n-2n-1jn-1j所以：所以：d dn-1n-1ij=mindij=mindn-2n-2ij,ij,d dn-2n-2in-1+din-1+dn-2n-1jn-1j 一

28、般地一般地一般地一般地设设d dk kijij 为从为从i i到到j j的只以的只以(0-k)(0-k)集合中的节点为中集合中的节点为中间结点的最短路径的长度。间结点的最短路径的长度。重叠子问题重叠子问题重叠子问题重叠子问题：为了计算：为了计算：为了计算：为了计算d dk kijij 时，必须先计算时，必须先计算时，必须先计算时，必须先计算d dk k1 1ijij、d dk k1 1ikik和和和和d dk k1 1kjkj，d dk k 1 1的元素的元素的元素的元素被多个被多个被多个被多个d dk k的元素的计算共享。的元素的计算共享。的元素的计算共享。的元素的计算共享。7.2.3弗洛伊

29、德算法弗洛伊德算法第第一一步，步，所有的所有的d-1ij=wij；第第二二步，步，在当前在当前i到到j的最短路径中的最短路径中加入中间顶点加入中间顶点0，取，取dij与与di0+d0j中较小的值作中较小的值作dij的值，完成后得到的值，完成后得到d0ij；第第三三步，步，在当前在当前i到到j的最短路径中的最短路径中加入中间顶点加入中间顶点1，取，取dij与与di1+d1j中较小的值，完成后得到中较小的值，完成后得到d1ij，如此进行下去，如此进行下去，当第当第n步完成后，得到步完成后，得到dn-1ij，dn-1ij表示顶点表示顶点i到顶点到顶点j的的最短距离。最短距离。记录记录i到到j的最短路

30、径的最短路径pathij：结点：结点i到到j的最短路径上的最短路径上j之前的结点；之前的结点；通过对通过对path数组的反向追溯，可得到结点数组的反向追溯，可得到结点i到到j的最短路的最短路径。径。例如：结点例如：结点2到到3的最短路径可以这样确定：的最短路径可以这样确定：path23=1，path21=0，path20=2所以最短路径是所以最短路径是2，0，1，3 pathijpathijpathijpathij=-1-1-1-1 若若若若i=ji=ji=ji=j-1-1-1-1 若若若若 EEEEi i i i 若若若若 EEEE1.1.初始化初始化 【程序程序程序程序7 72 2】弗洛伊

31、德算法弗洛伊德算法弗洛伊德算法弗洛伊德算法templatevoidMGraph:Floyd(T*&d,int*&path)inti,j,k;d=newT*n;path=newint*n;for(i=0;in;i+)di=newTn;pathi=newintn;for(j=0;jn;j+)dij=aij;if(i!=j&dijINFTY)pathij=i;elsepathij=-1;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jn;j+)if(dik+dkjdij)dij=dik+dkj;pathij=pathkj;弗洛伊德算法的时间复杂度为弗洛伊德算法的时间复杂度为

32、弗洛伊德算法的时间复杂度为弗洛伊德算法的时间复杂度为O(nO(nO(nO(n3 3 3 3)7.2.4 算法正确性算法正确性 定理定理定理定理7 71 1弗弗洛洛伊伊德德算算法法得得到到的的dij，0 i,j n-1是是从从i到到j的最短路径。的最短路径。7.3矩阵连乘矩阵连乘 7.3.1问题描述问题描述设设设设给定矩阵为：给定矩阵为：给定矩阵为：给定矩阵为：=(=(a aij ij)nmnm,B,B=(=(b bij ij)mkmk,C,C=(=(c cij ij)k krr计算：计算：计算：计算：D D(AB)C(AB)CA(BC)A(BC)两次计算所需乘法运算次数分别为：两次计算所需乘法

33、运算次数分别为：两次计算所需乘法运算次数分别为：两次计算所需乘法运算次数分别为：nmk+nkrmkr+nmr运算结果相同，但进行的运算次数却差距很大。运算结果相同，但进行的运算次数却差距很大。运算结果相同，但进行的运算次数却差距很大。运算结果相同，但进行的运算次数却差距很大。如如如如:n=10,m=100,k=5,r=50.:n=10,m=100,k=5,r=50.则有：则有：则有：则有：nmk+nkr=7500mkr+nmr=75000 计算矩阵连乘积A=A1*A2*A3*A4*A5*A6，各矩阵的维数分别为：A1:30*1A1:30*1；A2:1*40A2:1*40A3:40*10A3:4

34、0*10；A4:10*25A4:10*25矩阵相乘满足结合律。运算次数计算如下：矩阵相乘满足结合律。运算次数计算如下：矩阵相乘满足结合律。运算次数计算如下：矩阵相乘满足结合律。运算次数计算如下：(A1A2)A3)A4:20700(A1A2)A3)A4:20700(A1A2)(A3A4):41200(A1A2)(A3A4):41200(A1(A2A3)A4):8200(A1(A2A3)A4):8200A1(A2A3)A4):1400A1(A2A3)A4):1400A1(A2(A3A4):11750A1(A2(A3A4):11750分析分析运算运算次数次数与结与结果。果。给给定定n个个矩矩阵阵A0

35、,A1,An1，其其中中Ai，i=0,n-1的的维维数数为为pi pi+1，并并且且Ai与与Ai+1是是可可乘乘的的。考考察察这这n个个矩矩阵阵的的连连乘乘积积A0A1An 1，由由于于矩矩阵阵乘乘法法满满足足结结合合律律，所所以以计计算算矩矩阵阵的的连连乘乘可可有有许许多多不不同同的的计计算算次次序序。矩矩阵阵连连乘乘问问题题是是确确定定计计算算矩矩阵阵连连乘乘积积的的计计算算次次序序，使使得得按按照照这这一一次次序序计计算算矩矩阵阵连连乘乘积积，需需要要的的“数乘数乘”次数最少。次数最少。一般描述一般描述 (A1A2)A3)A4)(A1A2)A3)A4)完全加括号完全加括号的矩阵连乘积可递

36、归地定义为：的矩阵连乘积可递归地定义为：单个矩阵是完全加括号的；单个矩阵是完全加括号的；矩矩阵阵连连乘乘积积A是是完完全全加加括括号号的的，则则A可可表表示示为为两两个个完完全全加加括括号号的的矩矩阵阵连连乘乘积积B和和C的的乘乘积积并并加加括括号号，即即A=(BC)。例例例例7 74 44个个矩矩阵阵连连乘乘积积ABCD，设设它它们们的的维维数数分分别别为为A:50 10，B:10 40,C:40 30,D:30 5。穷举搜索可以确定最优连乘积次序，但矩阵穷举搜索可以确定最优连乘积次序，但矩阵结合次序方法数随矩阵数量的增长呈指数级结合次序方法数随矩阵数量的增长呈指数级增长。显然不是有效算法。

37、增长。显然不是有效算法。满足最优子结构、满足子结构重叠性质，可满足最优子结构、满足子结构重叠性质，可以采用动态规划求的最优解以采用动态规划求的最优解 7.3.2动态规划法求解动态规划法求解 最优子结构最优子结构最优子结构最优子结构矩阵连乘矩阵连乘AiAi+1Aj简记为简记为Ai:j，i j。于是矩阵连于是矩阵连乘乘A0A1An-1可记作可记作A0:n-1。将这一计算次序在矩阵。将这一计算次序在矩阵Ak和和Ak+1，0 kn-1之间断开，则其相应的完全加括之间断开，则其相应的完全加括号形式为（号形式为（A0A1Ak）（）（Ak+1Ak+2An 1）。）。可可先分别计算先分别计算A0:k和和Ak+

38、1:n-1，然后将两个连乘积然后将两个连乘积再相乘得到再相乘得到A0:n-1。（A0A1Ak）（）（Ak+1Ak+2An 1）l矩矩阵阵连连乘乘A0:n-1的的最最优优计计算算次次序序的的计计算算量量等等于于A0:k和和Ak+1:n-1两两者者的的最最优优计计算算次次序序的的计计算算量量之之和和，再再加加上上A0:k和和Ak+1:n-1相相乘乘的的计计算算量量。如如果果两两个个矩矩阵阵子子序序列列的的计计算算次次序序不不是是最最优优的的，则则原原矩矩阵阵的的计计算算次次序序也也不不可可能能是是最最优优的的。这这就就是是说说，矩矩阵阵连连乘乘问问题的最优解具有最优子结构特性。题的最优解具有最优子

39、结构特性。最优解的递推关系最优解的递推关系最优解的递推关系最优解的递推关系先先定定义义一一个个二二维维数数组组m m，用用来来保保存存矩矩阵阵连连乘乘时时所所需需的的最最少计算量。少计算量。mijmij 表示表示A Ai iA Ai+1i+1A Aj j最少计算量最少计算量其中其中pi i表示矩阵的行列数，表示矩阵的行列数，Ai是是p pi ip pi i+1+1的矩阵。的矩阵。重叠子问题重叠子问题重叠子问题重叠子问题：许多子问题被重复计算。：许多子问题被重复计算。：许多子问题被重复计算。：许多子问题被重复计算。k此时并未确定，需要从此时并未确定，需要从i到到j-1遍历以寻找一个最小的遍历以寻

40、找一个最小的mij。我们把这个最小的。我们把这个最小的k放在放在sij。例例例例7 75 56个个矩矩阵阵连连乘乘积积A0A1A2A3A4A5，设设它它们们的的维维数数分分别别为为A:30 35，B:35 15C:15 5D:5 10，E:10 20，F:20 25。A0:30 35，A1:35 15,A2:15 5,A3:5 10，A4:10 20，A5:20 25。1 1、给给给给 miimii置初值；置初值；置初值；置初值；(i=0,1,2,3,4,5)(i=0,1,2,3,4,5)siisii|i=0,1,2,3,4,5=(0,0,0,0,0,0)|i=0,1,2,3,4,5=(0,0

41、,0,0,0,0)2 2、计算、计算、计算、计算mii+1mii+1；sii+1(i=0,1,2,3,4)sii+1(i=0,1,2,3,4)3 3、计算、计算、计算、计算mii+2mii+2；(i=0,1,2,3)(i=0,1,2,3)A A0 0:30:30 3535，A A1 1:35:35 15A15A2 2:15:15 5A5A3 3:5:5 1010，A A4 4:10:10 2020，A A5 5:20:20 2525。m02=minm00+m12+pm02=minm00+m12+p0 0p p1 1p p3 3=0+2625+30*35*5=7875;=0+2625+30*35

42、*5=7875;m01+m22+pm01+m22+p0 0p p2 2p p3 3=15750+0+30*15*5=15750+0+30*15*5s02=0s02=0 4、计算、计算mii+3；(i=0,1,2)m03=minm00+m13+p0p1p4=0+4375+30*35*10=14875;m03=minm00+m13+p0p1p4=0+4375+30*35*10=14875;m03=minm00+m13+p0p1p4=0+4375+30*35*10=14875;m03=minm00+m13+p0p1p4=0+4375+30*35*10=14875;m01+m23+p0p2p4=157

43、50+750+30*15*10;m01+m23+p0p2p4=15750+750+30*15*10;m01+m23+p0p2p4=15750+750+30*15*10;m01+m23+p0p2p4=15750+750+30*15*10;m02+m33+p0p3p4=7875+0+30*5*10=9375;m02+m33+p0p3p4=7875+0+30*5*10=9375;m02+m33+p0p3p4=7875+0+30*5*10=9375;m02+m33+p0p3p4=7875+0+30*5*10=9375;s03=2s03=2s03=2s03=2 5 5、计算、计算mii+4mii+4；(

44、i=0,1)(i=0,1)6 6、计算、计算m05m05；得出最优分段位置得出最优分段位置sijsij ，从而得到最优连乘积序列，从而得到最优连乘积序列A0,n-1=(A0(A1A2)(A3A4)A5)因：s0,5=2，s0,2=0，s3,5=4所以有：A=A1*A2*A3*A4*A5*A6=(A0*A1*A2)*(A3*A4*A5)=(A0*(A1*A2)*(A3*A4)*A5)此序列为最佳序列，所需乘积次数为15125次。7.3.3矩阵连乘算法矩阵连乘算法classMatrixChainpublic:MatrixChain(intmSize,int*q);/创建数组创建数组m和和s，一维，

45、一维数组数组p，并初始化，并初始化intMChain();/一般动态规划法求最优解值一般动态规划法求最优解值intLookupChain();/备忘录方法求最优解值备忘录方法求最优解值voidTraceback();/构造最优解的公有函数构造最优解的公有函数private:voidTraceback(inti,intj);/构造最优解的私有递归函数构造最优解的私有递归函数intLookupChain(inti,intj);/备忘录方法私有递归备忘录方法私有递归int*p,*m,*s,n;intint MatrixChain:MChainMatrixChain:MChain()()/求求A0:n

46、-1A0:n-1的最优解值的最优解值 for(for(intint i=0;in;i+)i=0;in;i+)miimii=0;=0;for(for(intint r=1;rn;r+)r=1;rn;r+)for(for(intint i=0;i i=0;in-rn-r;i+);i+)intint j=j=i+ri+r;mijmij=mii+mi+1j+pi*pi+1*pj+1;/mij=mii+mi+1j+pi*pi+1*pj+1;/mij的初值的初值 sijsij=i;=i;for(for(intint k=i+1;kj;k+)k=i+1;kj;k+)intint t=mik+mk+1j+pi

47、*pk+1*pj+1;t=mik+mk+1j+pi*pk+1*pj+1;if(tif(tmijmij)mijmij=t;=t;sijsij=k;=k;return m0n-1;return m0n-1;voidMatrixChain:Traceback(inti,intj)if(i=j)coutAi;return;if(isij)cout(;Traceback(i,sij);if(isij)cout);if(sij+1j)cout(;Traceback(sij+1,j);if(sij+1j)cout);voidMatrixChain:Traceback()cout(;Traceback(0,n

48、-1);cout);coutendl;算法评估:三重循环，O(n3)，占用一定的空间，与穷举法相比，效率大幅度提高。7.3.4备忘录方法备忘录方法 矩阵连乘的备忘录方法矩阵连乘的备忘录方法矩阵连乘的备忘录方法矩阵连乘的备忘录方法 备忘录方法为每个已经计算的子问题建立备忘录，备忘录方法为每个已经计算的子问题建立备忘录，即保存子问题的计算结果以备需要时引用，从而即保存子问题的计算结果以备需要时引用，从而避免了相同子问题的重复求解。避免了相同子问题的重复求解。Fibonacci数（数列）的计算其定义为其定义为F0=0,F1=1,Fn=Fn-1+Fn-2 (n2)计算此数列可由递归函数完成计算此数列可

49、由递归函数完成 intint fibo(intfibo(int n)n)intint f;f;if(n2)f=n;if(n2)f=n;else f=fibo(n-1)+fibo(n-2);else f=fibo(n-1)+fibo(n-2);return f;return f;当当n=6n=6时，函数时，函数fibofibo()()的调用过程的调用过程65443323221211021101033101012345678910111213141516171819202122232425 改进：改进：intfibo(intn)intinti,f,f0=0,f1=1;i,f,f0=0,f1=1;f

50、or(i=2;i=n;i+)for(i=2;i0)returnmij;if(i=j)return0;intu=LookupChain(i,i)+LookupChain(i+1,j)+pi*pi+1*pj+1;sij=i;for(intk=i+1;kj;k+)intt=LookupChain(i,k)+LookupChain(k+1,j)+pi*pk+1*pj+1;if(tu)u=t;sij=k;mij=u;returnu;A0*A1*A2*A3*A4*A5 intMatrixChain:LookupChain()returnLookupChain(0,n-1);7.5 最优二叉搜索树最优二叉搜