第5章 动态规划.ppt

1、2018/10/6,第5章 动态规划,2018/10/6,1. 多阶段决策问题多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一阶段i以后的行为仅依赖于i阶段的过程状态，而与i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决策称为多阶段决策过程(multistep decision process) 。最优化问题：问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。 多阶段决策的最优化问题就是：求能够获得问题最优解的决策序列最优决策序列。,5.1 一般方法,2018/10/

2、6,2. 多阶段决策过程的求解策略 1）枚举法：穷举可能的决策序列，从中选取可以获得最优解的决策序列 2）动态规划20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问题的新方法动态规划。动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、

3、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。,2018/10/6,3. 最优性原理(Principle of Optimality)过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。利用动态规划求解问题的前提1) 证明问题满足最优性原理如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题2) 获得问题状态的递推关系式获得各阶段间的递推关系式是解决问题的关键。,2018/10/6,例5.1 多段图问题多段图G=(V,E)是一个有向图，且具有特性:结点：

4、结点集V被分成k2个不相交的集合Vi，1ik，其中V1和Vk分别只有一个结点s(源点)和t(汇点) 每一集合Vi定义图中的一段。边： 所有的边(u,v)均具有如下性质： 若E，则该边将是从某段i指向i+1段，即若uVi，则vVi1, 1ik1。 每条边(u,v)均附有成本c(u,v)。s到t的路径：从第1段开始，至第2段、第3段、最后在第k段终止。路径的成本是这条路径上边的成本和。多段图问题：求由s到t的最小成本路径。,2018/10/6,2018/10/6,多段图问题的多阶段决策过程：生成从s到t的最小成本路径是在k-2个阶段（除s和t外）进行某种决策的过程：从s开始，第i次决策决定Vi+1

5、(1ik-2)中的哪个结点在从s到t的最短路径上。 最优性原理对多段图问题成立假设s,v2,v3,vk-1,t是一条由s到t的最短路径。 初始状态：s 初始决策：(s,v2)， v2V2 初始决策产生的状态：v2则，其余的决策：v3,.,vk-1相对于v2将构成一个最优决策序列最优性原理成立。反证：若不然，设v2,q3,qk-1,t是一条由v2到t的更短的路径，则s, v2,q3,qk-1,t将是比s,v2,v3,vk-1,t更短的从s到t的路径。与假设矛盾。故，最优性原理成立,2018/10/6,例5.20/1背包问题 KNAP(l,j,X)目标函数：约束条件：0/1背包问题：KNAP(1,

6、n,M),2018/10/6,最优性原理对0/1背包问题成立：设y1,y2,yn是x1,x2,xn的0/1值最优序列。若y10, KNAP(2,n,M)是初始决策产生的状态。则y2,yn相对于KNAP(2,n,M)将构成一个最优序列。否则，y1,y2,yn将不是KNAP(1,n,M)的最优解若y11, KNAP(2,n,Mw1)是初始决策产生的状态。则y2,yn相对于KNAP(2,n,Mw1)将构成一个最优序列。否则，设存在另一0/1序列z1,z2,zn,使得 且则序列y1,z2,zn将是一个对于KNAP(1,n,M)具有更大效益值的序列,与假设矛盾故，最优性原理成立,2018/10/6,4.

7、 动态规划模型的基本要素 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素： 1) 阶段阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1,2,n表示。,2018/10/6,2） 状态状态(state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有无后向性，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。描述状态的变量称状态变量(state variable)。变量允许取值的范围称允

8、许状态集合(set of admissible states)。用xk表示第k阶段的状态变量，它可以是一个数或一个向量。用Xk表示第k阶段的允许状态集合。状态变量简称为状态,2018/10/6,3）决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为决策(decision) 。描述决策的变量称决策变量(decision variable)。变量允许取值的范围称允许决策集合(set of admissible decisions)。用uk(xk)表示第k阶段处于状态xk时的决策变量，它是xk的函数，用Uk(xk)表示了xk的允许决策集合。决策变量简称决策。,

9、2018/10/6,4）策略决策组成的序列称为策略(policy)。由初始状态x1开始的全过程的策略记作p1,n(x1)，即p1,n(x1)=u1(x1), u2(x2),.，un(xn)。由第k阶段的状态xk开始到终止状态的后部子过程的策略记作pk,n(xk)，即pk,n(xk)=uk(xk),uk+1(xk+1),.，un(xn)。类似地，由第k到第j阶段的子过程的策略记作 pk,j(xk)=uk(xk),uk+1(xk+1),.，uj(xj)。对于每一个阶段k的某一给定的状态xk，可供选择的策略pk,j(xk)有一定的范围，称为允许策略集合(set of admissible polic

10、ies).,2018/10/6,5) 状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程(equation of state)表示这种演变规律，写作,2018/10/6,6) 指标函数和最优值函数指标函数(objective function)是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段k到阶段n的指标函数用Vk,n(xk,pk,n(xk)表示，k=1,2,.,n。能够用动态规划解决的问题的指标函数应具有可分离性，即Vk,n可表为xk,uk,Vk+1, n 的函数，记为：,2018/10/6,7.最优策略和最优轨线使指标函数Vk,n达到

11、最优值的策略是从k开始的后部子过程的最优策略，记作pk,n*=uk*,un*,p1,n*又是全过程的最优策略，简称最优策略(optimal policy)。从初始状态x1(=x1*)出发，过程按照p1,n*和状态转移方程演变所经历的状态序列x1*,x2*,xn+1*称最优轨线(optimal trajectory)。,2018/10/6,5. 递推策略 1）向前处理法列出根据xi+1,xn的最优决策序列求取xi决策值的关系式。从最后一个阶段，逐步向前递推求出各阶段的决策值。决策序列x1,x2,xn就是问题的最优解。,xn-1,1,xn-1,pn-1,xn,2018/10/6,例5.3 利用向前

12、处理法求解0/1背包问题设gi(x)是KNAP(i+1,n,X)的最优解。 g0(M)：KNAP(1,n,M)的最优解。由于x1的取值等于1或0,可得：g0(M)=maxg1(M),g1(M-w1)+p1 对于某个xi，xi等于1或0，则有：gi(X)=maxgi+1(X),gi+1(X-wi+1)+pi+1初始值：0 X0 gn(X) = - X0,2018/10/6,例5.4 利用向前处理法求解k段图问题设 V2，1j2p2,|V2|=p2;是由 到t的最短路径，则s到t的最短路径是s | V2,1j2p2中最短的那条路径。若s,v2,v3,vi,vk-1,t是s到t的一条最短路径，vi是

13、其中的一个中间点，则s,v2,v3,vi和 vi,vk-1,t分别是由s到vi和vi到t的最短路径（最优性原理）从Vi中的结点ji到t的最短路径将是：min( | Vi+1,1ji+1pi+1),2018/10/6,2） 向后处理法列出根据x1,xi-1的最优决策序列求取xi决策值的关系式。从第一个阶段，逐步向后递推求出各阶段的决策值。决策序列x1,x2,xn就是问题的最优解。,2018/10/6,例5.5 0/1背包问题（向后处理策略）设fi(x)是KNAP(1,i,X)的最优解。则，fn(M) = KNAP(1,n,M)向后递推关系式：fi(X)=maxfi-1(X),fi-1(X-wi)

14、+pi初始值：0 X0 f0(X) = - X0,2018/10/6,例5.6 k段图问题（向后处理策略）设 Vk-1，1jk-1pk-1，|Vk-1|=pk-1;是由s到 的最短路径，则s到t的最短路径是 t | Vk-1,1jk-1pk-1中最短的那条路径。若s,v2,v3,vi,vk-1,t是s到t的一条最短路径，vi是其中的一个中间点，则s,v2,v3,vi和 vi,vk-1,t分别是由s到vi和vi到t的最短路径（最优性原理）从s到Vi中的结点ji的最短路径将是：min( | Vi ,1jipi),2018/10/6,动态规划的基本思想： （1）动态规划方法的关键在于正确写出基本的递

15、推关系式和恰当的边界条件。要做到这一点，必须将问题的过程分成几个相互联系的阶段，恰当选择状态变量，决策变量和定义最优值函数，从而把一个大问题化成一簇同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题的最优解，就是整个问题的最优解。 （2）在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前的效益和未来效益综合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。 （3）在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状

16、态的函数，故最优策略所经的各段状态便可逐次变换得到，从而确定最优路线。,2018/10/6,关于动态规划求解策略的进一步说明 采用枚举法：若问题的决策序列由n次决策构成，而每次决策有p种选择，则可能的决策序列将有pn个。 利用动态规划策略的求解过程中保存了所有子问题的最优解，而舍去了所有不能导致问题最优解的次优决策序列 动态规划：可能有多项式的计算复杂度。,2018/10/6,与非线性规划相比，动态规划的优点： （1）易于确定全局最优解。动态规划方法是一种逐步改善法，它把原问题化为一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少的多，约束集合也要简单得多。 （2）能得到一簇解，有

17、利于分析结果 （3）能利用经验，提高求解的效率。动态规划方法反映了过程逐段演变的前后联系，较之非线性规划与实际过程联系得更紧密。 不足之处： （1）没有一个统一的标准模型可供应用。 （2）应用的局限性。要求状态变量满足“无后效性”条件，不少实际问题在取其自然特征作为状态变量往往不能满足这条件。 （3）在数值求解中，存在“维数障碍”。在计算机中，每递推一段，必须把前一段的最优值函数在相应的状态集合上的全部值存入内存中。当维数增大时，所需的内存量成指数倍增长。,2018/10/6,5.2 多段图问题,1. 问题的描述 在多段图中求从s到t的一条最小成本的路径，可以看作是在k-2个段作出某种决策的结

18、果。 第i次决策决定Vi+1中的哪个结点在这条路径上，这里 1ik-2； 最优性原理对多段图问题成立,2018/10/6,2. 向前处理策略求解 设 P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径， COST(i,j)是这条路径的成本。1) 向前递推式2) 递推过程 第k-1段 c(j,t) ECOST(k-1,j) = jVK-2计算COST(k-2,j)=minc(j,l)+cost(k-1,l) COST(1,S),2018/10/6,l1,l2,. . .,lpi+1,t,j,Vi,Vi+1,2018/10/6,5段图,2018/10/6,各递推结果 第4段 COST(4,9

19、) = c(9,12) = 4COST(4,10) = c(10,12) = 2COST(4,11) = c(11,12) = 5 第3段 COST(3,6) = min6+COST(4,9),5+COST(4,10) = 7COST(3,7) = min4+COST(4,9),3+COST(4,10) = 5COST(3,8) = min5+COST(4,10),6+COST(4,11) = 7 第2段 COST(2,2) = min4+COST(3,6) , 2+COST(3,7), 1+COST(3,8) = 7COST(2,3) = 9COST(2,4) = 18COST(2,5) =

20、 15 第1段 COST(1,1) = min9+COST(2,2),7+COST(2,3), 3+COST(2,4),2+COST(2,5)= 16 S到t的最小成本路径的成本 16,2018/10/6, 最小路径的求取记 D(i,j)每一COST(i,j)的决策即，使c(j,L)+COST(i+1,L)取得最小值的L值。例：D(3,6) = 10, D(3,7)= 10 D(3,8) = 10D(2,2) = 7, D(2,3) = 6,D(2,4) = 8, D(2,5) = 8 D(1,1) = 2根据D(1,1)的决策值向后递推求取最小成本路径： v2=D(1,1)=2 v3 = D

21、(2,D(1,1) = 7 v4 = D(3,D(2,D(1,1) = D(3,7) = 10 故由s到t的最小成本路径是：1271012,2018/10/6,3) 算法描述 结点的编号规则源点s编号为1,然后依次对V2、V3Vk-1中的结点编号，汇点t编号为n。目的：使对COST和D的计算仅按n-1,n-2,1的次序计算即可，无需考虑标示结点所在段的第一个下标。 算法描述,2018/10/6,算法5.1 多段图的向前处理算法procedure FGRAPH(E,k,n,P)/输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c(i,j)是边的成本。P(1:k)存储最小成本路径/re

22、al COST(n) 0; integer D(n-1),P(k),r,j,k,nfor jn-1 to 1 by -1 do /计算COST(j)/设r是具有性质：E且使c(j,r)+COST(r)取最小值的结点COST(j)c(j,r) + COST(r)D(j) r /记录决策值/repeatP(1)1; P(k)nfor j2 to k-1 do /找路径上的第j个结点/P(j) D(P(j-1) /回溯求出该路径/repeatend FGRAPH,2018/10/6,算法的时间复杂度若G采用邻接表表示，总计算时间为：,2018/10/6,3. 向后处理策略求解设 BP(i,j)是一条

23、从源点s到Vi中的结点j的最小成本路径， BCOST(i,j)是这条路径的成本。1) 向后递推式2) 递推过程 第2段 c(1,j) EBCOST(2,j) = ,2018/10/6,5段图,2018/10/6,各递推结果 第2段 BCOST(2,2) = 9BCOST(2,3) = 7BCOST(2,4) = 3BCOST(2,5) = 2 第3段 BCOST(3,6) = minBCOST(2,2)+4,BCOST(2,3)+2 = 9BCOST(3,7) = minBCOST(2,2)+2,BCOST(2,3)+7,BCOST(2,5)+11 = 11BCOST(3,8) = minBC

24、OST(2,4)+11, BCOST(2,5)+8 = 10 第4段 BCOST(4,9) = minBCOST(3,6)+6,BCOST(3,7)+4 = 15BCOST(4,10) = minBCOST(3,6)+5,BCOST(3,7)+3,BCOST(3,8)+5 = 14BCOST(4,11) = minBCOST(3,8)+6 = 16 第5段 BCOST(5,12) = minBCOST(4,9)+4,BCOST(4,10)+2,BCOST(4,11)+5= 16S到t的最小成本路径的成本 16,2018/10/6, 最小路径的求取记 BD(i,j)每一COST(i,j)的决策即

25、，使COST(i-1,l)+c(l,j)取得最小值的l值。例：BD(3,6) = 3, BD(3,7)= 2 ,BD(3,8) = 5BD(4,9) = 6, BD(4,10) = 7, BD(4,11) = 8BD(5,12) = 10根据D(5,12)的决策值向前递推求取最小成本路径： v4 = BD(5,12)=10 v3 = BD(4,BD(5,12) = 7 v2 = BD(3,BD(4,BD(5,12) = BD(3,7) = 2 故由s到t的最小成本路径是：1271012,2018/10/6,5段图,2018/10/6,算法4.2 多段图的向后处理算法procedure BGRA

26、PH(E,k,n,P)/输入是按段的顺序给结点编号的，有n个结点的k段图。E是边集，c(i,j)是边的成本。P(1:k)带出最小成本路径/real BCOST(n); integer BD(n-1),P(k),r,j,k,n,BCOST(1) 0for j2 to n do /计算BCOST(j)/设r是具有E且使BCOST(r)+ c(r,j)取最小值性质的结点BCOST(j) BCOST(r)+ c(r,j)BD(j) r /记录决策值/repeatP(1)1; P(k)nfor jk-1 to 2 by -1 do /找路径上的第j个结点/P(j) D(P(j+1) /回溯求出该路径/r

27、epeatend BGRAPH,2018/10/6,4. 多段图问题的应用实例将n个资源分配给r个项目的问题：如果把j个资源，0jn，分配给项目i，可以获得N(i,j)的净利。问题：如何将这n个资源分配给r个项目才能获得最大可能的净利。转换成一个多段图问题。,2018/10/6,用r1段图描述该问题：段： 1到r之间的段i表示项目i。结点：i=1时，只有一个结点源点s =V(1,0)当2ir时，每段有n+1个结点，每个结点具有形式V(i,j)：表示到项目i之前为止，共把j个资源分配给了项目1,2,i-1汇点t=V(r+1,n)边的一般形式：,jL,1ir成本： 当jL且1ir时，边赋予成本N(

28、i,l-j),表示给项目i分配l-j个资源所可能获得的净利。 当jn且i=r时，此时的边为：,该边赋予成本：,2018/10/6,实例：将4个资源分配给3个项目。构成一个4段图。问题的解：资源的最优分配方案是由s到t的一条最大成本的路径给出改变边成本的符号，从而将问题转换成为求取最小成本路径问题。,2018/10/6,5.3 每对结点之间的最短路径,1. 问题描述设G=(V,E)是一个有n个结点的有向图，无负环，C是G的成本邻接矩阵，C中元素有：0 ，i jc(i,j)= 边的成本，ij且E(G) ，ij且其中，1i，jn每对结点之间的最短路径问题：求满足下述条件的矩阵A，A中的任一元素A(i

29、,j)代表结点i到结点j的最短路径长度。,2018/10/6,分析：利用单源最短路径算法求解 计算n个结点的单源最短路径。 时间复杂度：(n3)利用动态规划策略求解将求解G中每对结点之间的最短路径问题转化成一个多阶段决策过程。 决策什么？ 最优性原理对于该问题是否成立？,2018/10/6,2. 动态规划求解策略 1）最优性原理对于每对结点之间的最短路径问题成立对G的一条由i到j的最短路径（假设该路径中不包含环），设k是该路径上的一个中间结点：i,.,k,j由i到k的最短路径 k是中间结点 由k到i的最短路径则，由i到k和k到j的两条子路径将分别是由i到k和由k到j的最短路径。否则i,.,k,

30、j也将不是由i到j的最短路径。故，最优性原理对于该问题成立。,2018/10/6,2）多阶段决策过程设k是由i到j的最短路径上编号（假设所有n个结点依次有从1到n的编号）最高的中间结点：i,.,k,jk是编号最高的中间结点则由i到k的子路径上将不会有比编号k-1更大的结点；同理，由k到i的子路径上也将不会有比编号k-1更大的结点。构造多阶段决策过程：对由i到j的最短路径，首先决策哪一个结点是该路径上具有最大编号的中间结点k，然后再去求取由i到k和由k到j的最短路径其中应不包含比k-1还大的中间结点。,2018/10/6,3）递推关系式记Ak(i,j)表示从i到j并且不经过比k还大的结点的最短路

31、径长度。则，A(i,j) = An(i,j)即，由i到j的最短路径不通过比编号n还大的结点。注：该路径可以经过结点n，也可以不经过结点n。 若该路径经过结点n，则An(i,j) An-1(i,n) + An-1(n,j) 若该路径不经过结点n，则An(i,j) An-1(i,j)故可得，An(i,j) = minAn-1(i,j) ，An-1(i,n) + An-1(n,j)不经过n结点 经过n结点,2018/10/6,对任意的k， k1，有，Ak(i,j) = minAk-1(i,j) ，Ak-1(i,k) + Ak-1(k,j)不经过结点k 刚好经过结点k初值：A0(i,j)= C(i,j

32、)，1in，1jn递推计算： A1(i,j), A2(i,j), An(i,j)= A (i,j),2018/10/6,3. 算法描述 算法5.3 每对结点之间的最短路径长度procedure ALL-PATHS(COST,A,n)/COST(n,n)是n结点图的成本邻接矩阵；A(i,j)是结点vi到vj的最短路径的成本；COST(i,i)=0,1in/integer I,j,k,n; real COST(n,n),A(n,n)for i1 to n dofor j1 to n doA(i,j) COST(i,j) /用COST(i,j)对A0赋初值/repeatrepeatfor k1 to

33、 n dofor i1 to n dofor j1 to n doA (i,j) minA (i,j) ，A (i,k) + A (k,j)repeatrepeatrepeatend ALL-PATHS,2018/10/6,算法的设计说明 1） Ak(i,k) = Ak-1(i,k) Ak(k,j) = Ak-1(k,j) Ak(i,j) minAk-1(i,j), Ak(i,k) + Ak-1(k,j) Ak(i,j) minAk-1(i,j), Ak-1(i,k) + Ak-1(k,j) 在算法的计算过程中取消了A的上标，并保证了每次计算的 Ak(i,j)即为minAk-1(i,j), A

34、k-1(i,k) + Ak-1(k,j) 2）如何求每对结点之间的路径？,2018/10/6,例5.8 有向图如图所示,求图中所有结点间的最短路径矩阵A：,注： A(i,j) = 表明G中从i到j没有有向路径,2018/10/6,性能分析计算时间注：该时间与A的值无关：for k1 to n do 迭代n次for i1 to n do 迭代n次for j1 to n do 迭代n次A (i,j) minA (i,j) ，A (i,k) + A (k,j)repeatrepeatrepeat,2018/10/6,的处理设M是E中最大成本的一条边的成本，则An(i,j) (n-1)*M，则表明G中

35、没有由i到j的有向路径。,2018/10/6,4.4 最优二分检索树,1. 问题的描述 1）二分检索树定义二分检索树是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有：的左子树的所有元素比根结点中的元素小；的右子树的所有元素比根结点中的元素大；的左子树和右子树也是二分检索树。注：二分检索树要求树中所有结点的元素值互异,2018/10/6,对于一个给定的标识符集合，可能有若干棵不同的二分检索树:,不同形态的二分检索树对标识符的检索性能是不同的。,2018/10/6,2）二分检索树的检索算法5.4 SEARCH(T,X,i)/为X检索二分检索树T，如果X不在T中，则置i=

36、0；否则i有IDENT(i)=X/iTwhile i0 docase:XIDENT(i):iLCHILD(i) /若X小于IDENT(i)，则在左子树中继续查找/:XIDENT(i):return /X等于IDENT(i)，则返回/:XIDENT(i):iRCHILD(i) /若X大于IDENT(i)，则在右子树中继续查找/endcaserepeatend SEARCH,2018/10/6,二分检索树的性能特征 例 图(a)：最坏情况下查找标识符loop需要做4次比较；成功检索平均需要做12/5次比较; 图(b):最坏情况下查找标识符loop/while需要做3次比较；成功检索平均需要做11/

37、5次比较 查找概率可以期望不同标识符的检索频率是不同的。如PforPwhile Ploop 不成功检索可以期望不成功检索出现的频率也是不同的。,2018/10/6,2018/10/6,3）最优二分检索树问题设给定的标识符集合是a1,a2,an，并假定a1a2 an 。设，P(i)是对ai检索的概率，Q(i)是正被检索的标识符X恰好满足： ai Xai+1，0in（设a0=-,an+1=+)时的概率，即一种不成功检索情况下的概率。 则 表示所有成功检索的概率表示所有不成功检索的概率考虑所有可能的成功和不成功检索情况，共2n+1种可能的情况，有,2018/10/6,二分检索树内结点：代表成功检索情

38、况，刚好有n个外结点：代表不成功检索情况，刚好有n1个关于a1,a2,an的最优二分检索树含义如下：,2018/10/6,二分检索树的预期成本预期成本：算法对于所有可能的成功检索情况和不成功检索情况，平均所要做的比较次数。根据期望值计算方法，平均检索成本每种情况出现的概率该情况下所需的比较次数平均检索成本的构成：成功检索成分不成功检索成分 成功检索：在l级内结点终止的成功检索，需要做l次比较运算（基于二分检索树结构）。该级上的任意结点ai的检索的成本为：P(i)*level(ai) ；其中，level(ai) = 结点ai 的级数=l,2018/10/6,不成功检索：不成功检索的等价类：每种不

39、成功检索情况定义了一个等价类，共有n+1个等价类Ei(0in)。其中， E0=X|Xa1Ei=X|aiXai+1(1in)En=X|Xan若Ei处于l级，则算法需作l-1次迭代。则，l级上的外部结点的不成功检索的成本分担额为：Q(i)*(level(Ei)-1)则预期总的成本公式表示如下：,2018/10/6,最优二分检索树问题：求一棵使得预期成本最小的二分检索树例5.9 标识符集合（a1,a2,a3）=（do,if,stop）。可能的二分检索树如下所示。成 功 检 索：3种不成功情况：4种,2018/10/6,2018/10/6,1) 等概率：P(i)=Q(i)=1/7cost(a) = 1

40、5/7cost(b) = 13/7 cost(c) = 15/7cost(d) = 15/7cost(e) = 15/72）不等概率：P(1)=0.5 P(2)=0.1 P(3)=0.05Q(0)=0.15 Q(1)=0.1 Q(2)=0.05 Q(3)=0.05cost(a) = 2.65cost(b) = 1.9 cost(c) = 1.5 cost(d) = 2.15cost(e) = 1.6,最优,最优,2018/10/6,2. 多阶段决策过程把构造二分检索树的过程看成一系列决策的结果。决策的策略：决策树根，如果a1,a2,an存在一棵二分检索树，ak是该树的根，则内结点a1,a2,a

41、k-1和外部结点E0,E1,Ek-1将位于根ak的左子树中，而其余的结点将位于右子树中。,ak,由ak1, ak+2, ,an及Ek,Ek+1,En构成的二分检索树,由a1,a2,ak-1及E0,E1,Ek-1构成的二分检索树,2018/10/6,定义：含义： 左、右子树的预期成本左、右子树的根处于第一级 左、右子树中所有结点的级数相对于子树的根测定，而相对于原树的根少1,2018/10/6,记：则，原二分检索树的预期成本可表示为：COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n)最优二分检索树：COST(T)有最小值 最优性原理成立若T最优二分检索树，则

42、COST(L)和COST(R)将分别是包含a1,a2,ak-1和E0,E1,Ek-1、及ak1, ak+2, ,an和Ek,Ek+1,En的最优二分检索(子)树。记由ai+1,ai+2,aj和Ei,Ei+!,Ej构成的二分检索树的成本为C(i,j)，则对于最优二分检索树T有，COST(L) = C(0,k-1)COST(R) = C(k,n),2018/10/6,则，对任何C(i,j)有，向前递推过程： 首先计算所有j-i=1的C(i,j) 然后依次计算j-i=2,3,n的C(i,j)。 C(0,n)=最优二分检索树的成本。初始值C(i,i) = 0W(i,i) = Q(i)，0in,2018

43、/10/6,最优二分检索树的构造 在计算C(i,j)的过程中，记下使之取得最小值的k值，即树Tij的根，记为R(i,j)。 依据R(0,n)，推导树的形态,例.10 设n=4,且(a1,a2,a3,a4)=(do,if,read,while)。 设P(1:4) = (3,3,1,1)，Q(0:4) = (2,3,1,1,1) (概率值“扩大”了16倍) 初始：W(i,i)=Q(i) C(i,i)=0 R(i,i)=0,且有，W(i,j)=P(j)+Q(j)+W(i,j-1),2018/10/6,且有，W(i,j)=P(j)+Q(j)+W(i,j-1) j-i=1阶段的计算：W(0,1)=P(1

44、)+Q(1)+W(0,0) = 8C(0,1)=W(0,1)+minC(0,0)+C(1,1) = 8R(0,1) = 1W(1,2)=P(2)+Q(2)+W(1,1) = 7C(1,2)=W(1,2)+minC(1,1)+C(2,2) = 7R(1,2) = 2W(2,3)=P(3)+Q(3)+W(2,2) = 3C(2,3)=W(2,3)+minC(2,2)+C(3,3) = 3R(2,3) = 3W(3,4)=P(4)+Q(4)+W(3,3) = 3C(3,4)=W(3,4)+minC(3,3)+C(4,4) = 3R(3,4) = 4,2018/10/6,j-i=2 w(0,2)=p(

45、2)+q(2)+w(0,1)=12 c(0,2)=w(0,2)+minc(0,1)+c(2,2),c(0,0)+c(1,2)=19 r(0,2)=1 w(1,3)=p(3)+q(3)+w(1,2)=9 c(1,3)=w(1,3)+minc(1,1)+c(2,3) ,c(1,2)+c(3,3)=12 r(1,3)=2 w(2,4)=p(4)+q(4)+w(2,3)=5 c(2,4)=w(1,4)+minc(2,2)+c(3,4) ,c(2,3)+c(4,4)=8 r(2,4)=3/4,且有，W(i,j)=P(j)+Q(j)+W(i,j-1),2018/10/6,j-i=3 w(0,3)=P(3)

46、+q(3)+w(0,2)=14 c(0,3)=w( 0,3 )+minc(0,0)+c(1,3), c(0,1)+c(2,3) , c(0,2)+c(3,3)=25 r(0,3)=2 w(1,4)= P(4)+q(4)+w(1,3)=11 c(1,4)= w( 1,4 )+minc(1,1)+c(2,4), c(1,2)+c(3,4) , c(1,3)+c(4,4)=19 r(1,4)=2 j-i=4 w(0,4)= P(4)+q(4)+w(0,3)=16 c(0,4)= w(0,4)+minc(0,0)+c(1,4), c(0,1)+c(2,4) , c(0,2)+c(3,4),c(0,3)

47、+c(4,4)=32 r(0,4)=2,2018/10/6,C(i,j),W(i,j),R(i,j)计算结果则，C(0,4)=32 二分检索树：T04=2 =T01(左子树），T24(右子树） T01=1 =T00(左子树），T11(右子树） T24=3 =T22(左子树），T34(右子树）,2018/10/6,树的形态,if,do,read,while,2018/10/6,3.计算时间 当j-i=m时，有n-m+1个C(i,j)要计算 C(i,j)的计算：(m)每个C(i,j)要求找出m个量中的最小值。则，n-m+1个C(i,j)的计算时间：(nm-m2)对所有可能的m，总计算时间为：一种改

48、进措施（克努特）：最优的kR(i,j-1),R(i+1,j),2018/10/6,4.算法描述procedure OBST(P,Q,n)/给定n个标识符a1a2an。已知成功检索的概率P(i),不成功检索概率Q(i), 0in。算法对于标识符ai+1,aj计算最优二分检索树Tij的成本C(i,j)、根R(i,j)、权W(i,j) /real P(1:n),Q(1:n),C(0:n,0:n),W(0:n,0:n);integer R(0:n,0:n)for i0 to n-1 do(W(i,i), R(i,i), C(i,i)(Q(i),0,0) /置初值/(W(i,i+1), R(i,i+1), C(i,i+1)(Q(i)+Q(i+1)+P(i+1),i+1, Q(i)+Q(i+1)+P(i+1) repeat /含有一个结点的最优树/(W(n,n), R(n,n), C(n,n)(Q(n),0,0) for m2 to n do /找有m个结点的最优树/for i0 to n-m doji+mW(i,j) W(i,j-1)+P(j)+Q(j)k区间R(i,j-1), R(i+1,j)中使C(i,l-1)+C(l,j)取最小值的l值 /Knuth结论 C(i,j) W(i,j)+C(i,k-1)+C(k,j)R(i,j)krepeatrepeatend OBST,