资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,学习要点:,理解动态规划算法的概念。,掌握动态规划算法的根本要素,1最优子构造性质,2重叠子问题性质,掌握设计动态规划算法的步骤。,(1)找出最优解的性质，并刻划其构造特征。,(2)递归地定义最优值。,(3)以自底向上的方式计算出最优值。,(4)根据计算最优值时得到的信息，构造最优解。,第,4,章 动态规划,dynamic programming,1,最优化原理,1951年美国数学家RBellman等人，根据一类多阶段问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。与此同时，他提出了解决这类问题的“最优化原理(PrincipleofOptimality)。,“最优化原理用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，Dn，如假设这个决策序列是最优的，对于任何一个整数k，1 k B2,一,C4D3E,。最短路程长度为,13,。,12,动态规划算法求解问题的一般思路,每个阶段中，都求出本阶段的各个初始状态到过程终点,E,的最短路径和最短距离，当逆序倒推到过程起点,A,时，便得到了全过程的最短路径及最短距离，同时附带得到了一组最优结果,(,即各阶段的各状态到终点,E,的最优结果,),。,13,思考与练习：假设城市路径示意图如下图，图中，每条边上的数字是这段道路的长度。条件：从A地出发，只允许向右或向上走。试寻找一条从A地到B地的最短路径和长度。,14,动态规划根本步骤,找出最优解的性质，并刻划其构造特征。,递归地定义最优值。,以自底向上的方式计算出最优值。,根据计算最优值时得到的信息，构造最优解。,在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准那么便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。,15,4.1,算法总体思想,动态规划设计的一般模式：,for k:=阶段最小值 to 阶段最大值 do,顺推每一个阶段,for I:=状态最小值 to 状态最大值 do,枚举阶段k的每一个状态,for j:=决策最小值 to 决策最大值 do,枚举阶段k中状态i可选择的每一种决策,fik:=minmaxfik-1+aik-1，jk-1|ik-1通过决策jk-1可达ik,16,4.2 动态规划算法的根本要素,一、最优子构造,某个问题的最优解包含着其子问题的最优解。这种性质称为最优子构造性质。,同一个问题可以有多种方式刻划它的最优子构造，有些表示方法的求解速度更快空间占用小，问题的维度低,例如图中，假设路线I和J是A到C的最优路径，那么根据最优化原理，路线J必是从B到C的最优路线。这可用反证法证明：假设有另一路径J是B到C的最优路径，那么A到C的路线取I和J比I和J更优，矛盾。从而证明J必是B到C的最优路径。,最优子构造是问题能用动态规划算法求解的前提。,17,4.2动态规划算法的根本要素,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算屡次。这种性质称为子问题的重叠性质。,动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。,通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,18,4.2动态规划算法的根本要素,三、备忘录方法,备忘录方法的控制构造与直接递归方法的控制构造一样，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，防止了一样子问题的重复求解。,步骤：,为每个问题建立一个记录项，初值设为一个特殊值表未求解,每个待求解子问题，首先查记录项，有解答那么直接选取，否那么求解该子问题。,19,4.3,典型问题,-,合唱队形,【问题描述】N位同学站成一排，音乐教师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, , K，他们的身高分别为T1, T2, , TK，那么他们的身高满足T1 Ti+1 TK (1 = i =1;因为它本身就是一个上升序列元素。假设 i=1 ，此时b1=1;因为a1的前面没有元素。那么如果a2a1，显然可以得到b2=b1+1,因为a1、a2是一个上升子序列。如果a2a1.a3-1，那么b3=maxb1.b3-1+1。由此我们可以得到递推关系式：bi=maxbj(1 aj+1,ci=maxcj(i aj+1,然后，可以得到符合合唱队的队列是bi+ci-1(ai被重复计算了一次)，而题目要求的合唱队列是：maxbi+ci-1。,21,4.3,典型问题,-,合唱队形,i,1,2,3,4,5,6,7,8,ai,186,186,150,200,160,130,197,220,bi,1,1,1,2,2,1,3,4,ci,3,3,2,3,2,1,1,1,bi+ci,4,4,3,5,4,2,4,5,22,4.3,典型问题,-,合唱队形,#include ,#include ,#define MAXN 200,int main(),int n, aMAXN, bMAXN, cMAXN, i, j, max;,scanf(%d, ,for (i = 1; i = n; i+),O(n),scanf(%d, ,memset(b, 0, sizeof(a);,memset(c, 0, sizeof(c);,/,求左侧的最长上升子序列,O(n,2,),b1 = 1;,for (i = 2; i = 1; j-),if (aj max),max = bj;,bi = max + 1;,/,求左侧的最长上升子序列,O(n,2,),cn = 1;,for (i = n - 1; i 0; i-),max = 0;,for (j = i + 1; j = n; j+),if (aj max),max = cj;,ci = max + 1;,/,枚举求最长队形长度,O(n),max = b1 + c1;,for (i = 2; i max),max = bi + ci;,printf(%dn, n - max + 1);,return 0;,思考：如何判断哪些人出队列？LISLongest Increasing Subsequence,23,4.3,典型问题,-,合唱队形,#include ,#include ,#define MAXN 200,int main(),int premaxN=0;,/,求左侧的最长上升子序列,O(n,2,),b1 = 1;,for (i = 2; i = 1; j-),if (aj max),max = bj;,prei=j;,bi = max + 1;,/,求左侧的最长上升子序列,O(n,2,),略,/,输出最长队形,O(n),for (i = n; i=1;i-),if (prei!=0),printf(%dn, aprei);,24,4.3,典型问题,-,合唱队形,i,1,2,3,4,5,6,7,8,ai,186,186,150,200,160,130,197,220,bi,1,1,1,2,2,1,3,4,prei,0,0,0,3,3,0,5,7,25,4.4,典型问题,最大,k,乘积,题目：在一个长度为N的数字串中插入k-1个乘号，将N分成k局部，找出一种分法，使得这k个局部的乘积最大。,例如有一个数字串: 312，当N=3，K=1时会有以下两种分法：,13*12=36 231*2=62这时，符合题目要求的结果是： 31*2=62,问题中只有乘号插入的位置是变化的，取数字串中的任意一段P1，P2，假设能求出在其中插入k-2个乘号的最大乘积，那么只需穷举第k-1个乘号的插入位置P。打擂台选出P在各个位置时得到的最大乘积即为问题的解。,依此类推，把k-2的问题归结为k-3的情况，直到求在任意一段中插入1个乘号的最大乘积时，需预先算出在任意一段中插入0个乘号时的最大乘积。而此时的值是的即为该段的数值。,26,4.4,典型问题,最大,k,乘积,设w(h,k) 表示: 从第h位到第K位所组成的十进制数。,设m(i,j)表示：前i位(从1i)分成j段所得的最大乘积,那么可得到如下的DP方程：,if(j=1) m(i,1) = w(1,i) ;,if(j =1 & j=i) m(i,j) = maxm(d,j-1)*w(d+1,i),其中: 1=d i (即从1开场直到i-1 中找最大值,else if(i j) m(i,j) = 0 ;,27,void maxdp(int n,int k,int *a),for(i=1; i= n ; i+) /*,分成,1,段*,/,mi1 = w1i;,for(i=1 ; i= n ; i+) /* DP,过程*,/,for(j=2; j= k ; j+), max = 0;,for(d=1; d max),max = temp ;,mij = max ;,int main(void),La=0,；,scanf(%d %d ,while ( ( c=getchar() )!=n) /*,读入数据*,/,a+la = c-0 ;,for(i=1; i= n; i+), wii= ai ;,for(j=i+1 ; j= n; j+),wij = wij-1*10 + aj ;,for(i=1 ; i= n; i+) /,输出, for(j=1 ; j= n; j+),printf(%5d,wij);,printf(n);,maxdp(n,k,a) ;,printf(nmax=%ld ,mnk) ;,28,4.5,典型问题,0-1,背包问题,问题描述给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大,0-1背包问题是一个特殊的整数规划问题。,29,4.5,典型问题,0-1,背包问题,1,、减小规模,m(i,，,j),是背包容量为,j,，可选择物品为,i,，,i+1,，,，,n,时,0-1,背包问题的最优值。,m(i+1,，,j),可选择物品为,i+1,，,，,n,时,0-1,背包问题的最优值。,m(n,，,j),可选择物品为,n,时,0-1,背包问题的最优值。,规模已经为,1,2、推导递归式，判断第i件？,1不放，背包当前产生价值仍为m(i+1，j)；,2放入，调整背包容量j-wi，背包当前产生价值为m(i+1,j-wi)+Vi,30,4.5,典型问题,0-1,背包问题,m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子构造性质，可以建立计算m(i，j)的递归式如下。,31,void KnapSack(int v,int w,int c,int n,int m11),int jMax=min(wn-1,c);,for (j=0;j=jMax;j+) /*m(n,j)=0 0=j1;i-), int jMax=min(wi-1,c);,for (j=0;j=jMax;j+) /*m(i,j)=m(i+1,j) 0=j=w1),m1c=max(m1c,m2c-w1+v1);,32,4.5,典型问题,0-1,背包问题,算法复杂度分析：,从,m(i,，,j),的递归式容易看出，算法需要,O(nc),计算时间。当背包容量,c,很大时，算法需要的计算时间较多。例如，当,c2,n,时，算法需要,(,n2,n,),计算时间。,m(i,j),值,0 1 2 3 4 5 6 7 8 9 10,1,2,3,4,5,N=5,，,c=10,，,w=2,，,2,，,6,，,5,，,4,v=6,3,5,4,6,m(i,，,j),是背包容量为,j,，可选择物品为,i,，,i+1,，,，,n,时,0-1,背包问题的最优值,33,4.5,典型问题,0-1,背包问题,用倒推法来求出每种物品是否选中。选中,1,，,2,，,5,三件物品，最高价值,15,，总重,8,。,void traceback(int m11,int w,int c,int n,int x),for(i=1;i0 1:0);,N=5,，,c=10,，,w=2,，,2,，,6,，,5,，,4,v=6,3,5,4,6,34,思考与练习工程选择问题,某工厂预计明年有A,B,C,D四个新建工程，每个工程的投资额 wk及其投资后的收益 vk如下表所示。投资总额为30万元，问如何选择工程才能使总收益最大。,上述问题的静态规划模型如下：,35,例 工程选择问题,解：设工程选择的顺序为A, B, C, D;,1、阶段 k=1, 2, 3, 4 分别对应 D, C, B, A工程的选择过程,2、第 k 阶段的状态 sk，代表第 k 阶段初尚未分配的投资额,3、第 k 阶段的决策变量 xk,，代表第 k 阶段分配的投资额,4、状态转移方程为 sk1= sk wk xk,5、直接效益 dk(sk ,xk)= vk 或 0,6、总效益递推公式,36,4.6,典型问题,花瓶插花问题,【问题描述】想以最美观的方式布置花店的橱窗。有F束花，每束花的品种都不一样，同时至少有同样数量的花瓶。花瓶从左到右按1 到 V编号。花束可以移动，并且每束花用1到F的整数唯一标识。标识花束的整数决定了花束在花瓶中的排列的顺序，如果ij，那么花束i必须放在花束j左边的花瓶中。如果花瓶的数目大于花束的数目，那么多余的花瓶必须空，即每个花瓶只能放一束花。 每一个花瓶的形状和颜色也不同，因此，当各个花瓶中放入不同的花束时，会产生不同的美学效果，并以美学值一个整数来表示，空花瓶的美学值为0。在上述例子中，花瓶与花束不同的搭配所具有的美学值，可以用如下的表格表示：,pFV,花束 花瓶,1,2,3,4,5,1,7,23,-5,-24,16,2,5,21,-4,10,23,3,-21,5,-4,-20,20,37,4.6,典型问题,花瓶插花问题,qij,表示,1.i,束鲜花插入,1.j,个花瓶所能得到的最大好看程度,规划方程为,:qij=MAX(qi-1j-1+pij,qij-1),边界条件为：,q00=0,；,q0j=0(1=j=v),1.j束鲜花插入到前面的1.j只花瓶中,所得到的好看程度是 qjj=p11+p22+.+p jj.,将插花过程按花瓶排列顺序划分成不同阶段,那么在第j阶段,第i束鲜花假设放入第j号花瓶,最大好看程度是qi-1j-1+pij;第i束鲜花假设放入前j-1个花瓶中的某一个,所得的好看程度是qij-1, 那么在第j阶段,插入第i束鲜花所能得到的最大好看程度为:qij=MAX(qi-1j-1+pij,qij-1),qFV是问题的解,38,q00=0,;/,没有一束花插入花瓶时,好看程度为,0,/,设置,v,个花瓶分别被插入,v,束鲜花时各号花瓶对应的,(,初始,),最大好看程度,for(j=1;j=V;j+) q0j=0; /,设置第,j,束鲜花放入第,j,号花瓶中的最大好看程度,qjj=qj-1j-1+pjj; ,for (j=1;j=V; j+) for(i=1;i0;i-) while(qi-1newv-1+pinewvqinewv) newv-; /,确定鲜花,i,插在花瓶,newv,中,并准备考虑前一只花瓶,wayi=newv-; return(qFV); ,39,i j,0,1,2,3,4,5,0,0,0,0,0,0,0,1,0,7,23,23,23,23,2,0,0,28,28,33,46,3,0,0,0,24,24,53,pij,pij,表示第,i,束花插入第,j,个花瓶的好看程度,qij,表示,1.i,束鲜花插入,1.j,个花瓶所能得到的最大好看程度,qij,=MAX(qi-1j-1+pij,qij-1),qij,花 花瓶,1,2,3,4,5,1,7,23,-5,-24,16,2,5,21,-4,10,23,3,-21,5,-4,-20,20,40,4.7,田忌赛马,问题描述田忌与齐王赛马，双方各有n匹马参赛n=1;i-) for(j=2;jbj) cij=ci+1j-1-1; if(ai+j-1=bj) cij=max(ci+1j-1-1,cij-1),44,4.7,田忌赛马,a1.5,100,90,60,50,45,b1.5,90,80,75,60,40,ci,j,1,2,3,4,5,1,-1,-1,0,1,2,2,0,1,2,3,0,3,1,2,3,0,0,4,1,2,0,0,0,5,1,0,0,0,0,c(i，j)为齐王的从第i匹马开场的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益,45,练习,46,提示：,for(r=n-2;r=0;r-) for(c=0;ctr+1c+1),trc+=tr+1c;,else trc+=tr+1c+1;,7,8,10,74 4,452 6 5,47,4.8 典型问题石子归并问题略,问题描述在一个圆形操场的四周摆放着N堆石子(N=100),现要将石子有次序地合并成一堆. 规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数记为该次合并的得分. 编写一程序,读入堆栈数N及每堆栈的石子数(=20).,选择一种合并石子的方案, 做N-1次合并,使所有得分的总和最小最大。,1,2,3,8,48,4.8,典型问题,石子归并问题,方法一每次找相邻最小的两堆合并,从最左上面的一堆开场,沿顺时针方向排成一个序列.,合并的过程如下:,每次合并得分:,第一次合并 3 4 6 5 4 25,第二次合并 5 4 6 5 4 9,第三次合并 9 6 5 4 9,第四次合并 9 6 9 15,第五次合并 15 9 24,总得分=5+9+9+15+24=62,例如有,6,堆石子,每堆石子数依次为,3 4 6 5 4 2.,要求做,5,次合并,得分的总和最小,.,贪心法,：每一次选择得分最小的相邻两堆合并,不一定保证余下的合并过程能导致最优解,.,49,4.8,典型问题,石子归并问题,方法二：另外方法逐次合并,合并的过程如下,:,每次合并得分,:,第一次合并,3 4,6 5 4 27,第二次合并,7 6,5 4 2 13,第三次合并,13 5,4 2, 6,第四次合并,13,5 6, 11,第五次合并,13 11, 24,总得分,=7+13+6+11+24=61,例如有,6,堆石子,每堆石子数依次为,3 4 6 5 4 2.,要求做,5,次合并,得分的总和最小,.,如果,N-1,次合并的全局最优解包含了每一次合并的子问题的最优解,那么经这样的,N-1,次合并后的得分总和必然是最优的,.,50,4.8,典型问题,石子归并问题,例如上例中第五次合并石子数分别为,13,和,11,的相邻两堆,.,这两堆石头分别由最初的第,1,2,3,堆,(,石头数分别为,3,4,6),和第,4,5,6,堆,(,石头数分别为,5,4,2),经,4,次合并后形成的,.,于是问题又归结为如何使得这两个子序列的,N-2,次合并的得分总和最优,.,为了实现这一目标,我们将第,1,个序列又一分为二,:,第,1,、,2,堆构成子序列,1,第,3,堆为子序列,2.,第一次合并子序列,1,中的两堆,得分,7;,第二次再将之与子序列,2,的一堆合并,得分,13.,显然对于第,1,个子序列来说,这样的合并方案是最优的,.,同样,我们将第,2,个子序列也一分为二,:,第,4,堆为子序列,1,第,5,6,堆构成子序列,2.,第三次合并子序列,2,中的,2,堆,得分,6;,第四次再将之与子序列,1,中的一堆合并,得分,13.,显然对于第二个子序列来说,这样的合并方案也是最优的,.,由此得出一个结论,: 6,堆石子经过这样的,5,次合并后,得分的总和最小,.,51,4.8,典型问题,石子归并问题,动态规划思路： 阶段i：石子的每一次合并过程，先两两合并，再三三合并，.最后N堆合并 状态s：每一阶段中各个不同合并方法的石子合并总得分。 决策：把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方案。,采用动态规划求解的关键是确定所有石子堆子序列的最正确合并方案。 这些石子堆子序列包括：第堆、第堆、第堆、第堆、第N堆、第堆；第堆、第堆、第堆、第堆、第堆、第堆、第N堆、第堆、第堆；第堆、第N堆第2堆、第N堆、第堆第N堆、第堆、第N堆,52,4.8,典型问题,石子归并问题,为了便于运算，我们用i，j表示一个从第i堆数起，顺时针数j堆时的子序列第i堆、第i堆、第ij1mod n堆,设fi，j将子序列i，j中的j堆石子合并成一堆的最正确得分和；ci，j将i，j一分为二，其中子序列的堆数；iN，jN显然，对每一堆石子来说，它的fi，1因为一开场还没有合并，所以这些值应该全部为0。,ci， (1iN),53,4.8,典型问题,石子归并问题,规划的方向是顺推。先考虑含二堆石子的N个子序列各子序列分别从第堆、第堆、第N堆数起，顺时针数堆的合并方案f，f，fN，c，c，cN，,然后考虑含三堆石子的个子序列各子序列分别从第堆、第堆、第堆数起，顺时针数堆的合并方案f，f，fN，c，c，cN，,依次类推，直至考虑了含N堆石子的N个子序列各子序列分别从第堆、第堆、 、第N堆数起，顺时针数N堆的合并方案f，N，f，N，fN，Nc，N，c，N，cN，N,最后，在子序列，N，N，N，N中，选择得分总和f值最小或最大的一个子序列i，NiN，由此出发倒推合并过程。,54,4.8,典型问题,石子归并问题,动态规划方程和倒推合并过程,对子序列(i,j)最后一次合并,其得分为第i堆数起,顺时针数j堆的石子总数t.,被合并的两堆石子是由子序列(i,k)和(i+k-1)modn+1, j-k) (1kj-1)经有限次合并形成的. 为了求出最正确合并方案中的k值,我们定义一个动态规划方程:,当求最大得分总和时,f(i,j)=maxf(i,k)+f(x,j-k)+t 1kj-1,c(i,j)=k f(i,j)=f(i,k)+f(x,j-k)+t 2jn,1in,当求最小得分总和时,f(i,j)=minf(i,k)+f(x,j-k)+t1kj-1,c(i,j)=k f(i,j)=f(i,k)+f(x,j-k)+t2jn,1in,其中x=(i+k-1)modn+1,即第i堆数起,顺时针数k+1堆的堆序号.,55,4.8,典型问题,石子归并问题,j i,1,2,3,4,5,6,1,0,7,20,36,51,61,2,0,10,25,38,48,62,3,0,11,24,34,45,61,4,0,9,17,28,41,61,5,0,6,14,26,43,61,6,0,5,14,29,45,62,fi,j,ci,j,j i,1,2,3,4,5,6,1,0,1,2,2,3,3,2,0,1,2,2,2,2,3,0,1,1,1,2,2,4,0,1,1,1,2,3,5,0,1,1,2,3,4,6,0,1,2,3,3,3,f(i,j)=minf(i,k)+f(x,j-k)+t 1kj-1,c(i,j)=k f(i,j)=f(i,k)+f(x,j-k)+t 2jn,1in,x=(i+k-1)modn+1,56,4.8,典型问题,石子归并问题,57,4.8,典型问题,石子归并问题,上述倒推过程,可由一个,print(,子序列,),的递归算法描述,:,void print(i,j), if(j!=1) /*,继续倒推合并过程*,/, print(i,c(i,j); /*,倒推子序列,1,的合并过程*,/,print(i+c(i,j)-1)%(n+1),j-c(i,j); /*,倒推子序列,2,的合并过程*,/,for(k=1;kN;k+), if(,第,K,堆石子未从圈内去除,),if(K=i | K=X),置第,K,堆石子待合并标志,;,else,第,K,堆石子未被合并,;,第,i,堆石子数第,i,堆石子数,+,第,X,堆石子数,;,将第,X,堆石子从圈内去除,;,58,4.8,典型问题,石子归并问题,59,4.9 最优二叉搜索树(,选学,),1,、二叉搜索树,是一棵二元树，或者为空，或者每个结点含有一个可比较大小的数据元素。并且：,1假设它的左子树不空，那么左子树上所有节点的值均小于它的根节点的值；,2假设它的右子树不空，那么右子树上所有节点的值均大于它的根节点的值；,3 它的左、右子树也分别为二叉排序树,注：树中所有结点互异,45,12,53,3,37,24,100,61,90,78,3,45,12,53,37,24,100,61,90,78,60,4.9 最优二叉搜索树,查找过程：,(1)假设T是空树，那么搜索失败，否那么：,(2)假设x等于T的根结点的数据域之值，那么查找成功；否那么：,(3)假设x小于T的根结点的数据域之值，那么搜索左子树；否那么：,(4)查找右子树。,2,、在二叉搜索树,T,中查找标识符,x,61,4.9 最优二叉搜索树,设,S=x,1,x,2,.,x,n,是一个有序集，且,x,1,x,2,.x,n,。表示有序集,S,的二叉搜索树，利用二叉树的结点来存储有序集中的元素。二叉搜索树的叶结点是形如,(x,i,，,x,i+1,),的开区间。在表示,S,的二叉搜索树中搜索一个元素,x,，返回的结果有两种情形：,在二叉搜索树的内结点中找到,x=x,i,。,在二叉搜索树的叶结点中确定,x(x,i,，,x,i+1,),。,设第一种情形中找到元素,x=x,i,的概率为,b,i,；在第二种情形中确定,x(x,i,，,x,i+1,),的概率为,a,i,。并约定,x,0,=-,，,x,n+1,=+,。显然有,搜索成功与不成功的概率,表示内部结点，包含了关键码集合中的某一个关键码；表示外部结点，代表了造成搜索失败的各关键码间隔中的不在关键码集合中的关键码。 在每两个外部结点之间必然存在一个内部结点。,62,4.9最优二叉搜索树,(a0,b1,a1,.,bn,an)称为集合S的存取概率分布。,在表示S的二叉搜索树T中，设存储元素xi的结点深度为ci；存储叶结点(xj,xj+1)的结点深度为dj，那么,上式表示在二叉搜索树T中作一次搜索所需要的平均比较次数。P又称为二叉搜索树T的平均路长。在一般情况下，不同的二叉树的平均路长是不一样的。,63,二叉搜索树的期望消耗例如,64,4.9 最优二叉搜索树,最优二叉搜索树问题,是对于有序集,S,及其存取概率分布,(a0,b1,a1,.,bn,an),，在所有表示有序集,S,的二叉搜索树中找出一棵具有最小平均路长的二叉搜索树。,65,构造最优二叉搜索树,对于任一棵子树,Tj,，它由, keyi+1, keyi+2, keyj ,组成，其内部结点的权值为, pi+1, pi+2, pj ,外部结点的权值为, q, qi+1, qi+2, qj ,使用数组,Wj,来存放它的累计权值和：,Wj = q + pi+1 + qi+1 + pi+2 + + qi+2+ pj + qj. 0=i=j=n,计算,Wj,可以用递推公式,:,W = q /,不是二叉树,只有一个外部结点,Wi+1 = q + pi+1 + qi+1 = W + pi+1 + qi+1 /,有一个内部结点及两个外部结点的二叉树,Wi+2 = Wi+1 + pi+2 + qi+2 /,加一个内部结点和一个外部结点的二叉树,一般地，,Wj = Wj-1 + pj + qj /,再加一个内部结点和一个外部结点,66,构造最优二叉搜索树,对于一棵包括关键码 keyi+1, , keyk-1, keyk, keyk+1, , keyj 的子树Tj，假设设它的根结点为k，i k=j， 它的代价为： Cj = pk+Ck-1+Wk-1+Ckj+Wkj Ck-1是其包含关键码 keyi+1, keyi+2, keyk-1 的左子树Tk-1的代价 Ck-1+Wk-1等于把左子树每个结点的路径长度加1而计算出的代价Ckj是包含关键码 keyk+1, keyk+2, keyj 的右子树Tkj的代价 Ckj + Wkj是把右子树每个结点的路径长度加1之后计算出的代价。,因此，公式 Cj = pk+Ck-1+Wk-1+Ckj+Wkj 说明：整个树的代价等于其左子树的代价加上其右子树的代价，再加上根的权值。,67,4.9 最优二叉搜索树,最优二叉搜索树Tij的平均路长为pij，那么所求的最优值为p1,n。由最优二叉搜索树问题的最优子构造性质可建立计算pij的递归式如下,记wi,jpi,j为m(i,j)，那么m(1,n)=w1,np1,n=p1,n为所求的最优值。计算m(i,j)的递归式为,注意到，,可以得到O(n2)的算法,68,4.10,典型问题,旅行商问题,问题描述：TSP问题Traveling Salesman Problem。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。,69,4.10,典型问题,旅行商问题,方法一：利用排列组合的方法,把所有的路径都计算出来，并逐一比较，选出最小的路径。,虽然该方法在理论上是可行的，但路径的个数与城市的个数成指数增长，当城市个数较大时，该方法的求解时间是难以忍受的，甚至是不可能完成的。以每秒1亿次的计算速度来估算，如果TSP问题包含20个城市时，求解时间长达350年。,70,4.10,典型问题,旅行商问题,1,2,3,4,12,1,8,10,3,2,寻找从,1,出发回到,1,的最短走法。,4,1,2,3,100,1,15,2,3,8,1,2,3,4,2,100,1,3,从1开场贪心，不成功。,71,4.10,典型问题,旅行商问题,方法二：动态规划法,T(V1; V) ：表示从V1出发,经过顶点集合V中的点各一次,再回到点V1的最短路径.,动态规划函数:,T(vi; V) = minDij + T(vj ; V-vj) (vj 属于 V),T(vi; V):就是 从V中任何一点vi出发, 经过V中的点各一次,再回到点 vi的最短路径.,Dij:表示从点vi出发,到某点vj的消耗(有方向性).,注:这是一个递归定义的函数,关键是每次的函数T(vi; V)它所处理的点集逐渐减少.,由于动态规划算法的时间复杂度为O (n22n ) , 空间复杂度为O (n2n ) , 故一般除了很小规模的问题外, 几乎不予采用,多项式时间算法：对规模为,n,的输入，算法在最坏情况下的计算时间为,O(n,k,),72,
展开阅读全文