计算机算法基础(第四章)

《计算机算法基础(第四章)》由会员分享，可在线阅读，更多相关《计算机算法基础(第四章)（97页珍藏版）》请在金锄头文库上搜索。

1、第四章第四章 动态规划动态规划4.1 一般方法一般方法1. 多阶段决策问题多阶段决策问题 多阶段决策过程多阶段决策过程：问题的活动过程分为若干相互联系的阶段，任一：问题的活动过程分为若干相互联系的阶段，任一阶段阶段i以后的行为仅依赖于以后的行为仅依赖于i阶段的过程状态，而与阶段的过程状态，而与i阶段之前的过程如何阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决策称为多阶段决策过程策称为多阶段决策过程(multistep decision process) 。 最优化问题最优化问题：问题的每一阶段可能有

2、多种可供选择的决策，必须从：问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所导致的问题的结果可能不同。导致的问题的结果可能不同。 多阶段决策的最优化问题多阶段决策的最优化问题就是：求能够获得问题最优解的决策序列就是：求能够获得问题最优解的决策序列最优决策序列。最优决策序列。2. 多阶段决策过程的求解策略多阶段决策过程的求解策略1）枚举法）枚举法 穷举穷举可能的决策序列，从中选取可以获得最优解的决策序列可能的决策序列，从中选取可以获得最优解的决策序列2）动态规划）动态规划 2

3、0世纪世纪50年代初美国数学家年代初美国数学家R.E.Bellman等人在研究多阶段决策等人在研究多阶段决策过程的优化问题时，提出了著名的过程的优化问题时，提出了著名的最优化原理最优化原理(principle of optimality)，把把多阶段多阶段过程转化为一系列过程转化为一系列单阶段单阶段问题，创立了解决这问题，创立了解决这类过程优化问题的新方法类过程优化问题的新方法动态规划动态规划。 动态规划动态规划(dynamic programming)是是运筹学运筹学的一个分支，是求解的一个分支，是求解决策过程决策过程(decision process)最优化的数学方法。最优化的数学方法。

4、应用领域：动态规划问世以来，在经济管理、生产调度、工程技应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。方法求解更为方便。3. 最优性原理最优性原理(Principle of Optimality) 过程的过程的最优决策序列最优决策序列具有如下性质：无论过程的具有如下性质：无论过程的初始状初始状态态和和初始决策初始决策是什么，其余的

5、决策都必须相对于初始决策所是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。产生的状态构成一个最优决策序列。 利用动态规划求解问题的前提利用动态规划求解问题的前提 1) 证明问题满足最优性原理证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明用动态如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题规划方法有可能解决该问题 2) 获得问题状态的递推关系式获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键。获得各阶段间的递推关系式是解决问题的关键。例例4.1 多段图问题多段图问题多段图多段图G=(V,E)是一个有向图，且具

6、有特性是一个有向图，且具有特性: 结点结点：结点集：结点集V被分成被分成k22个不相交的集合个不相交的集合V Vi i，1ik1ik， 其中其中V V1 1和和V Vk k分别只有一个结点分别只有一个结点s(s(源点源点) )和和t(t(汇点汇点) )。 每一集合每一集合V Vi i定义图中的定义图中的一段一段。 边边： 所有的边所有的边(u,v)(u,v)均具有如下性质：均具有如下性质： 若若EE，则则 该边将是从某段该边将是从某段i i指向指向i+1i+1段，即若段，即若uVuVi i，则，则vVvVi i1 1, , 1ik 1ik1 1。 每条边每条边(u,v)(u,v)均附有成本均附

7、有成本c(u,v)c(u,v)。 s s到到t t的路径的路径：从第：从第1 1段开始，至第段开始，至第2 2段、第段、第3 3段、段、最后、最后 在第在第k k段终止。路径的段终止。路径的成本成本是这条路径上边的成本是这条路径上边的成本 和。和。 多段图问题多段图问题：求由：求由s s到到t t的的最小成本路径最小成本路径。12345678910111297324227111181456356425V1V2V3V4V55段图 多段图问题的多段图问题的多阶段决策过程多阶段决策过程：生成从：生成从s到到t的最小成本路径的最小成本路径是在是在k-2个阶段（除个阶段（除s和和t外）进行某种决策的过程

8、：从外）进行某种决策的过程：从s开始，开始，第第i次次决策决定决策决定Vi+1(1ik-2)中的哪个结点在从中的哪个结点在从s到到t的最短路径上。的最短路径上。最优性原理对多段图问题成立最优性原理对多段图问题成立 假设假设s,v2,v3,vk-1,t是一条由是一条由s到到t的最短路径。的最短路径。 初始状态初始状态：s 初始决策初始决策：(s,v2)， v2VV2 2 初始决策产生的状态初始决策产生的状态：v2 则，其余的决策则，其余的决策：v3,.,vk-1相对于相对于v2将构成一个最优决策序将构成一个最优决策序列列最优性原理成立。最优性原理成立。 反证反证：若不然，设：若不然，设v2,q3

9、,qk-1,t是一条由是一条由v2到到t的更短的路径，的更短的路径，则则s, v2,q3,qk-1,t将是比将是比s,v2,v3,vk-1,t更短的从更短的从s到到t的路径。的路径。与假设矛盾。与假设矛盾。 故，最优性原理成立故，最优性原理成立n例例4.20/1背包问题背包问题 KNAP(l,j,X) 目标函数目标函数： 约束条件约束条件： 0/1背包问题：背包问题：KNAP(1,n,M) 最优性原理对最优性原理对0/1背包问题成立：背包问题成立： 设设y1,y2,yn是是x1,x2,xn的的0/1值最优序列。值最优序列。 若若y10, KNAP(2,n,M)是初始决策产生的状态。则是初始决策

10、产生的状态。则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)具有更大效益具有更大效益值的序列。值的序列。 故，最优性原理成立故，最优性原理成立4. 动态

11、规划模型的基本要素动态规划模型的基本要素一个多阶段决策过程最优化问题的动态规划模型通常包含以一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：下要素：1) 阶段阶段 阶段阶段(step)是对整个过程的自然划分。通常根据时间顺是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用阶段变量一般用k=1,2,.,n表示。表示。2） 状态状态 状态状态(state)表示每个阶段开始时过程所处的自然状况。它应表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有该能够描述过程的

12、特征并且具有无后向性无后向性，即当某阶段的状态给，即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，即每个状态都是过去历史的一个完整总结。通常还要求状态是直即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。接或间接可以观测的。 描述状态的变量称描述状态的变量称状态变量状态变量(state variable)。变量允许取值变量允许取值的范围称允许的范围称允许状态集合状态集合(set of admissible states)。用。用xk表示第表示第k阶段的状态变量，它可以是一个数或一个向

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

14、示第表示第k阶段处于状态阶段处于状态xk时的决策变量，它是时的决策变量，它是xk的函数，用的函数，用Uk(xk)表示了表示了xk的允许决策集合。的允许决策集合。 决策变量简称决策。决策变量简称决策。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),u

15、k+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 policies)，用，用P1,n(x1),Pk,n(xk),Pk,j(xk)表示。表示。5) 状态转移方程状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，在确定性过程中，一旦某阶段的

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

17、即Vk,n可表为可表为xk,uk,Vk+1, n 的函数，记为：的函数，记为：7.最优策略和最优轨线最优策略和最优轨线 使指标函数使指标函数Vk,n达到最优值的策略是从达到最优值的策略是从k开始的后部子过开始的后部子过程的最优策略，记作程的最优策略，记作pk,n*=uk*,.un*,p1,n*又是全过程的最又是全过程的最优策略，简称最优策略优策略，简称最优策略(optimal policy)。从初始状态从初始状态x1(=x1*)出发，过程按照出发，过程按照p1,n*和状态转移方程演变所经历的和状态转移方程演变所经历的状态序列状态序列x1*,x2*,.,xn+1*称最优轨线称最优轨线(optim

18、al trajectory)。5. 递推策略递推策略1）向前处理法）向前处理法 列出根据列出根据xi+1,xn的最优决策序列求取的最优决策序列求取xi决策决策值的关系式。值的关系式。 从最后一个阶段，逐步从最后一个阶段，逐步向前向前递推求出各阶段的递推求出各阶段的决策值。决策序列决策值。决策序列x1,x2,xn就是问题的最优解。就是问题的最优解。 xn-1,1xn-1,pn-1xn 例例4.3 利用向前处理法求解利用向前处理法求解0/1背包问题背包问题 设设gi(x)是是KNAP(i+1,n,X)的最优解。的最优解。 g0(M)：KNAP(1,n,M)的最优解。由于的最优解。由于x1的取值等于

19、的取值等于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 0 gn(X) = - X0 例例4.4 利用向前处理法求解利用向前处理法求解k段图问题段图问题 设设 V2，1j2p2,|V2|=p2; 是由是由 到到t的最短路径，的最短路径，则s到到t的最短路径是的最短路径是 s | V2,1j2p2中最短的那条路径。中最短的那条路径。 若若s,v2,v3,vi,vk-1,t是是s到到t的一条最短路径，的一条最短

20、路径，vi是其中是其中的一个中的一个中间点，点，则s,v2,v3,vi和和 vi,vk-1,t分分别是由是由s到到vi和和vi到到t的最短路径（最的最短路径（最优性原理）性原理） 从从Vi中的中的结点点ji到到t的最短路径将是：的最短路径将是： min( | Vi+1,1ji+1pi+1)2） 向后处理法向后处理法 列出根据列出根据x1,xi-1的最优决策序列求取的最优决策序列求取xi决决策值的关系式。策值的关系式。 从第一个阶段，逐步从第一个阶段，逐步向后向后递推求出各阶段的递推求出各阶段的决策值。决策序列决策值。决策序列x1,x2,xn就是问题的最优解。就是问题的最优解。 例例4.5 0/

21、1背包问题（向后处理策略）背包问题（向后处理策略） 设设fi(x)是是KNAP(1,i,X)的最优解。的最优解。 则，则，fn(M) = KNAP(1,n,M) 向后递推关系式：向后递推关系式： fi(X)=maxfi-1(X),fi-1(X-wi)+pi 初始值：初始值： 0 X0 0 f0(X) = - X0 例例4.6 k段图问题（向后处理策略）段图问题（向后处理策略） 设设 Vk-1，1jk-1pk-1，|Vk-1|=pk-1; 是由是由s到到 的最短路径，的最短路径，则s到到t的最短路径是的最短路径是 t | Vk-1,1jk-1pk-1中最短的那条路中最短的那条路径。径。 若若s,

22、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+1,1ji+1pi+1)动态规划的基本思想：动态规划的基本思想：（1）动态规划方法的关键在于正确写出基本的递推关系式）动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件。要做到这一点，必须将问题的过程分和恰当的边界条件。要做到这一点，必须将问题的过程分成

23、几个相互联系的阶段，恰当选择状态变量，决策变量和成几个相互联系的阶段，恰当选择状态变量，决策变量和定义最优值函数，从而把一个大问题化成一族同类型的子定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题的最优解，就是整优化结果，依次进行，最后一个子问题的最优解，就是整个问题的最优解。个问题的最优解。（2）在多阶段决策过程中，动态规划方法是既把当前一段）在多阶段决策

24、过程中，动态规划方法是既把当前一段和未来各段分开，又把当前的效益和未来效益综合起来考和未来各段分开，又把当前的效益和未来效益综合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。考虑的，与该段的最优选择答案一般是不同的。（3）在求整个问题的最优策略时，由于初始状态是已知的，）在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经的各而每段的决策都是该段状态的函数，故最优策略所经的各段状态便可逐次变换得到，从而确定最优路线。段状态便可逐次变换得到，从而确定最优

25、路线。关于动态规划求解策略的进一步说明关于动态规划求解策略的进一步说明采用枚举法：若问题的决策序列由采用枚举法：若问题的决策序列由n次决策构成，而每次次决策构成，而每次决策有决策有p种选择，则可能的决策序列将有种选择，则可能的决策序列将有pn个。个。利用动态规划策略的求解过程中保存了所有子问题的最优利用动态规划策略的求解过程中保存了所有子问题的最优解，而舍去了所有不能导致问题最优解的次优决策序列解，而舍去了所有不能导致问题最优解的次优决策序列动态规划：可能有多项式的计算复杂度。动态规划：可能有多项式的计算复杂度。与非线性规划相比，动态规划的优点：与非线性规划相比，动态规划的优点：（1）易于确定

26、全局最优解。动态规划方法是一种逐步改善法，）易于确定全局最优解。动态规划方法是一种逐步改善法，它把原问题化为一系列结构相似的最优化子问题，而每个子它把原问题化为一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少的多，约束集合也要简单得多。问题的变量个数比原问题少的多，约束集合也要简单得多。（2）能得到一族解，有利于分析结果）能得到一族解，有利于分析结果（3）能利用经验，提高求解的效率。动态规划方法反映了过）能利用经验，提高求解的效率。动态规划方法反映了过程逐段演变的前后联系，较之非线性规划与实际过程联系得程逐段演变的前后联系，较之非线性规划与实际过程联系得更紧密。更紧密。不足之处不

27、足之处：（1）没有一个统一的标准模型可供应用。）没有一个统一的标准模型可供应用。（2）应用的局限性。要求状态变量满足）应用的局限性。要求状态变量满足“无后效性无后效性”条件，条件，不少实际问题在取其自然特征作为状态变量往往不能满足这不少实际问题在取其自然特征作为状态变量往往不能满足这条件。条件。（3）在数值求解中，存在）在数值求解中，存在“维数障碍维数障碍”。在计算机中，每递。在计算机中，每递推一段，必须把前一段的最优值函数在相应的状态集合上的推一段，必须把前一段的最优值函数在相应的状态集合上的全部值存入内存中。当维数增大时，所需的内存量成指数倍全部值存入内存中。当维数增大时，所需的内存量成指

28、数倍增长。增长。4.2 多段图问题多段图问题1. 问题的描述问题的描述 在多段图中求从在多段图中求从s到到t的一条最小成本的路径，可以看的一条最小成本的路径，可以看 作是在作是在k-2个段作出某种决策的结果。个段作出某种决策的结果。 第第i次决策决定次决策决定Vi+1中的哪个结点在这条路径上，这里中的哪个结点在这条路径上，这里 1ik-2ik-2； 最优性原理对多段图问题成立最优性原理对多段图问题成立2. 向前处理策略求解向前处理策略求解 设设 P(i,j)是一条从是一条从Vi中的结点中的结点j到汇点到汇点t的最小成本路径，的最小成本路径， COST(i,j)是这条路径的成本。是这条路径的成本

29、。 1) 向前递推式向前递推式 2) 递推过程递推过程 第第k-1k-1段段 c(j,t) EE COST(k-1,j) = l1l2.lpi+1tjViVi+112345678910111297324227111181456356425V1V2V3V4V55段图各递推结果各递推结果第第4段段 COST(4,9) = c(9,12) = 4 COST(4,10) = c(10,12) = 2 COST(4,11) = c(11,12) = 5第第3段段 COST(3,6) = min6+COST(4,9),5+COST(4,10) = 7 COST(3,7) = min4+COST(4,9),

30、3+COST(4,10) = 5 COST(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) = 7 COST(2,3) = 9 COST(2,4) = 18 COST(2,5) = 15第第1段段 COST(1,1) = min9+COST(2,2),7+COST(2,3), 3+COST(2,4),2+COST(2,5) = 16S到到t的最小成本路径的成本的最小成本路径的成本 16 最小路径的求取最小路径的求取 记记 D(i,j)D(i,j)

31、每一每一COST(i,j)COST(i,j)的决策的决策 即，使即，使c(j,l)+COST(i+1,l)c(j,l)+COST(i+1,l)取得取得最小值最小值的的l l值。值。 例：例：D(3,6) = 10, D(3,7)= 10 D(3,8) = 10D(3,6) = 10, D(3,7)= 10 D(3,8) = 10 D(2,2) = 7, D(2,3) = 6,D(2,4) = 8,D(2,5) = 8 D(2,2) = 7, D(2,3) = 6,D(2,4) = 8,D(2,5) = 8 D(1,1) = 2 D(1,1) = 2 根据根据D(1,1)D(1,1)的决策值的决

32、策值向后向后递推求取最小成本路径：递推求取最小成本路径： v v2 2=D(1,1)=2=D(1,1)=2 v v3 3 = D(2,D(1,1) = 7 = D(2,D(1,1) = 7 v v4 4 = D(3,D(2,D(1,1) = D(3,7) = 10 = D(3,D(2,D(1,1) = D(3,7) = 10 故由故由s s到到t t的的最小成本路径最小成本路径是：是：12710121271012 3) 算法描述算法描述 结点的编号规则结点的编号规则 源点源点s s编号为编号为1 1, ,然后依次对然后依次对V V2 2、V V3 3V Vk-1k-1中的结点编号，中的结点编号

33、，汇点汇点t t编号为编号为n n。 目的：使对目的：使对COSTCOST和和D D的计算仅按的计算仅按n-1,n-2,n-1,n-2,1,1的次序计的次序计算即可，算即可，无需考虑无需考虑标示结点所在标示结点所在段段的第一个下标。的第一个下标。 算法描述算法描述算法算法4.1 多段图的向前处理算法多段图的向前处理算法 procedure FGRAPH(E,k,n,P) /输入是按段的顺序给结点输入是按段的顺序给结点编号编号的，有的，有n个结点的个结点的k段图。段图。E是边是边 集，集，c(i,j)是边是边的成本。的成本。P(1:k)带出最小成本路径带出最小成本路径/ real COST(n)

34、; integer D(n-1),P(k),r,j,k,n COST(n)0 for 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 /记录决策决策值/ repeat P(1)1; P(k)n for j2 to k-1 do /找路径上的第找路径上的第j个个结点点/ P(j) D(P(j-1) /回溯求出回溯求出该路径路径/ repeat end FGRAPH算法的时间复杂度算法的时间复杂度 若若G采用邻接表表示，总计算时间为：

35、采用邻接表表示，总计算时间为：3. 向后处理策略求解向后处理策略求解 设设 BP(i,j)是一条从源点是一条从源点s到到Vi中的结点中的结点j的最小成本路径，的最小成本路径， BCOST(i,j)是这条路径的成本。是这条路径的成本。 1) 向后递推式向后递推式 2) 递推过程递推过程 第第2 2段段 c(1,j) EE BCOST(2,j) = 12345678910111297324227111181456356425V1V2V3V4V55段图各递推结果各递推结果第第2段段 BCOST(2,2) = 9 BCOST(2,3) = 7 BCOST(2,4) = 3 BCOST(2,5) = 2

36、第第3段段 BCOST(3,6) = minBCOST(2,2)+4,BCOST(2,3)+2 = 9 BCOST(3,7) = minBCOST(2,2)+2,BCOST(2,3)+7, BCOST(2,5)+11 = 11 BCOST(3,8) = minBCOST(2,4)+11, BCOST(2,5)+8 = 10第第4段段 BCOST(4,9) = minBCOST(3,6)+6,BCOST(3,7)+4 = 15 BCOST(4,10) = minBCOST(3,6)+5,BCOST(3,7)+3, BCOST(3,8)+5 = 14 BCOST(4,11) = minBCOST(

37、3,8)+6 = 16第第5段段 BCOST(5,12) = minBCOST(4,9)+4,BCOST(4,10)+2, BCOST(4,11)+5 = 16S到到t的最小成本路径的成本的最小成本路径的成本 16 最小路径的求取最小路径的求取 记记 BD(i,j)BD(i,j)每一每一COST(i,j)COST(i,j)的决策的决策 即，使即，使COST(i-1,l)+c(l,j)COST(i-1,l)+c(l,j)取得取得最小值最小值的的l l值。值。 例：例：BD(3,6) = 3, BD(3,7)= 2 ,BD(3,8) = 5BD(3,6) = 3, BD(3,7)= 2 ,BD(3

38、,8) = 5 BD(4,9) = 6, BD(4,10) = 7, BD(4,11) = 8 BD(4,9) = 6, BD(4,10) = 7, BD(4,11) = 8 BD(5,12) = 10 BD(5,12) = 10 根据根据D(5,12)D(5,12)的决策值的决策值向前向前递推求取最小成本路径：递推求取最小成本路径： v v4 4 = BD(5,12)=10= BD(5,12)=10 v v3 3 = BD(4,BD(5,12) = 7 = BD(4,BD(5,12) = 7 v v2 2 = BD(3,BD(4,BD(5,12) = BD(3,7) = 2 = BD(3,B

39、D(4,BD(5,12) = BD(3,7) = 2 故由故由s s到到t t的的最小成本路径最小成本路径是是：12710121271012 12345678910111265434227111181456356425V1V2V3V4V55段图算法算法4.2 多段图的向后处理算法多段图的向后处理算法 procedure BGRAPH(E,k,n,P) /输入是按段的顺序给结点输入是按段的顺序给结点编号编号的，有的，有n个结点的个结点的k段图。段图。E是边是边 集，集，c(i,j)是边是边的成本。的成本。P(1:k)带出最小成本路径带出最小成本路径/ real BCOST(n); integer

40、 BD(n-1),P(k),r,j,k,n BCOST(1)0 for j2 to n do /计算算BCOST(j)/ 设r是具有是具有E且使且使BCOST(r)+ c(r,j)取最小取最小值性性质的的结点点 BCOST(j) BCOST(r)+ c(r,j) BD(j) r /记录决策决策值/ repeat P(1)1; P(k)n for jk-1 to 2 by -1 do /找路径上的第找路径上的第j个个结点点/ P(j) D(P(j+1) /回溯求出回溯求出该路径路径/ repeat end BGRAPH4. 多段图问题的应用实例多段图问题的应用实例 将将n个资源分配给个资源分配给

41、r个项目的问题：如果把个项目的问题：如果把j个资源，个资源，0jnjn，分配给项目分配给项目i i，可以获得可以获得N(i,j)N(i,j)的净利。的净利。 问题：如何将这问题：如何将这n个资源分配给个资源分配给r个项目才能获得最大可个项目才能获得最大可能的净利。转换成一个多段图问题。能的净利。转换成一个多段图问题。 用用r1段图段图描述该问题：描述该问题： 段段： 1到到r之间的段之间的段i表示项目表示项目i。 结点结点： i=1时，只有一个结点时，只有一个结点源点源点s =V(1,0)V(1,0) 当当2irir时，每段有时，每段有n+1n+1个结点，每个结点具有形式个结点，每个结点具有形

42、式 V(i,j)V(i,j)：表示到项目表示到项目i i之前为止，共把之前为止，共把j j个资源分配给了个资源分配给了 项目项目1,2,1,2,i-1,i-1 汇点汇点t t=V(r+1,n)=V(r+1,n) 边的一般形式边的一般形式：,jl,1irjl,1ir 成本：成本： 当当jljl且且1ir1ir时，边时，边赋予成本赋予成本 N(i,l-j),N(i,l-j),表示给项目表示给项目i i分配分配l-jl-j个资源所可能获得的净利。个资源所可能获得的净利。 当当jnjn且且i=ri=r时，此时的边为：时，此时的边为：,该边赋该边赋 予成本：予成本：实例：将实例：将4个资源分配给个资源分

43、配给3个项目。构成一个个项目。构成一个4段图。段图。 问题的解：资源的最优分配方案是由问题的解：资源的最优分配方案是由s到到t的一条的一条最大成本最大成本的路径给出的路径给出改变边成本的改变边成本的符号符号，从而将问题转换成为求取最小成本路径问题。，从而将问题转换成为求取最小成本路径问题。4.3 每对结点之间的最短路径每对结点之间的最短路径1. 问题描述问题描述 设设G=(V,E)是一个有是一个有n个结点的有向图，个结点的有向图，C是是G的成本邻接矩阵，的成本邻接矩阵，C中元素有：中元素有： 0 ，i j c(i,j)= 边边的成本，的成本，ij且且E(G) ，ij且且 其中，其中，1i，jn

44、 每对结点之间的最短路径问题每对结点之间的最短路径问题：求满足下述条件的矩阵：求满足下述条件的矩阵A，A中的任一元素中的任一元素A(i,j)代表结点代表结点i到结点到结点j的的最短路径长度最短路径长度。分析：分析：n 利用利用单源最短路径单源最短路径算法求解算法求解 计算计算n个结点的单源最短路径。个结点的单源最短路径。 时间复杂度时间复杂度：(n(n3 3) )n利用利用动态规划动态规划策略求解策略求解 将求解将求解G G中每对结点之间的最短路径问题转化成一个中每对结点之间的最短路径问题转化成一个多多阶段决策过程阶段决策过程。 决策什么？决策什么？ 最优性原理对于该问题是否成立？最优性原理对

45、于该问题是否成立？2. 动态规划求解策略动态规划求解策略1）最优性原理对于每对结点之间的最短路径问题成立最优性原理对于每对结点之间的最短路径问题成立 对对G的一条由的一条由i到到j的最短路径（假设该路径中不包含环），的最短路径（假设该路径中不包含环），设设k是该路径上的一个中间结点：是该路径上的一个中间结点： i,.,k,j 由由i到到k的最短路径的最短路径 k是中间结点是中间结点 由由k到到i的最短路径的最短路径 则，由则，由i到到k和和k到到j的两条的两条子路径子路径将分别是由将分别是由i到到k和由和由k到到j的最短路径。否则的最短路径。否则i,.,k,j也将不是由也将不是由i到到j的最短

46、路径。的最短路径。 故，最优性原理对于该问题成立。故，最优性原理对于该问题成立。2）多阶段决策过程多阶段决策过程 设设k是由是由i到到j的最短路径上编号（假设所有的最短路径上编号（假设所有n个结点依次有从个结点依次有从1到到n的编号）最高的中间结点：的编号）最高的中间结点： i,.,k,j k是编号最高的中间结点是编号最高的中间结点 则由则由i到到k的子路径上将不会有比编号的子路径上将不会有比编号k-1更大的结点；同理，更大的结点；同理，由由k到到i的子路径上也将不会有比编号的子路径上也将不会有比编号k-1更大的结点。更大的结点。 构造构造多阶段决策过程多阶段决策过程：对：对由由i到到j的最短

47、路径，首先决策哪一个的最短路径，首先决策哪一个结点是该路径上具有结点是该路径上具有最大编号最大编号的中间结点的中间结点k，然后再去求取由然后再去求取由i到到k和由和由k到到j的最短路径的最短路径其中应不包含比其中应不包含比k-1还大的中间结点。还大的中间结点。3）递推关系式）递推关系式 记记Ak(i,j)表示从表示从i到到j并且不经过比并且不经过比k还大的结点的还大的结点的最短最短路径长度路径长度。则，。则， A(i,j) = An(i,j) 即，即，由由i到到j的最短路径不通过比编号的最短路径不通过比编号n还大的结点。还大的结点。 注：该路径可以注：该路径可以经过经过结点结点n，也可以也可以

48、不经过不经过结点结点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结点结点 对任意的对任意的k， k11，有，有， Ak(i,j) = minAk-1(i,j) ，Ak-1(i,k) + Ak-1(k,j) 不经过结点不经过结点k 刚好经过结点刚好经过结点k 初值初值： A0(i,j)= C(i,j)，1ini

49、n，1jn1jn递推计算：递推计算： A1(i,j), A2(i,j), An(i,j)= A (i,j)3. 算法描述算法描述算法算法4.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 do for j1 to n do A(i,j) COST(i

50、,j) /用用COST(i,j)对A0赋初初值/ repeat repeat for k1 to n do for i1 to n do for j1 to n do A (i,j) minA (i,j) ，A (i,k) + A (k,j) repeat repeat repeat end ALL-PATHS算法的设计说明算法的设计说明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) 在

51、算法的计算过程中取消了在算法的计算过程中取消了A A的上标，并保证了每次计算的上标，并保证了每次计算 的的 Ak(i,j)即为即为 minAk-1(i,j), Ak-1(i,k) + Ak-1(k,j) 2）如何求每对结点之间的路径？如何求每对结点之间的路径？例例4.8 有向图如图所示有向图如图所示A012310411260233 0A1123104112602337 70A212310462602337 70A312310462502337 70642 113v1v2v312310411260233 0求图中所有结点间的最短路径矩阵求图中所有结点间的最短路径矩阵A：注：注： A(i,j) =

52、 表明表明G G中从中从i i到到j j没有有向路径没有有向路径性能分析性能分析 计算时间计算时间 注：该时间注：该时间与与A 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) repeat repeat repeat 的处理 设M是E中最大成本的一条边的成本，则An(i,j) (n-1)*M，则表明G中没有由i到j的有向路径。4.4 最优二分检索树最优二分检索树1. 问题的描述问题的描述1）二分检索树定义）

53、二分检索树定义 二分检索树是一棵二分检索树是一棵二元树二元树，它或者为，它或者为空空，或者其每个，或者其每个结点含有一个可以比较大小的数据元素，且有：结点含有一个可以比较大小的数据元素，且有：的的左子树左子树的所有元素比根结点中的元素小；的所有元素比根结点中的元素小；的的右子树右子树的所有元素比根结点中的元素大；的所有元素比根结点中的元素大；的左子树和右子树也是二分检索树。的左子树和右子树也是二分检索树。 注：注： 二分检索树要求树中所有结点的元素值二分检索树要求树中所有结点的元素值互异互异ifforwhilerepeatloopifforrepeatloopwhile 对于一个给定的对于一个

54、给定的标识符标识符集合，可能有集合，可能有若干棵若干棵不同的二不同的二分检索树分检索树: :不同形态的二分检索树对标识符的不同形态的二分检索树对标识符的检索性能检索性能是是不同不同的。的。2）二分检索树的检索）二分检索树的检索 算法算法4.4 SEARCH(T,X,i) /为为X检索二分检索树检索二分检索树T，如果如果X不在不在T中，则置中，则置i=0； 否则否则i有有IDENT(i)=X/ iT while i0 do case :XIDENT(i):iLCHILD(i) /若若X小于小于IDENT(i)，则在左子在左子树中中继续查找找/ :XIDENT(i):return /X等于等于ID

55、ENT(i)，则返回返回/ :XIDENT(i):iRCHILD(i) /若若X大于大于IDENT(i)，则在右子在右子树中中继续查找找/ endcase repeat end SEARCH二分检索树的性能特征二分检索树的性能特征 例例 图图(a)： 最坏情况最坏情况下查找标识符下查找标识符loop需要需要做做4次比较；次比较； 成功检索成功检索平均平均需要做需要做12/5次比较次比较; 图图(b)： 最坏情况最坏情况下查找标识符下查找标识符loop/while需要做需要做3次比较；次比较； 成功检索成功检索平均平均需要做需要做11/5次比较次比较 查找概率查找概率 可以期望不同标识符的可以期

56、望不同标识符的检索频率检索频率是不同的。如是不同的。如 PforPwhile Ploop 不成功检索不成功检索 可以期望不成功检索出现的可以期望不成功检索出现的频率频率也是不同的。也是不同的。3）最优二分检索树问题）最优二分检索树问题 设给定的标识符集合是设给定的标识符集合是a1,a2,an，并假定并假定a1a2 an 。 设，设，P(i)是对是对ai检索的概率检索的概率，Q(i)是正被检索的标识符是正被检索的标识符X恰好满足：恰好满足： ai Xai+1，0inin（设（设a a0 0=-,a=-,an+1n+1=+)=+)时的概率，即一种不成功检索时的概率，即一种不成功检索情况下的概率。情

57、况下的概率。则则 表示所有成功检索的概率表示所有成功检索的概率 表示所有不成功检索的概率表示所有不成功检索的概率 考虑所有可能的成功和不成功检索情况，共考虑所有可能的成功和不成功检索情况，共2n+12n+1种可能的情况，有种可能的情况，有 二分检索树二分检索树 内结点内结点：代表成功检索情况，刚好：代表成功检索情况，刚好有有n n个个 外结点外结点：代表不成功检索情况，刚好有：代表不成功检索情况，刚好有n n1 1个个 关于关于a1,a2,an的的最优二分检索树最优二分检索树含义如下：含义如下：二分检索树的预期成本二分检索树的预期成本 预期成本预期成本：算法对于所有可能的成功检索情况和不成功检

58、：算法对于所有可能的成功检索情况和不成功检索情况，平均所要做的比较次数。根据期望值计算方法，索情况，平均所要做的比较次数。根据期望值计算方法， 平均检索成本平均检索成本每种情况出现的每种情况出现的概率概率该情况下所需的比较该情况下所需的比较次数次数 平均检索成本的平均检索成本的构成构成：成功检索成分成功检索成分不成功检索成分不成功检索成分 成功检索成功检索：在：在l级内结点终止的成功检索，需要做级内结点终止的成功检索，需要做l次比次比较运算（基于二分检索树结构）。该级上的任意结点较运算（基于二分检索树结构）。该级上的任意结点ai的的成本成本检索的成本分担额检索的成本分担额为：为： P(i)*l

59、evel(ai) ； 其中，其中，level(ai) = 结点结点ai 的级数的级数=l 不成功检索： 不成功检索的不成功检索的等价类等价类：每种不成功检索情况定义了一个等：每种不成功检索情况定义了一个等价类，共有价类，共有n+1个等价类个等价类Ei(0in)。其中，其中， E0=X|Xa0 Ei=X|aiXai+1(1in) En=X|Xan 若若Ei处于处于l级，则算法需作级，则算法需作l-1次迭代。则，次迭代。则，l级上的外部结点级上的外部结点的的不成功检索的成本分担额不成功检索的成本分担额为：为： Q(i)*(level(Ei)-1) 则预期总的成本公式表示如下：则预期总的成本公式表示

60、如下：最优二分检索树问题最优二分检索树问题： 求一棵使得求一棵使得预期成本预期成本最小最小的二分检索树的二分检索树例例4.9 标识符集合（标识符集合（a1,a2,a3）=（do,if,stop）。）。可能的二可能的二分检索树如下所示。分检索树如下所示。n 成成 功功 检检 索：索：3种种n 不成功情况：不成功情况：4种种stopdoifdoifstopstopifdoifdostopdostopif(a)(b)(c)(d)(e) 1) 等概率等概率：P(i)=Q(i)=1/7 cost(a) = 15/7 cost(b) = 13/7 最优最优 cost(c) = 15/7 cost(d) =

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

62、二存在一棵二分检索树，分检索树，ak是该树的根，则内结点是该树的根，则内结点a1,a2,ak-1和外部结和外部结点点E0,E1,Ek-1将位于将位于根根ak的左子树中，而其余的结点将位的左子树中，而其余的结点将位于右子树中。于右子树中。ak由ak1, ak+2, ,an及Ek,Ek+1,En构成的二分检索树由a1,a2,ak-1及E0,E1,Ek-1构成的二分检索树定义：定义：含义：含义： 左、右子树左、右子树的的预期成本预期成本左、右子树的左、右子树的根根处于处于第一级第一级 左、右子树中所有结点的级数相对于子树的根测定，而相对于原左、右子树中所有结点的级数相对于子树的根测定，而相对于原树的

63、根少树的根少1记：记： 则，原二分检索树的预期成本可表示为：则，原二分检索树的预期成本可表示为： COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n) 最优二分检索树最优二分检索树：COST(T)有最小值有最小值最优性原理成立最优性原理成立 若若T最优二分检索树，则最优二分检索树，则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构成的二分检索树的

64、成本为构成的二分检索树的成本为C(i,j)，则对于最优二分检索则对于最优二分检索树树T有，有， COST(L) = C(0,k-1) COST(R) = C(k,n)则，则，对任何对任何C(i,j)有，有，向前递推过程：向前递推过程： 首先计算所有首先计算所有j-i=1的的C(i,j) 然后依次计算然后依次计算j-i=2,3,n的的C(i,j)。 C(0,n)=最优二分检索树的成本。最优二分检索树的成本。 初始值初始值 C(i,i) = 0 W(i,i) = Q(i)，0inin最优二分检索树的构造最优二分检索树的构造 在计算在计算C(i,j)的过程中，记下使之取得最小值的的过程中，记下使之取

65、得最小值的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)j-i=1阶段的计算：阶段的计算： W(0,1)=P(1)+Q(1)+W(0,0) = 8 C(0,1)=W(0,1)+minC(0

66、,0)+C(1,1) = 8 R(0,1) = 1 W(1,2)=P(2)+Q(2)+W(1,1) = 7 C(1,2)=W(1,2)+minC(1,1)+C(2,2) = 7 R(1,2) = 2 W(2,3)=P(3)+Q(3)+W(2,2) = 3 C(2,3)=W(2,3)+minC(2,2)+C(3,3) = 3 R(2,3) = 3 W(3,4)=P(4)+Q(4)+W(3,3) = 3 C(3,4)=W(3,4)+minC(3,3)+C(4,4) = 3 R(3,4) = 4C(i,j),W(i,j),R(i,j)计算结果计算结果则则，C(0,4)=32二分检索树：二分检索树：

67、T04=2 =T01(左子树），左子树），T24(右子树）右子树） T01=1 =T00(左子树），左子树），T11(右子树）右子树） T24=3 =T22(左子树），左子树），T34(右子树）右子树） 0123402,0,03,0,01,0,01,0,01,0,018,8,17,7,23,3,33,3,4212,19,19,12,25,8,3316,25,211,19,2416,32,2W(j,j+i),C(j,j+i),R(j,j+i)n树的形态树的形态ifdoreadwhile3.计算时间计算时间 当当j-i=m时，有时，有n-m+1个个C(i,j)要计算要计算 C(i,j)的计算：的计

68、算：(m) 每个每个C(i,j)要求找出要求找出m个量中的最小值。个量中的最小值。 则，则，n-m+1个个C(i,j)的计算时间：的计算时间： (nm-m2) 对所有可能所有可能的的m，总计算算时间为： 一种改一种改进措施（克努特）：最措施（克努特）：最优的的kR(i,j-1),R(i+1,j) 4.算法描述算法描述 procedure OBST(P,Q,n) /给定给定n个标识符个标识符a1a2a2anan。已知成功检索的概率已知成功检索的概率P(i),P(i),不成功检索概率不成功检索概率Q(i), Q(i), 0in 0in。算法对于标识符算法对于标识符ai+1,ai+1, ,ajaj计

69、算最优二分检索树计算最优二分检索树TijTij的成本的成本C(i,j)C(i,j)、根根 R(i,j)R(i,j)、权、权W(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

70、,n), R(n,n), C(n,n)(Q(n),0,0) for m2 to n do /找有找有m个结点的最优树个结点的最优树/ for i0 to n-m do ji+m W(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)k repeat repeat end OBSTOBST算法的计算时间算法的计算时间:(n2)1. 问题描述问题描述 1) KNAP(1,j,X) 目标函数目标函数： 约束

71、条件约束条件： 0/1背包问题：背包问题：KNAP(1,n,M) 最优性原理最优性原理对于对于0/1背包问题成立背包问题成立 求解策略：求解策略：向前递推向前递推、向后递推向后递推 4.5 0/1背包问题背包问题2) 向后递推关系式向后递推关系式 记记fj(X)是是KNAP(1,j,X)的最优解，则的最优解，则fn(M)有有 fn(M) = maxfn-1(M),fn-1(M-wn)+pn 对于任意的对于任意的fi(X)，i0,有有 fi(X) = maxfi-1(X),fi-1(X-wi)+pi 递推过程：递推过程： 初始值初始值 0 X00 f0= X0 0 求出所有可能的求出所有可能的X

72、对应的对应的fi值。值。 fn(M)=KNAP(1,n,M)例例4.11 背包问题背包问题 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6 递推计算过程递推计算过程 X0 f0(X)= 0 X0 X0 f1(X)= max0,+1=0 0X2 max0,0+1 = 1 X2 X0 0 0X2 f2(X)= 1 2X3 max1,0+2=2 3X5 max1,1+2 = 3 X5 f3(M)= max3,1+5 = 6 fi(X) = maxfi-1(X),fi-1(X-wi)+pi解向量的推导解向量的推导 f3(M)=6 x3=1 P=6-p3=1

73、KNAP(1,3,6)=6 M=6-w3=2 X=(1,0,1) f2(M)=1 x2=0 f1(M)=1 x1=1 f1,f2,f3计算过程（图解）计算过程（图解）1234567012f0(x)=0i:fi-1(x-wi) + pii=0:函数不存在1234567012i1:f0(x-w1) + p11234567012f1(x)1234567012i2:f1(x-w2) + p23xxxx12345670123xf2(x)12345670678x1234589i3:f2(x-w3) + p312345670678x1234589f3(x)10注： fi-1(X-wi)+pi曲线的构造：将曲

74、线的构造：将fi-1(X)的曲线在的曲线在X轴上右移轴上右移wi个单位，然后上个单位，然后上 移移pi个单位而得到；个单位而得到； fi(X)曲线的构造：由曲线的构造：由fi-1(X) 和和fi-1(X-wi)+pi的曲线按的曲线按X相同时相同时取大值取大值的规的规 则归并而成则归并而成2. 序偶表示序偶表示 记记 fi的序偶集合为的序偶集合为 Si = (Pj,Wj)|Wj是是fi曲线中使得曲线中使得fi产生一次阶跃的产生一次阶跃的X值，值，0jr 即即Pj=fi(Wj) (P0,W0)=(0,0) 共有共有r个阶跃值，分别对应个阶跃值，分别对应r个个(Pj,Wj)序偶，序偶， 1jr 若若

75、WjWj+1,则则PjPj+1，0jr 若若WjXWj+1，fi(X)=fi(Wj) 若若XWr，fi(X)=fi(Wr) Si的构造的构造 记记 是是fi-1(X-wi)+pi的所有序偶的集合，则的所有序偶的集合，则 其中，其中，Si-1是是fi-1的所有序偶的集合的所有序偶的集合 Si的构造的构造：由：由Si-1和和 按照按照支配规则支配规则合并而成。合并而成。 支配规则支配规则：如果：如果Si-1和和 之一有序偶之一有序偶(Pj,Wj),另一有另一有(Pk,Wk)， 且有且有 WjWk , Pj Pk， 则序偶则序偶(Pj,Wj)将被舍弃。将被舍弃。 （即取最大值规则）。（即取最大值规则

76、）。 注：注： Si中的所有序偶是背包问题中的所有序偶是背包问题KNAP(1,i,X)在在X各种各种 取值下的最优解取值下的最优解例例4.12 例例4.11的序偶计算的序偶计算 S0=(0,0) =(1,2) S1=(0,0),(1,2) =(2,3),(3,5) S2=(0,0),(1,2), (2,3),(3,5) =(5,4),(6,6), (7,7),(8,9) S3=(0,0),(1,2), (2,3),(5,4),(6,6), (7,7),(8,9) 注：序偶注：序偶(3,5)被被(5,4)“支配支配”而删除而删除KNAP(1,n,M)问题的解问题的解 Sn是是KNAP(1,n,X

77、)在在0XM各种取值下的最优解各种取值下的最优解 KNAP(1,n,M)的最优解的最优解由由Sn的最后一对的最后一对有效序偶有效序偶给出。给出。xi的推导的推导 xn: 设设Sn的最后一对的最后一对有效序偶有效序偶是是(P1,W1)，则，则(P1,W1)或者或者 是是Sn1的最末一对序偶，或者是的最末一对序偶，或者是(Pj+pn,Wj+wn)，其中其中 (Pj,Wj) Sn1且且Wj是是Sn1中满足中满足Wj+wnM的最大值。的最大值。 若若(P1,W1) Sn1，则，则Xn0；否则，否则， (P1pn,W1-wn) Sn1 ，Xn1 xn-1: 若若xn=0，则判断则判断(P1,W1) Sn

78、2？，？，以确定以确定Xn-1的值的值 若若xn=1，则依据则依据(P1pn,W1-wn) Sn2？，？，以判断以判断Xn-1的的值值 xn-2,x1将依次推导得出将依次推导得出 例例4.13 （例（例4.12) S0=(0,0) S1=(0,0),(1,2) S2=(0,0),(1,2), (2,3),(3,5) S3=(0,0),(1,2), (2,3),(5,4),(6,6), (7,7),(8,9) M=6，f3(6)由由S S3 3中的序偶中的序偶(6,6)给出。给出。 1) (6,6) S1) (6,6) S2 2 x x3 3=1=1 2) (6-p 2) (6-p3 3,6-w

79、,6-w3 3)=(1,2)S)=(1,2)S2 2且且(1,2)S(1,2)S1 1 x x2 2=0=0 3) (1,2) S 3) (1,2) S0 0 x x1 1=1=1算法算法4.6 非形式的背包算法非形式的背包算法 procedure DKP(p,w,n,M) S0 (0,0) for i1 to n-1 do (P1,W1)|(P1-pi,W1-wi) Si-1 and W1M Si MERGE-PURGE(Si-1, ) repeat (PX,WX) Sn-1的最末一个有效序偶的最末一个有效序偶 (PY,WY)(P1pn,W1+wn)，其中，其中，W1是是Sn-1中使得中使得

80、WwnM的的 所有序偶中取最大所有序偶中取最大值得得W /沿沿Sn-1, S1回溯确定回溯确定xn,xn-1,x1的取的取值/ if PXPY then xn0 /PX将是将是Sn的最末序的最末序偶偶/ else xn1 /PY将是将是Sn的最末序的最末序偶偶/ endif 回溯确定回溯确定xn-1,x1 end DKP3. DKP的实现的实现1)序偶集序偶集Si的存储结构的存储结构 使用两个一维数组使用两个一维数组P和和W存放所有的序偶存放所有的序偶(P1,W1),其中其中P存放存放P1值，值，W存放存放W1值值 序偶集序偶集S0, S1, Sn-1顺序顺序、连续连续存放存放于于P和和W中；

81、中； 用指针用指针F(i)表示表示Si中第一个元素在数组中第一个元素在数组 (P,W)中的下标位置，中的下标位置，0in; F(n)Sn-1中最末元素位置中最末元素位置1 1 2 3 4 5 6 7 P 0 0 1 0 1 2 3 W 0 0 2 0 2 3 5 F(0)F(1) F(2) F(3)2) 序偶的生成与合并序偶的生成与合并 Si的序偶将按照的序偶将按照P和和W的递增次序生成的递增次序生成 中序偶的生成将与中序偶的生成将与 和和Si-1的合并同时进行的合并同时进行 设设 生成的下一序偶是生成的下一序偶是(PQ,WQ)；对对所有所有的的(PQ,WQ)，根据支配规则根据支配规则处理如下

82、：处理如下： 将将Si-1中所有中所有W值值小于小于WQ的序偶直接计入的序偶直接计入Si中；中； 根据支配规则，若根据支配规则，若Si-1中有中有W值小于值小于WQ的序偶的序偶支配支配 (PQ,WQ)，则，则(PQ,WQ)将被舍弃，否则将被舍弃，否则(PQ,WQ)计入计入Si中；并清除中；并清除 Si-1中所有可被支配的序偶，这些序偶中所有可被支配的序偶，这些序偶有有WWQWQ且且PPQPPQ 对所有的对所有的(PQ,WQ)重复上述处理；重复上述处理； 将最后将最后Si-1中剩余的序偶直接计入中剩余的序偶直接计入Si中；中； 所有计所有计入入Si中的新序偶依次存放到中的新序偶依次存放到由由F(

83、i)指示的指示的Si的存放位的存放位 置上。置上。 注：不需要存放注：不需要存放 的的专用空间专用空间3) 算法的实现算法的实现算法算法4.7 0/1背包问题的算法描述背包问题的算法描述 procedure DKNAP(p,w,n,M,m) real p(n), w(n), P(m), W(m),pp,ww,M；integer F(0:n),l,h,u,i,j,p,next F(0)1;P(1)W(1)0 /S0/ lh1 / S0 的首端和末端；的首端和末端；l是是Si-1的首端，的首端，h是是Si-1的末端的末端/ F(1)next2 /P和和W中第一个空位；中第一个空位；next指示指示

84、P/W中可以存放中可以存放(P,W)序偶的第一个位置序偶的第一个位置/ for i1 to n-1 do /生成生成Si/ kl u在在lrh中使得中使得W(r)+wiM的最大的最大r /u指示由指示由Si-1生成生成 的最大有效位置的最大有效位置/ for jl to u do /生成生成 ，同，同时进行行归并并/ (pp,ww)(P(j)+pi,W(j)+wi) /生成生成 中的下一个元素中的下一个元素/ while kh and W(k)ww do /从从Si-1中取元素并归并中取元素并归并/ P(next)P(k);W(next)W(k) /所有所有W(k)ww 的序偶直接的序偶直接归

85、并并/ nextnext+1;kk1 repeat /按照支配按照支配规则考考虑(pp,ww)及及Si-1中的序偶中的序偶/ if kh and W(k)=ww then ppmax(pp,P(k) kk+1 endif if ppP(next-1) then (P(next), W(next)(pp,ww) nextnext+1 endif /清除清除Si-1中的序中的序偶偶/ while kh and P(k)P(next-1) do kk+1 repeat repeat /将将Si-1中剩余的元素并中剩余的元素并入入Si / while kh do (P(next),W(next)(P(

86、k),W(k) nextnext+1; kk+1 repeat /对Si+1置初置初值 / lh+1; hnext -1; F(i+1)next repeat CALL PARTS /递推求推求取取Xn,Xn-1,x1/ END DKNAP4. 过程过程DKNAP的分析的分析1) 空间复杂度空间复杂度 记记Si中的序偶数为：中的序偶数为：|Si| 则有，则有， |Si| |Si-1| | 又，又， | | |Si-1| 所以，所以， |Si|22|Si-1| 最坏情况下有（由最坏情况下有（由Si-1生成生成 和和Si时没有序偶被支配）时没有序偶被支配） ： 故，故，DKNAP所需的空间复杂度（

87、所需的空间复杂度（P、W数组）数组）为为:(2(2n n) )2) 时间复杂度时间复杂度 由由Si-1生成生成Si的时间为：的时间为： ，0iin-1 故，故，DKNAP计算所有的计算所有的Si所需的时间为：所需的时间为： 注：注： 若每件物品的重量若每件物品的重量wi和效益值和效益值pi均为均为整数整数，则，则Si中每个序偶中每个序偶(P,W)的的P值和值和W值也是整数，且有值也是整数，且有 ，WMM 又，在任一又，在任一Si中的所有序偶具有互异中的所有序偶具有互异P值和值和W值，故有值，故有 且且 在所有在所有w wj j和和p pj j均为均为整数整数的情况下，的情况下，DKNAPDKN

88、AP的时间和空间复的时间和空间复杂度将为：杂度将为：5. 序偶集合的一种启发式生成策略序偶集合的一种启发式生成策略 设设L是最优解的估计值，且是最优解的估计值，且有有fn(M)LL 设设PLEFT(i)=PLEFT(i)= 若正在生成的序偶若正在生成的序偶(P,W)(P,W)有有P PPLEFT(i)PLEFT(i)L L，则，则(P,W)(P,W)将将不计入不计入S Si i中。中。 L L的选择：的选择： 取取S Si i的最末序偶的最末序偶(P,W)(P,W)的的P P作为作为L L，PfPfn n(M)(M) 将某些剩余物品的将某些剩余物品的p p值值P P作为作为L L例例4.15

89、0/1背包问题背包问题 n=6,(p1,p2,p3,p4,p5,p6)=(w1,w2,w3,w4,w5,w6)=(100,50,20,10,7,3),M=165 不使用启发方法的序偶集不使用启发方法的序偶集S0=0S1=0,100S2=0,50,100,150S3=0,20,50,70,100,120,150S4=0,10,20,30,50,60,70,80,100,110,120,130,150，160S5=0,7,10,17,20,27,30,37,50,57,60,67,70,77,80,87,100, 107,110,117,120,127,130,137,150,157,160则，则

90、，f6(165)=163 注：每对序偶注：每对序偶(P,W)仅用单一仅用单一量量P（或（或W）表示表示启发式规则求解启发式规则求解 分析：将物品分析：将物品1,2,4,6装入背包，将占用装入背包，将占用163的重量并产生的重量并产生163的效益。的效益。 故，取期望值故，取期望值L163. 按照启发式生成规则，按照启发式生成规则，从从Si中删除所有中删除所有PPLEFT(i)L的序偶，则有的序偶，则有 PLEFT(0)=p1+p2+p3+p4+p5+p6=190 S0=0 =100 PLEFT(1)=p2+p3+p4+p5+p6=90 S1=100 =150 PLEFT(2)=p3+p4+p5+p6=40 S2=150 = PLEFT(3)=p4+p5+p6=20 (w3=20) S3=150 =160 PLEFT(4)=p5+p6=10 S4=160 = PLEFT(5)=p6=3 (w5=7) S5=160 PLEFT(6)=0 f6(165)=160+3 163