第4章-动态规划课件.ppt

《第4章-动态规划课件.ppt》由会员分享，可在线阅读，更多相关《第4章-动态规划课件.ppt（47页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析算法设计与分析授课教师：王秋芬授课教师：王秋芬办公地点：办公地点：7307Email:第四章 动态规划目录目录概述概述矩阵连乘问题矩阵连乘问题凸多边形最优三角剖分凸多边形最优三角剖分最长公共子序列问题最长公共子序列问题加工顺序问题加工顺序问题0-1背包问题背包问题最优二叉查找树最优二叉查找树教学目标理解动态规划的思想理解动态规划的思想掌握动态规划、分治法及贪心法的异同掌握动态规划、分治法及贪心法的异同掌握动态规划的基本要素掌握动态规划的基本要素掌握动态规划的设计步骤掌握动态规划的设计步骤通过实例学习，掌握动态规划设计的策略通过实例学习，掌握动态规划设计的策略学习动态规划的意义学习

2、动态规划的意义动态规划问世以来，在经济管理、生产调度、工程技动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用，例如最短路术和最优控制等方面得到了广泛的应用，例如最短路线、库存管理、资源分配、设备更新、排序、装载等线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。问题，用动态规划方法比用其它方法求解更为方便。虽然动态规划主要用于求解以时间划分阶段的动态过虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地

3、引进时间因素，线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方把它视为多阶段决策过程，也可以用动态规划方法方便地求解，因此研究该算法具有很强的实际意义。便地求解，因此研究该算法具有很强的实际意义。动态规划算法通常用于求解具有某种最优性质的问题，动态规划算法通常用于求解具有某种最优性质的问题，动态规划的解题步骤动态规划的解题步骤（1）分析最优解的性质，刻画最优解的结构特）分析最优解的性质，刻画最优解的结构特征征考察是否适合采用动态规划法。考察是否适合采用动态规划法。（2）递归定义最优值（即建立递归式或动态规）递归定义最优值（即建立递归式或动态规划方程

4、）。划方程）。（3）以自底向上的方式计算出最优值，并记录）以自底向上的方式计算出最优值，并记录相关信息。相关信息。（4）根据计算最优值时得到的信息，构造出最）根据计算最优值时得到的信息，构造出最优解。优解。动态规划的基本要素最优子结构性质最优子结构性质子问题重叠性质子问题重叠性质递归算法求解问题时，每次产生的子问题并不总是新问递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题出现多次，这种性质称为子问题的重叠题，有些子问题出现多次，这种性质称为子问题的重叠性质。性质。在应用动态规划时，对于重复出现的子问题，只需在第在应用动态规划时，对于重复出现的子问题，只需在第一次遇到时就加以解决

5、，并把已解决的各个子问题的解一次遇到时就加以解决，并把已解决的各个子问题的解储存在表中，便于以后遇到时直接引用，从而不必重新储存在表中，便于以后遇到时直接引用，从而不必重新求解，可大大提高解题的效率。求解，可大大提高解题的效率。自底向上的求解方式自底向上的求解方式矩阵连乘矩阵连乘问题描述问题描述给定给定n个矩阵个矩阵A1,A2,A3,An，其中，其中Ai与与Ai+1(i=1,2,3,n-1)是可乘的。用加括号的是可乘的。用加括号的方法表示矩阵连乘的次序，不同加括号的方法方法表示矩阵连乘的次序，不同加括号的方法所对应的计算次序是不同的。所对应的计算次序是不同的。以【例以【例4-2】为例讲述】为例

6、讲述最优子结构性质分析最优子结构性质分析算法设计算法设计步骤步骤1：确定合适的数据结构。采用数组：确定合适的数据结构。采用数组m来存放各个子问题的最优值，数组来存放各个子问题的最优值，数组s来存放各个子问题的最优决策来存放各个子问题的最优决策;步骤步骤2：初始化。令：初始化。令mii=0，sii0，其中，其中i=1,2,n；步骤步骤3：循环阶段。：循环阶段。步骤步骤3-1：按照递归关系式计算：按照递归关系式计算2个矩阵个矩阵AiAi+1相乘时的最优值并将其存入相乘时的最优值并将其存入mii+1，同时将最优决策记入，同时将最优决策记入sii+1，i=1,2,n-1；步骤步骤3-2：按照递归关系式

7、计算：按照递归关系式计算3个矩阵个矩阵AiAi+1Ai+2相乘时的最优值并将其存入相乘时的最优值并将其存入mii+2，同时将最优决策记入，同时将最优决策记入sii+2，i=1,2,n-2；依此类推，直到依此类推，直到 步骤步骤3-(n-1)：按照递归关系式计算：按照递归关系式计算n个矩阵个矩阵A1A2An相乘时的最优值并将其相乘时的最优值并将其存入存入m1n，同时将最优决策记入，同时将最优决策记入s1n。至此，至此，m1n即为原问题的最优值。即为原问题的最优值。步骤步骤4：根据数组：根据数组s记录的最优决策信息来构造最优解。记录的最优决策信息来构造最优解。步骤步骤4-1：递归构造：递归构造A1

8、As1n的最优解，直到包含一个矩阵结束；的最优解，直到包含一个矩阵结束；步骤步骤4-2：递归构造：递归构造As1n+1An的最优解，直到包含一个矩阵结束；的最优解，直到包含一个矩阵结束；步骤步骤4-3：将步骤：将步骤4-1和步骤和步骤4-2递归的结果加括号。递归的结果加括号。构造实例求矩阵求矩阵A1（32）、）、A2（25）、）、A3（510）、）、A4（102）和）和A5（23）连乘的最佳计算次序。）连乘的最佳计算次序。表4-6 实例最优值mij 表4-7 实例最优决策sijmijA1A2A3A4A5sijA1A2A3A4A5A1030160132150A101111A20100120132

9、A20224A30100130A3034A4060A404A50A50算法分析语句语句int t=mik+mk+1j+pi-1*pk*pj;为算法为算法MatrixChain的基本语句，最坏情况下该语句的执行次数为的基本语句，最坏情况下该语句的执行次数为O(n3)，故该算法的最坏时间复杂性为，故该算法的最坏时间复杂性为O(n3)。构造最优解的构造最优解的Traceback算法的时间主要取决于递归。最坏算法的时间主要取决于递归。最坏情况下时间复杂性的递归式为：情况下时间复杂性的递归式为：解此递归式得解此递归式得T(n)=O(n)。三角剖分的结构将图将图4-6中的叶子结点中的叶子结点vivi+1与

10、矩阵与矩阵Ai+1(i=0,1,2,3,4)对应，则图对应，则图4-6和图和图4-4所示的二叉树是一样的。因此，所示的二叉树是一样的。因此，n+1边形的三角剖分边形的三角剖分与与n个矩阵连乘的计算次序是一一对应的。可见，个矩阵连乘的计算次序是一一对应的。可见，凸多边形最优剖凸多边形最优剖分问题的解决方法和矩阵连乘问题相似。分问题的解决方法和矩阵连乘问题相似。最优子结构性质分析设设v0vkvn是将是将n+1边形边形P=v0,v1,vn分成三部分分成三部分v0,v1,vk、vk,vk+1,vn和和v0,vk,vn的最佳剖分方法，那么凸多边形的最佳剖分方法，那么凸多边形v0,v1,vk的剖分一定是最

11、优的，的剖分一定是最优的，vk,vk+1,vn的剖分也一定是的剖分也一定是最优的。最优的。设设v0,v1,vn三角剖分的权函数之和为三角剖分的权函数之和为c，v0,v1,vk三角剖分三角剖分的权函数之和为的权函数之和为a，vk,vk+1,vn三角剖分的权函数之和为三角剖分的权函数之和为b，三角，三角形形v0vkvn的权函数为的权函数为w(v0vkvn)，则，则c=a+b+w(v0vkvn)。如果如果c是最小的，则一定包含是最小的，则一定包含a和和b都是最小的。如果都是最小的。如果a不是最小的，则不是最小的，则它所对应的它所对应的v0,v1,vk的三角剖分就不是最优的。那么，对于凸多的三角剖分就

12、不是最优的。那么，对于凸多边形边形v0,v1,vk来说，肯定存在最优的三角剖分，设来说，肯定存在最优的三角剖分，设v0,v1,vk的最优三角剖分对应的权函数之和为的最优三角剖分对应的权函数之和为a(aa)，用，用a代替代替a得到得到c=a+b+w(v0vkvn)，则，则cc，这说明，这说明c对应的对应的v0,v1,vn的三角剖分不的三角剖分不是是最优最优的，产生矛盾。故的，产生矛盾。故a一定是最小的。同理，一定是最小的。同理，b也是最小的。最优子结构也是最小的。最优子结构性质得证。性质得证。最长公共子序列问题基本概念基本概念（1）子序列）子序列给定序列给定序列 X=x1,x2,xn、Z=z1,

13、z2,zk，若，若Z是是X的子序列，当且仅当存在一个严格递增的子序列，当且仅当存在一个严格递增的下标序列的下标序列 i1,i2,ik，对，对j1,2,k有有zj=x。（2）公共子序列）公共子序列给定序列给定序列X和和Y，序列，序列Z是是X的子序列，也是的子序列，也是Y的子序的子序列，则称列，则称Z是是X和和Y的公共子序列。的公共子序列。（3）最长公共子序列）最长公共子序列包含元素最多的公共子序列即为最长公共子序列。包含元素最多的公共子序列即为最长公共子序列。建立最优值的递归关系式设设cij表表示示序序列列Xi和和Yj的的最最长长公公共共子子序序列的长度。则：列的长度。则：算法设计步骤步骤1：确

14、定合适的数据结构。采用数组：确定合适的数据结构。采用数组c来存放各个子问题的最优值，数组来存放各个子问题的最优值，数组b来存放各个子问题最优值的来源。数组来存放各个子问题最优值的来源。数组x1:m和和y1:n分别存放分别存放X序列和序列和Y序列；序列；步骤步骤2：初始化。令：初始化。令ci00，c0j=0，其中，其中0im，0jn；步骤步骤3：循环阶段。根据递归关系式，确定序列：循环阶段。根据递归关系式，确定序列Xi和和Y的最长公共子序列长度；的最长公共子序列长度；步骤步骤3-1：i=1时，求出时，求出c1j，同时记录，同时记录b1j，1jn；步骤步骤3-2：i=2时，求出时，求出c2j，同时

15、记录，同时记录b2j，1jn；依此类推，直到依此类推，直到步骤步骤3-m：i=m时，求出时，求出cmj，同时记录，同时记录bmj，1jn。此时，。此时，cmn便是序列便是序列X和和Y的最长公共子序列长度；的最长公共子序列长度；步骤步骤4：根据二维数组：根据二维数组b记录的相关信息以自底向上的方式来构造最优解；记录的相关信息以自底向上的方式来构造最优解；步骤步骤4-1：初始时，：初始时，i=m，j=n；步骤步骤4-2：如果：如果bij=1，则输出，则输出xi，同时递推到，同时递推到bi-1j-1;如果如果bij=2，则递推到则递推到bij-1;如果如果bij=3，则递推到，则递推到bi-1j；重

16、复执行步骤重复执行步骤4-2，直到，直到i=0或或j=0，此时就可得到序列，此时就可得到序列X和和Y的最长公共子序的最长公共子序列。列。实例构造【例【例4-6】给定序列】给定序列X=A,B,C,B,D,A,B和和Y=B,D,C,A,B,A，求，求它们的最长公共子序列。它们的最长公共子序列。（1）m=7，n=6，将停止条件填入数组，将停止条件填入数组c中，即中，即ci00，c0j=0，其中，其中0im，0jn。（2）当）当i=1时，时，X1=A，最后一个字符为，最后一个字符为A；Yj的的规模从规模从1逐步放大到逐步放大到6，其最后一个字符分别为，其最后一个字符分别为B、D、C、A、B、A；依此类

17、推，直到依此类推，直到i=7。从从i=7，j=6处向前递推处向前递推，找到，找到X和和Y的最长公共子序列为的最长公共子序列为B,C,B,A 最优子结构性质分析将将n个工件的集合看作个工件的集合看作N=1,2,n，设，设P是给定是给定n个工件的个工件的一个最优加工顺序方案，一个最优加工顺序方案，P(i)是该调度方案的第是该调度方案的第i个要调度个要调度的工件的工件(i=1,2,n)。从集合从集合S中的第一个工件开始在机器中的第一个工件开始在机器M1上加工到最后一个上加工到最后一个工件在机器工件在机器M2上加工结束时所耗的时间为上加工结束时所耗的时间为T(S，t)。设集合。设集合S的最优加工顺序中

18、第一个要加工的工件为的最优加工顺序中第一个要加工的工件为i，那么，经过，那么，经过的时间，进入的状态为第一台机器的时间，进入的状态为第一台机器M1开始加工集合开始加工集合S-i中中的工件时，第二台机器的工件时，第二台机器M2需要时间才能空闲下来，这种情需要时间才能空闲下来，这种情况下机器况下机器M2加工完加工完S-i中的工件所需的时间为中的工件所需的时间为T(S-i，t)，其中，即，其中，即t=t2i+maxt-t1i，0，则，则T(S，t)=t1i+T(S-i，t2i+maxt-t1i，0)（4-1）从式（从式（4-1）可以看出，如果）可以看出，如果T(S，t)是最小是最小的，那么肯定包含的

19、，那么肯定包含T(S-i,t2i+maxt-t1i，0)也是最小的。整体最优一定包含子问题也是最小的。整体最优一定包含子问题最优。最优。建立最优值的递归关系式设设T(S，t)表示从集合表示从集合S中的第一个工件开始中的第一个工件开始在机器在机器M1上加工到最后一个工件在机器上加工到最后一个工件在机器M2上加工结束时所耗的最短时间，则：上加工结束时所耗的最短时间，则：当当S为空集时，耗时为为空集时，耗时为M2闲下来所需要的时闲下来所需要的时间，即间，即T(S，t)=t；当当S不为空集时，不为空集时，算法设计算法设计步骤步骤1：令：令N1=i|t1i Cn-1W，表明，表明第第n个物品被装入背包，

20、则个物品被装入背包，则xn=1，前，前n-1个物品被装入容量个物品被装入容量为为W-wn的背包中；否则，第的背包中；否则，第n个物品没有被装入背包，则个物品没有被装入背包，则xn=0，前，前n-1个物品被装入容量为个物品被装入容量为W的背包中。依此类推，的背包中。依此类推，直到确定第直到确定第1个物品是否被装入背包中为止。由此，得到个物品是否被装入背包中为止。由此，得到下面关系式：下面关系式：（4-12）按照式（按照式（4-12），从），从CnW的值向前倒推，即的值向前倒推，即j初始为初始为W，i初始为初始为n，即可确定装入背包的具体物品。，即可确定装入背包的具体物品。构造实例【例例4-8】有

21、有5个个物物品品，其其重重量量分分别别为为2,2,6,5,4，价价值值分分别别为为6,3,5,4,6。背背包包容容量量为为10，物物品品不不可可分分割割，求求装装入入背背包包的的物物品和获得的最大价值。品和获得的最大价值。行行i表示物品，列表示物品，列j表示背包容量，表中数据表示表示背包容量，表中数据表示Cij 012345678910000000000000100666666666200669999999300669999111114400669991011131450066991212151515确定装入背包的具体物品从从CnW的值根据式（的值根据式（4-12）向前推，最终可求出装入背包的

22、具体物）向前推，最终可求出装入背包的具体物品，即问题的最优解。品，即问题的最优解。初始时，初始时，j=W，i=5。如果如果Cij=Ci-1j，说明第，说明第i个物品没有被装入背包，则个物品没有被装入背包，则xi=0；如果如果CijCi-1j，说明第，说明第i个物品被装入背包，则个物品被装入背包，则xi=1，j=j-wi。由于由于CnW=C510=15C410=14，说明物品，说明物品5被装入了背包，被装入了背包，因此因此x5=1，且更新，且更新j=j-w5=10-4=6。由于。由于C4j=C46=9=C36，说明物品，说明物品4没有被装入背包，因此没有被装入背包，因此x4=0；由于；由于C3j

23、=C36=9=C26=9，说明物品，说明物品3没有被装入背包，因此没有被装入背包，因此x3=0。由于由于C2j=C26=9C16=6，说明物品，说明物品2被装入了背包，因此被装入了背包，因此x2=1，且更新，且更新j=j-w2=6-2=4。由于。由于C1j=C14=6C04=0，说，说明物品明物品1被装入了背包，因此被装入了背包，因此x1=1，且更新，且更新j=j-w1=4-2=2。最终可求。最终可求得装入背包的物品的最优解得装入背包的物品的最优解X=(x1,x2,xn)=(1,1,0,0,1)。算法分析在算法在算法KnapSack中，第中，第3个循环是两层嵌套的个循环是两层嵌套的for循环，

24、循环，为此，可选定语句为此，可选定语句if(j2n时，算法需要时，算法需要O(n2n)的计算的计算时间。因此，在这里设计了对算法时间。因此，在这里设计了对算法KnapSack的改进方法，的改进方法，采用该方法可克服这两大缺点。采用该方法可克服这两大缺点。改进算法改进思路改进思路由由Cij的递归式（的递归式（4-11）容易证明：在一般情）容易证明：在一般情况下，对每一个确定的况下，对每一个确定的i(1in)，函数，函数Cij是关是关于变量于变量j的阶梯状单调不减函数（事实上，计算的阶梯状单调不减函数（事实上，计算Cij的递归式在变量的递归式在变量j是连续变量，即为实数时是连续变量，即为实数时仍成

25、立）。跳跃点是这一类函数的描述特征。在仍成立）。跳跃点是这一类函数的描述特征。在一般情况下，函数一般情况下，函数Cij由其全部跳跃点唯一确由其全部跳跃点唯一确定。定。改进步骤（a）对每一个确定的）对每一个确定的i，用一个表，用一个表pi来存储函数来存储函数Cij的全的全部跳跃点。对每一个确定的实数部跳跃点。对每一个确定的实数j，可以通过查找，可以通过查找pi来确定来确定函数函数Cij的值。的值。pi中的全部跳跃点中的全部跳跃点(j，Cij)按按j升序排升序排列。由于函数列。由于函数Cij是关于是关于j的阶梯状单调不减函数，故的阶梯状单调不减函数，故pi中全部跳跃点的中全部跳跃点的Cij值也是递

26、增排列的。值也是递增排列的。（b）pi可通过计算可通过计算pi-1得到。得到。（c）清除受控点。）清除受控点。（d）由此可得，在递归地由）由此可得，在递归地由pi-1计算计算pi时，可先由时，可先由pi-1计算出计算出qi-1，然后合并，然后合并pi-1和和qi-1，并清除其中的受控，并清除其中的受控跳跃点得到跳跃点得到pi。改进后算法的计算时间复杂性为改进后算法的计算时间复杂性为O(minnW，2n)最优二叉查找树定义定义最优二叉查找树是在所有表示有序序列最优二叉查找树是在所有表示有序序列S的二叉的二叉查找树中，具有最小平均比较次数的二叉查找树。查找树中，具有最小平均比较次数的二叉查找树。注

27、意：在查找概率不等的情况下，最优二叉树并注意：在查找概率不等的情况下，最优二叉树并不一定是高度最小的二叉查找树。不一定是高度最小的二叉查找树。最优子结构性质分析将由实结点将由实结点s1,s2,sn和虚结点和虚结点e0,e1,en构成的二叉查构成的二叉查找树记为找树记为T(1，n)。设定元素。设定元素sk作为该树的根结点，作为该树的根结点，1kn。则二。则二叉查找树叉查找树T(1，n)的左子树由实结点的左子树由实结点s1,sk-1和虚结点和虚结点e0,ek-1组成，记为组成，记为T(1，k-1)，而右子树由实结点，而右子树由实结点sk+1,sn和虚结点和虚结点ek,en组成，记为组成，记为T(k

28、+1，n)。如果如果T(1，n)是最优二叉查找树，则左子树是最优二叉查找树，则左子树T(1，k-1)和右子树和右子树T(k+1，n)也是最优二叉查找树。如若不然，假设也是最优二叉查找树。如若不然，假设T(k+1，n)是是比比T(k+1，n)更优的二叉查找树，则更优的二叉查找树，则T(k+1，n)的平均比较次数的平均比较次数小于小于T(k+1，n)的平均比较次数，从而由的平均比较次数，从而由T(1，k-1)、sk和和T(k+1，n)构成的二叉查找树构成的二叉查找树T(1，n)的平均比较次数小于的平均比较次数小于T(1，n)的平的平均比较次数，这与均比较次数，这与T(1，n)是最优二叉树的前提相矛

29、盾。因此，最是最优二叉树的前提相矛盾。因此，最优二叉查找树具有最优子结构性质得证。优二叉查找树具有最优子结构性质得证。建立最优值的递归关系式 (4-21)其中 （4-22）初始时，C(i，i-1)=0;wi(i-1)=qi-1，其中1in。(4-23)式（4-21）和（4-23）即为建立的最优值递归定义式。算法设计步骤步骤1：设计合适的数据结构。设有序序列：设计合适的数据结构。设有序序列S=s1,sn，数组，数组sn存储序列存储序列S中的元素；数组中的元素；数组pn存储序列存储序列S中相应元素的查找中相应元素的查找概率；二维数组概率；二维数组Cn+1n+1，其中，其中Cij表示二叉查找树表示二

30、叉查找树T(i，j)的平均比较次数；二维数组的平均比较次数；二维数组Rn+1n+1，其中，其中Rij表示二叉查表示二叉查找树找树T(i，j)中作为根结点的元素在序列中作为根结点的元素在序列S中的位置。数组中的位置。数组qn存储存储虚结点虚结点e0,e1,en的查找概率。为了提高效率，不是每次计算的查找概率。为了提高效率，不是每次计算C(i，j)时都计算时都计算wij的值，而是把这些值存储在二维数组的值，而是把这些值存储在二维数组Wij中；中；步骤步骤2：初始化。设置：初始化。设置Cii-1=0；Wii-1=qi-1；步骤步骤3：循环阶段。采用自底向上的方式逐步构造最优二叉查找树；：循环阶段。采

31、用自底向上的方式逐步构造最优二叉查找树；步骤步骤3-1：字符集规模为：字符集规模为1的时候，即的时候，即Sij=si，i=1,2,n且且j=i，显然这种规模的子问题有显然这种规模的子问题有n个，即首先要构造出个，即首先要构造出n棵最优二叉查找棵最优二叉查找树树T(1，1)，T(2，2),T(n，n)。依据公式。依据公式(4-20)(4-22)，很容，很容易求得易求得Wii和和Cii。同时，对于所构造的。同时，对于所构造的n棵最优二叉查找树，棵最优二叉查找树，它们的根分别记为：它们的根分别记为：R11=1，R22=2,Rnn=n；依此类推，构造出字符集依此类推，构造出字符集Sij中含中含3个字符

32、的最优二叉查找树、含个字符的最优二叉查找树、含4个字个字符的最优二叉查找树，直到符的最优二叉查找树，直到步骤步骤3-n:字符集规模为字符集规模为n的时候，即的时候，即S1n=s1,s2,sn，显然这种规，显然这种规模的子问题有模的子问题有1个，即要构造出个，即要构造出1棵最优二叉查找树棵最优二叉查找树T(1，n)。依据公式。依据公式(4-21)，求得，求得Wij，然后在整数，然后在整数1,2n中选择适当的中选择适当的k值，使得成立。值，使得成立。同时，记录该树的根同时，记录该树的根R1n=k；步骤步骤4：最优解的构造。：最优解的构造。从从Rij中保存的最优二叉查找子树中保存的最优二叉查找子树T

33、(i，j)的根结点信息，可构造出问的根结点信息，可构造出问题的最优解。当题的最优解。当R1n=k时，则元素时，则元素sk即为所求的最优二叉查找树的即为所求的最优二叉查找树的根结点。此时，需要计算两个子问题：求左子树根结点。此时，需要计算两个子问题：求左子树T(1，k-1)和右子树和右子树T(k+1，n)的根结点信息。如果的根结点信息。如果R1k-1=i，则元素，则元素si即为即为T(1，k-1)的的根结点元素。依此类推，将很容易由根结点元素。依此类推，将很容易由R中记录的信息构造出问题的最优中记录的信息构造出问题的最优解。解。构造实例【例【例4-11】设】设5个有序元素的集合为个有序元素的集合

34、为s1,s2,s3,s4,s5,查找概率查找概率p=；叶结点元素；叶结点元素e0,e1,e2,e3,e4,e5，查找概率，查找概率q=。试构造。试构造5个有序元素的最优二叉查找树。个有序元素的最优二叉查找树。根据R中的信息构造最优解步骤步骤1：由于：由于R15=2，即，即k=2，最优二叉查找树，最优二叉查找树T(1，5)的根结点为的根结点为s2；步骤步骤2：求出：求出T(1，5)的左子树的左子树T(1，k-1)=T(1，1)的根结点为的根结点为s1；步骤步骤3：求出：求出T(1，5)的右子树的右子树T(k+1，5)=T(3，5)的根结点为的根结点为s5；步骤步骤4：求出子树：求出子树T(3，5)的左子树的左子树T(3，4)的根结点为的根结点为s4；由此构造出如图由此构造出如图4-9所示的最优二叉查找树所示的最优二叉查找树 算法分析由算法描述容易看出，语句由算法描述容易看出，语句if(Cik-1+Ck+1j)Cij)对算法的运行时间贡对算法的运行时间贡献最大，因此，可选该语句作为基本语句。献最大，因此，可选该语句作为基本语句。对于固定的对于固定的t值，该语句需要的计算时间为值，该语句需要的计算时间为O(j-i)=O(t)，因此，它总的运行时间为，因此，它总的运行时间为