算法与设计：动态规划法.ppt

算法设计与分析,广东白云学院 计算机科学系2010-2011学年 第2学期,第3章 动态规划法,本 章 目 录,返回,3.1 概 述,3.2 图问题中的动态规划法,3.3 组合问题中的动态规划法,3.4 查找问题中的动态规划法,3.1 概 述,3.1.2 最优化问题,3.1.3 最优性原理,3.1.4 动态规划法的设计思想,返回,3.1.1 动态规划法简介,动态规划法与分治法类似，其基本思想也是将待求解的问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。,3.1.1 动态规划法简介,与分治法不同的是，适合用动态规划求解的问题，经分解得到的子问题往往不是互相独立的。若用分治法解这类问题，则分解得到的子问题太多，以致于最后解决原问题需要耗费指数时间。在用分治求解时，有些子问题被重复计算了多次。如果能够保存已解决的子问题的答案。在需要的时候再找出已求的答案，就可以避免大量的重复计算，从而简化了算法。为了达到这个目的，可以用一个表来记录所有已解决的子问题答案。不管该子问题以后是否被用到，只要他被计算过，就将其结果填入表中。这就是动态规划法的基本思想。,图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少?,多阶段决策过程最优化问题,最短路径的特性:最短路径的第k阶段通过Xk 点，则这一最短路径在由Xk 出发到终点的那一部分路径，对于起始点为Xk 到终点的所有可能的路径来说必定也是路径最短的.,利用倒推方法求解A到E的最短距离。把从A到E的全过程分成四个阶段，用k表示阶段变量，第1阶段有一个初始状态A，两条可供选择的支路ABl、AB2；第2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路。用dk(xk，xk+1)表示在第k阶段由初始状态xk 到下阶段的初始状态xk+1的路径距离，Fk(xk)表示从第k阶段的xk 到终点E的最短距离。,求从A到E的最短路问题Fk(A)，可以转化为两个性质完全相同，但规模较小的问题，即分别从B1、B2到E的最短路问题Fk(B1)和Fk(B2)，这时有：Fk(A)=mind1(A,B1)+Fk(B1),d1(A,B2)+Fk(B2)同样，计算Fk(B1)，又可以转化为性质完全相同，但规模更小的问题，即分别从C1、C2、C3到E的最短路问题Fk(C1)、Fk(C2)和 Fk(C3)，最后，归结为Fk(D1)、Fk(D2)两个子问题。由于Fk(D1)、Fk(D2)是已知的，因此，可以从这两个值开始，逆向递归计算出Fk(A)的值。最终，可以得到从A到E的最短路径。动态规划法就是根据最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。（逆向递归的方法）,S1：K=4，有：F4(D1)=3，F4(D2)=4，F4(D3)=3S2:K=3，有：F3(C1)=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2)=min8,10=8 F3(C2)=d3(C2,D1)+F4(D1)=5+3=8 F3(C3)=d3(C3,D3)+F4(D3)=8+3=11 F3(C4)=d3(C4,D3)+F4(D3)=3+3=6S2:K=2，有：F2(B1)=mind2(B1,C1)+F3(C1),d2(B1,C2)+F3(C2),d2(B1,C3)+F3(C3)=min9,14,14=9 F2(B2)=mind2(B2,c2)+F3(C2),d2(B2,C4)+F3(C4)=min16,10=10S4：k=1，有：F1(A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2)=min14,13=13因此由A到E的全过程的最短路径为 AB2一C4D3E,最短路程长度为13。,数塔问题 有形如图所示的一个数塔，从顶部出发，在每一结点可以选择向左走或是向右走，一直走到底层，要求找出一条路径，使路径上的数值和最大。,算法设计过程如下：1.阶段划分：第一步对于第五层的数据，我们做如下决策：对经过第四层2的路径选择第五层的19，对经过第四层18的路径选择第五层的10，对经过第四层9的路径也选择第五层的10，对经过第四层5的路径选择第五层的16。,以上的决策结果将五阶数塔问题变为4阶子问题，递推出第四层与第五层的和为:21(2+19),28(18+10),19(9+10),21(5+16)。用同样的方法还可以将4阶数塔问题,变为3阶数塔问题。最后得到的1阶数塔问题，就是整个问题的最优解。,2存储、求解：1)原始信息存储 原始信息有层数和数塔中的数据，层数用一个整型变量 n 存储，数塔中的数据用二维数组data，存储成如下的下三角阵:9 12 15 10 6 8 2 18 9 5 19 7 10 4 16,2)动态规划过程存储 用二维数组d存储各阶段的决策结果。二维数组d的存储内容如下：dnj=datanj j=1,2,n；dij=max(di+1j，di+1j+1)+dataij i=n-1,n-2,1，j=1,2,i；最后d11存储的就是问题的结果。,数组data 数组d 9 59 12 15 50 49 10 6 8 38 34 29 2 18 9 5 21 28 19 21 19 7 10 4 16 19 7 10 4 16 数塔及动态规划过程数据,输出data11 9b=d11-data11=59-9=50 b与d21,d22比较,b与d21相等输出data2112b=d21-data21=50-12=38 b与d31,d32 比较b与d31相等输出data3110b=d31-data31=38-10=28 b与d41,d42 比较b与d42相等输出data4218b=d42-data42=28-18=10 b与d52,d53 比较b与d53相等输出data5310“,3)最优解路径求解及存储,为了设计简洁的算法，用三维数组a50503存储以上确定的三个数组的信息。a50501代替数组data，a50502代替数组d,a50503记录解路径。,for(i=n-1;i=1;i-)for(j=1;jai+1j+12)aij2=aij2+ai+1j2;aij3=0;else aij2=aij2+ai+1j+12;aij3=1;,cout;j=j+aij3;coutanj1;,返回,最优化问题：有n个输入，它的解由这n个输入的一个子集组成，这个子集必须满足某些事先给定的条件，这些条件称为约束条件，满足约束条件的解称为问题的可行解。满足约束条件的可行解可能不只一个，为了衡量这些可行解的优劣，事先给出一定的标准，这些标准通常以函数的形式给出，这些标准函数称为目标函数，使目标函数取得极值（极大或极小）的可行解称为最优解，这类问题就称为最优化问题。,3.1.2 最优化问题,例：付款问题：超市的自动柜员机（POS机）要找给顾客数量最少的现金。假定POS机中有n张面值为pi(1in)的货币，用集合P=p1,p2,pn表示，如果POS机需支付的现金为A，那么，它必须从P中选取一个最小子集S，使得,如果用向量X=(x1,x2,xn)表示S中所选取的货币，则（式3.2）,（式3.1）,那么，POS机支付的现金必须满足（式3.3）,并且（式3.4）,在付款问题中，集合P是该问题的输入，满足式2.1的解称为可行解，式3.2是解的表现形式，因为向量X中有n个元素，每个元素的取值为0或1，所以，可以有2n个不同的向量，所有这些向量的全体构成该问题的解空间，式3.3是该问题的约束条件，式3.4是该问题的目标函数，使式3.4取得极小值的解称为该问题的最优解。,返回,3.1.3 最优性原理,对于一个具有n个输入的最优化问题，其求解过程往往可以划分为若干个阶段，每一阶段的决策仅依赖于前一阶段的状态，由决策所采取的动作使状态发生转移，成为下一阶段决策的依据。从而，一个决策序列在不断变化的状态中产生。这个决策序列产生的过程称为多阶段决策过程。,在每一阶段的决策中有一个赖以决策的策略或目标，这种策略或目标是由问题的性质和特点所确定，通常以函数的形式表示并具有递推关系，称为动态规划函数。,多阶段决策过程满足最优性原理（Optimal Principle）：无论决策过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的当前状态，构成一个最优决策序列。如果一个问题满足最优性原理通常称此问题具有最优子结构性质。,返回,3.1.4 动态规划法的设计思想,动态规划法将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，一般来说，子问题的重叠关系表现在对给定问题求解的递推关系（也就是动态规划函数）中，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解，从而避免了大量重复计算。,动态规划法的求解过程,n=5时分治法计算斐波那契数的过程。,例：计算斐波那契数：,动态规划法求解斐波那契数F(9)的填表过程：,注意到，计算F(n)是以计算它的两个重叠子问题 F(n-1)和F(n-2)的形式来表达的，所以，可以设计一张表填入n+1个F(n)的值。,用动态规划法求解的问题具有特征：能够分解为相互重叠的若干子问题；满足最优性原理（也称最优子结构性质）：该问题的最优解中也包含着其子问题的最优解。（用反证法）分析问题是否满足最优性原理：先假设由问题的最优解导出的子问题的解不是最优的;然后再证明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。,动态规划法设计算法一般分成三个阶段：（1）分段：将原问题分解为若干个相互重叠的子问题；（2）分析：分析问题是否满足最优性原理，找出动态规划函数的递推式；（3）求解：利用递推式自底向上计算，实现动态规划过程。动态规划法利用问题的最优性原理，以自底向上的方式从子问题的最优解逐步构造出整个问题的最优解。（逆向递归的方法）,返回,3.2 图问题中的动态规划法,3.2.2 TSP问题,3.2.1 多段图的最短路径问题,返回,3.2.1 多段图的最短路径问题,设图G=(V,E)是一个带权有向连通图，如果把顶点集合V划分成k个互不相交的子集Vi（2kn,1ik），使得E中的任何一条边(u,v)，必有uVi，vVi+m（1ik,1i+mk），则称图G为多段图，称sV1为源点，tVk为终点。多段图的最短路径问题是求从源点到终点的最小代价路径。,由于多段图将顶点划分为k个互不相交的子集，所以，多段图划分为k段，每一段包含顶点的一个子集。不失一般性，将多段图的顶点按照段的顺序进行编号，同一段内顶点的相互顺序无关紧要。假设图中的顶点个数为n，则源点s的编号为0，终点t的编号为n-1，并且，对图中的任何一条边(u,v)，顶点u的编号小于顶点v的编号。,设s,s1,s2,sp,t是从s到t的一条最短路径，从源点s开始，设从s到下一段的顶点s1已经求出，则问题转化为求从s1到t的最短路径，显然s1,s2,sp,t一定构成一条从s1到t的最短路径，如若不然，设s1,r1,r2,rq,t是一条从s1到t的最短路径，则s,s1,r1,r2,rq,t将是一条从s到t的路径且比s,s1,s2,sp,t的路径长度要短，从而导致矛盾。所以，多段图的最短路径问题满足最优性原理。,证明多段图问题满足最优性原理,对多段图的边(u,v)，用cuv表示边上的权值，将从源点s到终点t的最短路径记为d(s,t)，则从源点0到终点9的最短路径d(0,9)由下式确定：d(0,9)=minc01+d(1,9),c02+d(2,9),c03+d(3,9)这是最后一个阶段的决策，它依赖于d(1,9)、d(2,9)和d(3,9)的计算结果，而 d(1,9)=minc14+d(4,9),c15+d(5,9)d(2,9)=minc24+d(4,9),c25+d(5,9),c26+d(6,9)d(3,9)=minc35+d(5,9),c36+d(6,9)这一阶段的决策又依赖于d(4,9)、d(5,9)和d(6,9)的计算结果：,d(4,9)=minc47+d(7,9),c48+d(8,9)d(5,9)=minc57+d(7,9),c58+d(8,9)d(6,9)=minc67+d(7,9),c68+d(8,9)这一阶段的决策依赖于d(7,9)和d(8,9)的计算，而d(7,9)和d(8,9)可以直接获得（括号中给出了决策产生的状态转移）：d(7,9)=c797(79)d(8,9)=c893(89)再向前推导，有：d(6,9)=minc67+d(7,9),c68+d(8,9)=min6+7,5+3=8(68)d(5,9)=minc57+d(7,9),c58+d(8,9)=min8+7,6+3=9(58)d(4,9)=minc47+d(7,9),c48+d(8,9)=min5+7,6+3=9(48),d(3,9)=minc35+d(5,9),c36+d(6,9)=min4+9,7+8=13(35)d(2,9)=minc24+d(4,9),c25+d(5,9),c26+d(6,9)=min6+9,7+9,8+8=15(24)d(1,9)=minc14+d(4,9),c15+d(5,9)=min9+9,8+9=17(15)d(0,9)=minc01+d(1,9),c02+d(2,9),c03+d(3,9)=min4+17,2+15,3+13=16(03)最后，得到最短路径为03589，长度为16。,S1：K=4，有：F4(D1)=3，F4(D2)=4，F4(D3)=3S2:K=3，有：F3(C1)=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2)=min8,10=8 F3(C2)=d3(C2,D1)+F4(D1)=5+3=8 F3(C3)=d3(C3,D3)+F4(D3)=8+3=11 F3(C4)=d3(C4,D3)+F4(D3)=3+3=6S2:K=2，有：F2(B1)=mind2(B1,C1)+F3(C1),d2(B1,C2)+F3(C2),d2(B1,C3)+F3(C3)=min9,14,14=9 F2(B2)=mind2(B2,c2)+F3(C2),d2(B2,C4)+F3(C4)=min16,10=10S4：k=1，有：F1(A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2)=min14,13=13因此由A到E的全过程的最短路径为 AB2一C4D3E,最短路程长度为13。,多段图的最短路径问题的填表形式。用一个数组costn作为存储子问题解的表格，costi表示从顶点i到终点n-1的最短路径，数组pathn存储状态，pathi表示从顶点i到终点n-1的路径上顶点i的下一个顶点。则：costi=mincij+costj(ijn且顶点j是顶点i的邻接点)(式3.5)pathi=使cij+costj最小的j(式3.6）,算法多段图的最短路径 1初始化：数组costn初始化为最大值，数组pathn初始化为-1；2for(i=n-2;i=0;i-)2.1 对顶点i的每一个邻接点j，根据式2.5计算costi;2.2 根据式2.6计算pathi;3输出最短路径长度cost0;4.输出最短路径经过的顶点：4.1 i=0 4.2 循环直到pathi=n-1 4.2.1 输出pathi;4.2.2 i=pathi;,算法主要由三部分组成：第一部分是初始化部分，其时间性能为O(n)；第二部分是依次计算各个顶点到终点的最短路径，由两层嵌套的循环组成，外层循环执行n-1次，内层循环对所有出边进行计算，并且在所有循环中，每条出边只计算一次。假定图的边数为m，则这部分的时间性能是O(m)；第三部分是输出最短路径经过的顶点，其时间性能是O(n)。所以，算法6.2的时间复杂性为O(n+m)。,返回,3.2.2 TSP问题,TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。各个城市间的距离可以用代价矩阵来表示。,设s,s1,s2,sp,s是从s出发的一条路径长度最短的简单回路，假设从s到下一个城市s1已经求出，则问题转化为求从s1到s的最短路径，显然s1,s2,sp,s一定构成一条从s1到s的最短路径。如若不然，设s1,r1,r2,rq,s是一条从s1到s的最短路径且经过n-1个不同城市，则s,s1,r1,r2,rq,s将是一条从s出发的路径长度最短的简单回路且比s,s1,s2,sp,s要短，从而导致矛盾。所以，TSP问题满足最优性原理。,证明TSP问题满足最优性原理,假设从顶点i出发，令d(i,V)表示从顶点i 出发经过V 中各个顶点一次且仅一次，最后回到出发点 i 的最短路径长度，开始时，V V i，于是，TSP问题的动态规划函数为：d(i,V)=mincik+d(k,Vk)(kV)（式3.7）d(k,)=cki(ki)（式3.8）,这是最后一个阶段的决策，而：d(1,2,3)=minc12+d(2,3),c13+d(3,2)d(2,1,3)=minc21+d(1,3),c23+d(3,1)d(3,1,2)=minc31+d(1,2),c32+d(2,1)这一阶段的决策又依赖于下面的计算结果：d(1,2)=c12+d(2,)d(2,3)=c23+d(3,)d(3,2)=c32+d(2,)d(1,3)=c13+d(3,)d(2,1)=c21+d(1,)d(3,1)=c31+d(1,),从城市0出发经城市1、2、3然后回到城市0的最短路径长度是：d(0,1,2,3)=minc01+d(1,2,3),c02+d(2,1,3),c03+d(3,1,2),而下式可以直接获得（括号中是该决策引起的状态转移）：d(1,)=c10=5(10)d(2,)=c20=6(20)d(3,)=c30=3(30),再向前倒推，有：d(1,2)=c12+d(2,)=2+6=8(12)d(1,3)=c13+d(3,)=3+3=6(13)d(2,3)=c23+d(3,)=2+3=5(23)d(2,1)=c21+d(1,)=4+5=9(21)d(3,1)=c31+d(1,)=7+5=12(31)d(3,2)=c32+d(2,)=5+6=11(32)再向前倒退，有：d(1,2,3)=minc12+d(2,3),c13+d(3,2)=min2+5,3+11=7(12)d(2,1,3)=minc21+d(1,3),c23+d(3,1)=min4+6,2+12=10(21),d(3,1,2)=minc31+d(1,2),c32+d(2,1)=min7+8,5+9=14(32)最后有：d(0,1,2,3)=minc01+d(1,2,3),c02+d(2,1,3),c03+d(3,1,2)=min3+7,6+10,7+14=10(01)所以，从顶点0出发的TSP问题的最短路径长度为10，路径是01230。,假设n个顶点用0n-1的数字编号，首先生成1n-1个元素的子集存放在数组V2n-1中，设数组dn2n-1存放迭代结果，其中dij表示从顶点i经过子集Vj中的顶点一次且仅一次，最后回到出发点0的最短路径长度。,动态规划法求解TSP问题的填表过程,算法TSP问题 1for(i=1;in;i+)/初始化第0列 di0=ci0;2for(j=1;j2n-1-1;j+)for(i=1;in;i+)/依次进行第i次迭代 if(子集Vj中不包含i)对Vj中的每个元素k，计算dij=min(cik+dkj-1);3对V2n-1-1中每一个元素k，计算d02n-1-1=min(c0k+dk2n-1-2);4输出最短路径长度d02n-1-1;,显然，算法的时间复杂性为O(2n)。和蛮力法相比，动态规划法求解TSP问题，把原来的时间复杂性是O(n!)的排列问题，转化为组合问题，从而降低了算法的时间复杂性，但它仍需要指数时间。,设顶点之间的代价存放在数组cnn中，动态规划法求解TSP问题的算法如下：,返回,3.3 组合问题中的动态规划法,3.3.1 0/1背包问题,3.3.2 最长公共子序列问题,返回,0/1背包问题,在0/1背包问题中，物品i或者被装入背包，或者不被装入背包，设xi表示物品i装入背包的情况，则当xi=0时，表示物品i没有被装入背包，xi=1时，表示物品i被装入背包。根据问题的要求，有如下约束条件和目标函数：,（式3.9）,（式3.10）,于是，问题归结为寻找一个满足约束条件式3.9，并使目标函数式3.10达到最大的解向量X=(x1,x2,xn)。,证明0/1背包问题满足最优性原理。设(x1,x2,xn)是所给0/1背包问题的一个最优解，则(x2,xn)是下面一个子问题的最优解：,如若不然，设(y2,yn)是上述子问题的一个最优解，则 因此，这说明(x1,y2,yn)是所给0/1背包问题比(x1,x2,xn)更优的解，从而导致矛盾。,0/1背包问题可以看作是决策一个序列(x1,x2,xn)，对任一变量xi的决策是决定xi=1还是xi=0。在对xi-1决策后，已确定了(x1,xi-1)，在决策xi时，问题处于下列两种状态之一：（1）背包容量不足以装入物品i，则xi=0，背包不增加价值；（2）背包容量可以装入物品i，则xi=1，背包的价值增加了vi 这两种情况下背包价值的最大者应该是对xi决策后的背包价值。,的最优值为V(i，j)，即V(i，j)是背包容量为j（1jC），可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算V(i，j)的递归式（动态规划函数）如下。V(i,0)=V(0,j)=0（式3.11）,（式3.12）,设所给0-1背包问题的子问题,式3.11表明：把前面i个物品装入容量为0的背包和把0个物品装入容量为j的背包，得到的价值均为0。式3.12的第一个式子表明：如果第i个物品的重量大于背包的容量，则装入前i个物品得到的最大价值和装入前i-1个物品得到的最大价值是相同的，即物品i不能装入背包；第二个式子表明：如果第i个物品的重量小于背包的容量，则会有以下两种情况：（1）如果把第i个物品装入背包，则背包中物品的价值等于把前i-1个物品装入容量为j-wi的背包中的价值加上第i个物品的价值vi；（2）如果第i个物品没有装入背包，则背包中物品的价值就等于把前i-1个物品装入容量为j的背包中所取得的价值。显然，取二者中价值较大者作为把前i个物品装入容量为j的背包中的最优解。,根据动态规划函数，用一个(n+1)(C+1)的二维表V，Vij表示把前i个物品装入容量为j的背包中获得的最大价值。,例如，有5个物品，其重量分别是2,2,6,5,4，价值分别为 6,3,5,4,6，背包的容量为10。,按下述方法来划分阶段：第一阶段，只装入前1个物品，确定在各种情况下的背包能够得到的最大价值；第二阶段，只装入前2个物品，确定在各种情况下的背包能够得到的最大价值；依此类推，直到第n个阶段。最后，V(n,C)便是在容量为C的背包中装入n个物品时取得的最大价值。为了确定装入背包的具体物品，从V(n,C)的值向前推，如果V(n,C)V(n-1,C)，表明第n个物品被装入背包，前n-1个物品被装入容量为C-wn的背包中；否则，第n个物品没有被装入背包，前n-1个物品被装入容量为C的背包中。依此类推，直到确定第1个物品是否被装入背包中为止。由此，得到如下函数：,（式3.13）,设n个物品的重量存储在数组wn中，价值存储在数组vn中，背包容量为C，数组Vn+1C+1存放迭代结果，其中Vij表示前i个物品装入容量为j的背包中获得的最大价值，数组xn存储装入背包的物品，动态规划法求解0/1背包问题的算法如下：,算法0/1背包问题 int KnapSack(int n,int w,int v)for(i=0;i0;i-)if(VijVi-1j)xi=1;j=j-wi;else xi=0;return VnC;/返回背包取得的最大价值,在算法中，第一个for循环的时间性能是O(n)，第二个for循环的时间性能是O(C)，第三个循环是两层嵌套的for循环，其时间性能是O(nC)，第四个for循环的时间性能是O(n)，所以，算法6.3的时间复杂性为O(nC)。,返回,3.3.2 最长公共子序列问题,对给定序列X=(x1,x2,xm)和序列Z=(z1,z2,zk)，Z是X的子序列当且仅当存在一个严格递增下标序列(i1,i2,ik)，使得对于所有j=1,2,k，有zj=xij（1ijm）。给定两个序列X和Y，当另一个序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。最长公共子序列问题就是在序列X和Y的公共子序列中查找长度最长的公共子序列。,证明最长公共子序列问题满足最优性原理。设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，记Xk为序列X中前k个连续字符组成的子序列，Yk为序列Y中前k个连续字符组成的子序列，Zk为序列Z中前k个连续字符组成的子序列，显然有下式成立：（1）若xm=yn，则zk=xm=yn，且Zk-1是Xm-1和Yn-1的最长公共子序列；（2）若xmyn且zkxm，则Z是Xm-1和Y的最长公共子序列；（3）若xmyn且zkyn，则Z是X和Yn-1的最长公共子序列。可见，两个序列的最长公共子序列包含了这两个序列的前缀序列的最长公共子序列。,要找出序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列，可按下述递推方式计算：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm即可得到X和Y的最长公共子序列；当xmyn时，必须求解两个子问题：找出Xm-1和Y的最长公共子序列以及Xm和Yn-1的最长公共子序列，这两个公共子序列中的较长者即为X和Y的最长公共子序列。用Lij表示子序列Xi和Yj的最长公共子序列的长度，可得如下动态规划函数：L00=Li0=L0j=0(1im,1jn)（式3.14）（式3.15）,由此，把序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列的搜索分为m个阶段，第1阶段，按照式3.15计算X1和Yj的最长公共子序列长度L1j（1jn），第2阶段，按照式3.15计算X2和Yj的最长公共子序列长度L2j（1jn），依此类推，最后在第m阶段，计算Xm和Yj的最长公共子序列长度Lmj（1jn），则Lmn就是序列Xm和Yn的最长公共子序列的长度。,为了得到序列Xm和Yn具体的最长公共子序列，设二维表Sm+1n+1，其中Sij表示在计算Lij的过程中的搜索状态，并且有：,（式3.16）,若Sij=1，表明ai=bj，则下一个搜索方向是Si-1j-1；若Sij=2，表明aibj且Lij-1Li-1j，则下一个搜索方向是Sij-1；若Sij=3，表明aibj且Lij-1Li-1j，则下一个搜索方向是Si-1j。,(a)长度矩阵L(b)状态矩阵S,例：序列X=(a,b,c,b,d,b)，Y=(a,c,b,b,a,b,d,b,b)，建立两个(m+1)(n+1)的二维表L和表S，分别存放搜索过程中得到的子序列的长度和状态。,算法最长公共子序列问题 int CommonOrder(int m,int n,int x,int y,int z)for(j=0;j=Li-1j)Lij=Lij-1;Sij=2;else Lij=Li-1j;Sij=3;i=m;j=n;k=Lmn;for(i0,第一个for循环的时间性能是O(n)；第二个for循环的时间性能是O(m)；第三个循环是两层嵌套的for循环，其时间性能是O(mn)；第四个for循环的时间性能是O(k)，而kminm,n，所以，算法6.4的时间复杂性是O(mn)。,返回,设r1,r2,rn是n个记录的集合，其查找概率分别是p1,p2,pn，最优二叉查找树（Optimal Binary Search Trees）是以这n个记录构成的二叉查找树中具有最少平均比较次数的二叉查找树，即 最小，其中pi是记录ri的查找概率，ci是在二叉查找树中查找ri的比较次数。,最优二叉查找树,3.4 查找问题中的动态规划法,返回,例如，集合A,B,C,D的查找概率是0.1,0.2,0.4,0.3，(a)的平均比较次数是0.110.22+0.43+0.34=2.9，(b)的平均比较次数是0.120.21+0.42+0.33=2.1，(c)的平均比较次数是0.130.22+0.41+0.32=1.7。,将由r1,r2,rn构成的二叉查找树记为T(1,n)，其中rk（1kn）是T(1,n)的根结点，则其左子树T(1,k-1)由r1,rk-1构成，其右子树T(k+1,n)由rk+1,rn构成。,证明最优二叉查找树满足最优性原理,若T(1,n)是最优二叉查找树，则其左子树T(1,k-1)和右子树T(k+1,n)也是最优二叉查找树，如若不然，假设T(1,k-1)是比T(1,k-1)更优的二叉查找树，则T(1,k-1)的平均比较次数小于T(1,k-1)的平均比较次数，从而由T(1,k-1)、rk和T(k+1,n)构成的二叉查找树T(1,n)的平均比较次数小于T(1,n)的平均比较次数，这与T(1,n)是最优二叉查找树的假设相矛盾。,设T(i,j)是由记录ri,rj(1ijn)构成的二叉查找树，C(i,j)是这棵二叉查找树的平均比较次数。虽然最后的结果是C(1,n)，但遵循动态规划法的求解方法,需要求出所有较小子问题C(i,j)的值，考虑从ri,rj中选择一个记录rk作为二叉查找树的根结点，可以得到如下关系：,因此，得到如下动态规划函数：C(i,i-1)=0(1in+1)（式6.17）C(i,i)=pi(1in)（式6.18）C(i,j)=minC(i,k-1)+C(k+1,j)+(1ijn,ikj)（式6.19）设一个二维表Cn+1n+1，其中Cij表示二叉查找树T(i,j)的平均比较次数。注意到在式6.19中，当k=1时，求Cij需要用到Ci0，当k=n时，求Cij需要用到Cn+1j，所以，二维表Cn+1n+1行下标的范围为1n+1，列下标的范围为0n。为了在求出由r1,r2,rn构成的二叉查找树的平均比较次数的同时得到最优二叉查找树，设一个二维表Rn+1n+1，其下标范围与二维表C相同，Rij表示二叉查找树T(i,j)的根结点的序号。,例如，集合A,B,C,D的查找概率是0.1,0.2,0.4,0.3，二维表C和R的初始情况如图6.13所示。,在二维表C和R中只需计算主对角线以上的元素。首先计算C(1,2)：,在前两个记录构成的最优二叉查找树的根结点的序号是2。,按对角线逐条计算每一个C(i,j)和R(i,j)，得到最终表。,设n个字符的查找概率存储在数组pn中，动态规划法求解最优二叉查找树的算法如下：,算法最优二叉查找树 double OptimalBST(int n,double p,double C,int R)for(i=1;i=n;i+)/按式6.17和式6.18初始化 Cii-1=0;Cii=pi;Rii=i;Cn+1n=0;,for(d=1;dn;d+)/按对角线逐条计算 for(i=1;i=n-d;i+)j=i+d;min=;mink=i;sum=0;for(k=i;k=j;k+)sum=sum+pk;if(Cik-1+Ck+1jmin)min=Cik-1+Ck+1j;mink=k;Cij=min+sum;Rij=mink;return C1n;,返回,