第5章 动态规划 2018/11/16.

Presentation on theme: "第5章 动态规划 2018/11/16."— Presentation transcript:

1 第5章 动态规划 2018/11/16

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

3 1）枚举法：穷举可能的决策序列，从中选取可以获得最优解的决策序列
2. 多阶段决策过程的求解策略 1）枚举法：穷举可能的决策序列，从中选取可以获得最优解的决策序列 2）动态规划 20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，创立了解决这类过程优化问题的新方法——动态规划。 动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。 应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划(如线性规划、非线性规划)，只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 2018/11/16

4 3. 最优性原理(Principle of Optimality)
过程的最优决策序列具有如下性质：无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。 利用动态规划求解问题的前提 1) 证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题 2) 获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键。 2018/11/16

5 例5.1 [多段图问题]多段图G=(V,E)是一个有向图，且具有特性: 结点：结点集V被分成k≥2个不相交的集合Vi，1≤i≤k，
其中V1和Vk分别只有一个结点s(源点)和t(汇点) · 每一集合Vi定义图中的一段。 边： 所有的边(u,v)均具有如下性质： 若<u,v>∈E，则该边将是从某段i指向i+1段，即若u∈Vi，则v∈Vi＋1, 1≤i≤k－1。 · 每条边(u,v)均附有成本c(u,v)。 s到t的路径：从第1段开始，至第2段、第3段、…、最后 在第k段终止。路径的成本是这条路径上边的成本和。 多段图问题：求由s到t的最小成本路径。 2018/11/16

6 1 2 3 4 5 6 7 8 9 10 11 12 V1 V2 V3 V4 V5 5段图 2018/11/16

7 假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径。 ● 初始状态：s ● 初始决策：(s,v2)， v2∈V2
多段图问题的多阶段决策过程：生成从s到t的最小成本路径是在k-2个阶段（除s和t外）进行某种决策的过程：从s开始，第i次决策决定Vi+1(1≤i≤k-2)中的哪个结点在从s到t的最短路径上。 最优性原理对多段图问题成立 假设s,v2,v3,…,vk-1,t是一条由s到t的最短路径。 ● 初始状态：s ● 初始决策：(s,v2)， v2∈V2 ● 初始决策产生的状态：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/11/16

8 例5.2[0/1背包问题] KNAP(l,j,X) 目标函数： 约束条件： 0/1背包问题：KNAP(1,n,M) 2018/11/16

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

10 4. 动态规划模型的基本要素 一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素： 1) 阶段
阶段(step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。阶段变量一般用k=1,2,..,n表示。 2018/11/16

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

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

13 pk,j(xk)={uk(xk),uk+1(xk+1),...，uj(xj)}。
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 policies). 2018/11/16

14 5) 状态转移方程 在确定性过程中，一旦某阶段的状态和决策为已知，下阶段的状态便完全确定。用状态转移方程(equation of state)表示这种演变规律，写作 2018/11/16

15 能够用动态规划解决的问题的指标函数应具有可分离性，即Vk,n可表为xk,uk,Vk+1, n 的函数，记为：
6) 指标函数和最优值函数 指标函数(objective function)是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段k到阶段n的指标函数用Vk,n(xk,pk,n(xk))表示，k=1,2,...,n。 能够用动态规划解决的问题的指标函数应具有可分离性，即Vk,n可表为xk,uk,Vk+1, n 的函数，记为： 2018/11/16

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

17 xn … 5. 递推策略 1）向前处理法 列出根据xi+1,…,xn的最优决策序列求取xi决策值的关系式。
从最后一个阶段，逐步向前递推求出各阶段的决策值。决策序列x1,x2,…,xn就是问题的最优解。 xn-1,1 xn … xn-1,pn-1 2018/11/16

18 例5.3 利用向前处理法求解0/1背包问题 设gi(x)是KNAP(i+1,n,X)的最优解。
例5.3 利用向前处理法求解0/1背包问题 设gi(x)是KNAP(i+1,n,X)的最优解。 ● g0(M)：KNAP(1,n,M)的最优解。由于x1的取值等于1或0,可得： g0(M)=max{g1(M),g1(M-w1)+p1} ● 对于某个xi，xi等于1或0，则有： gi(X)=max{gi+1(X),gi+1(X-wi+1)+pi+1} 初始值： 0 X≥0 gn(X) = -∞ X＜0 2018/11/16

19 例5.4 利用向前处理法求解k段图问题 设 ∈V2，1≤j2≤p2,|V2|=p2; 是由 到t的最短路径，则s到t的最短路径是
{s | ∈V2,1≤j2≤p2}中最短的那条路径。 若s,v2,v3,…,vi,…,vk-1,t是s到t的一条最短路径，vi是其中的一个中间点，则s,v2,v3,…,vi和 vi,…,vk-1,t分别是由s到vi和vi到t的最短路径（最优性原理） 从Vi中的结点ji到t的最短路径将是： min( { | ∈Vi+1,1≤ji+1≤pi+1}) 2018/11/16

20 列出根据x1,…,xi-1的最优决策序列求取xi决策值的关系式。
2） 向后处理法 列出根据x1,…,xi-1的最优决策序列求取xi决策值的关系式。 从第一个阶段，逐步向后递推求出各阶段的决策值。决策序列x1,x2,…,xn就是问题的最优解。 2018/11/16

21 设fi(x)是KNAP(1,i,X)的最优解。 则，fn(M) = KNAP(1,n,M) 向后递推关系式：
例5.5 0/1背包问题（向后处理策略） 设fi(x)是KNAP(1,i,X)的最优解。 则，fn(M) = KNAP(1,n,M) 向后递推关系式： fi(X)=max{fi-1(X),fi-1(X-wi)+pi} 初始值： 0 X≥0 f0(X) = -∞ X＜0 2018/11/16

22 例5.6 k段图问题（向后处理策略） 设 ∈Vk-1，1≤jk-1≤pk-1，|Vk-1|=pk-1;
是由s到 的最短路径，则s到t的最短路径是 { t | ∈Vk-1,1≤jk-1≤pk-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 ,1≤ji≤pi}) 2018/11/16

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

24 关于动态规划求解策略的进一步说明 采用枚举法：若问题的决策序列由n次决策构成，而每次决策有p种选择，则可能的决策序列将有pn个。
利用动态规划策略的求解过程中保存了所有子问题的最优解，而舍去了所有不能导致问题最优解的次优决策序列 动态规划：可能有多项式的计算复杂度。 2018/11/16

25 （3）能利用经验，提高求解的效率。动态规划方法反映了过程逐段演变的前后联系，较之非线性规划与实际过程联系得更紧密。 不足之处：
与非线性规划相比，动态规划的优点： （1）易于确定全局最优解。动态规划方法是一种逐步改善法，它把原问题化为一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少的多，约束集合也要简单得多。 （2）能得到一簇解，有利于分析结果 （3）能利用经验，提高求解的效率。动态规划方法反映了过程逐段演变的前后联系，较之非线性规划与实际过程联系得更紧密。 不足之处： （1）没有一个统一的标准模型可供应用。 （2）应用的局限性。要求状态变量满足“无后效性”条件，不少实际问题在取其自然特征作为状态变量往往不能满足这条件。 （3）在数值求解中，存在“维数障碍”。在计算机中，每递推一段，必须把前一段的最优值函数在相应的状态集合上的全部值存入内存中。当维数增大时，所需的内存量成指数倍增长。 2018/11/16

26 5.2 多段图问题 1. 问题的描述 ● 在多段图中求从s到t的一条最小成本的路径，可以看作是在k-2个段作出某种决策的结果。
5.2 多段图问题 1. 问题的描述 ● 在多段图中求从s到t的一条最小成本的路径，可以看作是在k-2个段作出某种决策的结果。 ● 第i次决策决定Vi+1中的哪个结点在这条路径上，这里 1≤i≤k-2； ● 最优性原理对多段图问题成立 2018/11/16

27 2. 向前处理策略求解 设 P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径， COST(i,j)是这条路径的成本。
2. 向前处理策略求解 设 P(i,j)是一条从Vi中的结点j到汇点t的最小成本路径， COST(i,j)是这条路径的成本。 1) 向前递推式 2) 递推过程 ★ 第k-1段 c(j,t) <j,t>∈E COST(k-1,j) = ∞ ★ j∈VK-2计算COST(k-2,j)=min{c(j,l)+cost(k-1,l)} ★ COST(1,S) 2018/11/16

28 Vi Vi+1 l1 l2 t … j . lpi+1 2018/11/16

29 1 2 3 4 5 6 7 8 9 10 11 12 V1 V2 V3 V4 V5 5段图 2018/11/16

30 ★各递推结果 第4段 COST(4,9) = c(9,12) = 4 COST(4,10) = c(10,12) = 2
第3段 COST(3,6) = min{6+COST(4,9),5+COST(4,10)} = 7 COST(3,7) = min{4+COST(4,9),3+COST(4,10)} = 5 COST(3,8) = min{5+COST(4,10),6+COST(4,11)} = 7 第2段 COST(2,2) = min{4+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) = min{9+COST(2,2),7+COST(2,3), 3+COST(2,4),2+COST(2,5)} = 16 S到t的最小成本路径的成本 ＝ 16 2018/11/16

31 记 D(i,j)＝每一COST(i,j)的决策 即，使c(j,L)+COST(i+1,L)取得最小值的L值。
★ 最小路径的求取 记 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) = 10 D(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(2,D(1,1)) = 7 ● v4 = D(3,D(2,D(1,1))) = D(3,7) = 10 故由s到t的最小成本路径是：1→2→7→10→12 2018/11/16

32 3) 算法描述 ★ 结点的编号规则 源点s编号为1,然后依次对V2、V3…Vk-1中的结点编号，汇点t编号为n。
目的：使对COST和D的计算仅按n-1,n-2,…,1的次序计算即可，无需考虑标示结点所在段的第一个下标。 ★ 算法描述 2018/11/16

33 procedure FGRAPH(E,k,n,P) //输入是按段的顺序给结点编号的，有n个结点的k段图。E是边
算法5.1 多段图的向前处理算法 procedure FGRAPH(E,k,n,P) //输入是按段的顺序给结点编号的，有n个结点的k段图。E是边 集，c(i,j)是边<i,j>的成本。P(1:k)存储最小成本路径// real COST(n) ←0; integer D(n-1),P(k),r,j,k,n for j←n-1 to 1 by -1 do //计算COST(j)// 设r是具有性质：<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 j←2 to k-1 do //找路径上的第j个结点// P(j) ←D(P(j-1)) //回溯求出该路径// end FGRAPH 2018/11/16

34 算法的时间复杂度 若G采用邻接表表示，总计算时间为： 2018/11/16

35 3. 向后处理策略求解 设 BP(i,j)是一条从源点s到Vi中的结点j的最小成本路径， BCOST(i,j)是这条路径的成本。
3. 向后处理策略求解 设 BP(i,j)是一条从源点s到Vi中的结点j的最小成本路径， BCOST(i,j)是这条路径的成本。 1) 向后递推式 2) 递推过程 ★ 第2段 c(1,j) <1,j>∈E BCOST(2,j) = ∞ 2018/11/16

36 1 2 3 4 5 6 7 8 9 10 11 12 V1 V2 V3 V4 V5 5段图 2018/11/16

37 第3段 BCOST(3,6) = min{BCOST(2,2)+4,BCOST(2,3)+2} = 9
★各递推结果 第2段 BCOST(2,2) = 9 BCOST(2,3) = 7 BCOST(2,4) = 3 BCOST(2,5) = 2 第3段 BCOST(3,6) = min{BCOST(2,2)+4,BCOST(2,3)+2} = 9 BCOST(3,7) = min{BCOST(2,2)+2,BCOST(2,3)+7, BCOST(2,5)+11} = 11 BCOST(3,8) = min{BCOST(2,4)+11, BCOST(2,5)+8} = 10 第4段 BCOST(4,9) = min{BCOST(3,6)+6,BCOST(3,7)+4} = 15 BCOST(4,10) = min{BCOST(3,6)+5,BCOST(3,7)+3, BCOST(3,8)+5} = 14 BCOST(4,11) = min{BCOST(3,8)+6} = 16 第5段 BCOST(5,12) = min{BCOST(4,9)+4,BCOST(4,10)+2, BCOST(4,11)+5} = 16 S到t的最小成本路径的成本 ＝ 16 2018/11/16

38 ★ 最小路径的求取 记 BD(i,j)＝每一COST(i,j)的决策 即，使COST(i-1,l)+c(l,j)取得最小值的l值。
例：BD(3,6) = 3, BD(3,7)= 2 ,BD(3,8) = 5 BD(4,9) = 6, BD(4,10) = 7, BD(4,11) = 8 BD(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的最小成本路径是：1→2→7→10→12 2018/11/16

39 1 2 3 4 5 6 7 8 9 10 11 12 V1 V2 V3 V4 V5 5段图 2018/11/16

40 procedure BGRAPH(E,k,n,P) //输入是按段的顺序给结点编号的，有n个结点的k段图。E是边
算法4.2 多段图的向后处理算法 procedure BGRAPH(E,k,n,P) //输入是按段的顺序给结点编号的，有n个结点的k段图。E是边 集，c(i,j)是边<i,j>的成本。P(1:k)带出最小成本路径// real BCOST(n); integer BD(n-1),P(k),r,j,k,n,BCOST(1) ←0 for j←2 to n do //计算BCOST(j)// 设r是具有<r,j>∈E且使BCOST(r)+ c(r,j)取最小值性质的结点 BCOST(j)← BCOST(r)+ c(r,j) BD(j) ←r //记录决策值// repeat P(1)←1; P(k)←n for j←k-1 to 2 by -1 do //找路径上的第j个结点// P(j) ←D(P(j+1)) //回溯求出该路径// end BGRAPH 2018/11/16

41 4. 多段图问题的应用实例 将n个资源分配给r个项目的问题：如果把j个资源，0≤j≤n，分配给项目i，可以获得N(i,j)的净利。
2018/11/16

42 当2≤i≤r时，每段有n+1个结点，每个结点具有形式 V(i,j)：表示到项目i之前为止，共把j个资源分配给了项目1,2,…,i-1
段： 1到r之间的段i表示项目i。 结点： i=1时，只有一个结点——源点s =V(1,0) 当2≤i≤r时，每段有n+1个结点，每个结点具有形式 V(i,j)：表示到项目i之前为止，共把j个资源分配给了项目1,2,…,i-1 汇点t=V(r+1,n) 边的一般形式：<V(i,j),V(i+1,L)>,j≤L,1≤i≤r 成本： ★ 当j≤L且1≤i≤r时，边<V(i,j),V(i+1,l)>赋予成本 N(i,l-j),表示给项目i分配l-j个资源所可能获得的净利。 ★ 当j≤n且i=r时，此时的边为：<V(r,j),V(r+1,n)>,该边赋 予成本： 2018/11/16

43 实例：将4个资源分配给3个项目。构成一个4段图。
问题的解：资源的最优分配方案是由s到t的一条最大成本的路径给出——改变边成本的符号，从而将问题转换成为求取最小成本路径问题。 2018/11/16

44 5.3 每对结点之间的最短路径 1. 问题描述 设G=(V,E)是一个有n个结点的有向图，无负环，C是G的成本邻接矩阵，C中元素有：
，i ＝ j c(i,j)= 边<i,j>的成本，i≠j且<i,j>∈E(G) ∞ ，i≠j且 其中，1≤i，j≤n 每对结点之间的最短路径问题：求满足下述条件的矩阵A，A中的任一元素A(i,j)代表结点i到结点j的最短路径长度。 2018/11/16

45 将求解G中每对结点之间的最短路径问题转化成一个多阶段决策过程。 ● 决策什么？ ● 最优性原理对于该问题是否成立？
分析： 利用单源最短路径算法求解 ● 计算n个结点的单源最短路径。 ● 时间复杂度：Ο(n3) 利用动态规划策略求解 将求解G中每对结点之间的最短路径问题转化成一个多阶段决策过程。 ● 决策什么？ ● 最优性原理对于该问题是否成立？ 2018/11/16

46 i,...,k,…,j 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的最短路径。 故，最优性原理对于该问题成立。 2018/11/16

47 i,...,k,…,j 2）多阶段决策过程 设k是由i到j的最短路径上编号（假设所有n个结点依次有从1到n的编号）最高的中间结点：
则由i到k的子路径上将不会有比编号k-1更大的结点；同理，由k到i的子路径上也将不会有比编号k-1更大的结点。 构造多阶段决策过程：对由i到j的最短路径，首先决策哪一个结点是该路径上具有最大编号的中间结点k，然后再去求取由i到k和由k到j的最短路径——其中应不包含比k-1还大的中间结点。 2018/11/16

48 记Ak(i,j)表示从i到j并且不经过比k还大的结点的最短路径长度。则， A(i,j) = An(i,j)
3）递推关系式 记Ak(i,j)表示从i到j并且不经过比k还大的结点的最短路径长度。则， 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) = min{An-1(i,j) ，An-1(i,n) + An-1(n,j)} 不经过n结点 经过n结点 2018/11/16

49 Ak(i,j) = min{Ak-1(i,j) ，Ak-1(i,k) + Ak-1(k,j)}
初值： A0(i,j)= C(i,j)，1≤i≤n，1≤j≤n 递推计算： A1(i,j), A2(i,j),…, An(i,j)= A (i,j) 2018/11/16

50 3. 算法描述 算法5.3 每对结点之间的最短路径长度 procedure ALL-PATHS(COST,A,n)
算法5.3 每对结点之间的最短路径长度 procedure ALL-PATHS(COST,A,n) //COST(n,n)是n结点图的成本邻接矩阵；A(i,j)是结点vi到vj的最短路 径的成本；COST(i,i)=0,1≤i≤n// integer I,j,k,n; real COST(n,n),A(n,n) for i←1 to n do for j←1 to n do A(i,j) ←COST(i,j) //用COST(i,j)对A0赋初值// repeat for k←1 to n do A (i,j) ← min{A (i,j) ，A (i,k) + A (k,j)} end ALL-PATHS 2018/11/16

51 ⑵ Ak(i,j) ← min{Ak-1(i,j), Ak(i,k) + Ak-1(k,j) }
算法的设计说明 1） ∵ ⑴ Ak(i,k) = Ak-1(i,k) Ak(k,j) = Ak-1(k,j) ⑵ Ak(i,j) ← min{Ak-1(i,j), Ak(i,k) + Ak-1(k,j) } ≡ Ak(i,j) ← min{Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j) } ∴ 在算法的计算过程中取消了A的上标，并保证了每次计算的 Ak(i,j)即为 min{Ak-1(i,j), Ak-1(i,k) + Ak-1(k,j) } 2）如何求每对结点之间的路径？ 2018/11/16

52 注： A(i,j) = ∞表明G中从i到j没有有向路径
例5.8 有向图如图所示 求图中所有结点间的最短路径矩阵A： 6 4 2 11 3 v1 v2 v3 A0 1 2 3 4 11 6 ∞ A1 1 2 3 4 11 6 7 1 2 3 4 11 6 ∞ A2 1 2 3 4 6 7 A3 1 2 3 4 6 5 7 注： A(i,j) = ∞表明G中从i到j没有有向路径 2018/11/16

53 性能分析 计算时间＝ 注：该时间与A的值无关： for k←1 to n do 迭代n次 for i←1 to n do 迭代n次
for j←1 to n do 迭代n次 A (i,j) ← min{A (i,j) ，A (i,k) + A (k,j)} repeat 2018/11/16

54 ∞的处理 设M是E中最大成本的一条边的成本，则An(i,j)<=(n-1)*M。因此，对于成本邻接矩阵中的∞用一个大于(n-1)*M的值代替。如果在算法结束时，A(I,j)> (n-1)*M，则表明G中没有由i到j的有向路径。 2018/11/16

55 4.4 最优二分检索树 1. 问题的描述 1）二分检索树定义
　 二分检索树Ｔ是一棵二元树，它或者为空，或者其每个结点含有一个可以比较大小的数据元素，且有： 　　　·Ｔ的左子树的所有元素比根结点中的元素小； 　　　·Ｔ的右子树的所有元素比根结点中的元素大； 　　　·Ｔ的左子树和右子树也是二分检索树。 注： ·二分检索树要求树中所有结点的元素值互异 2018/11/16

56 if for 对于一个给定的标识符集合，可能有若干棵不同的二分检索树: while loop
repeat loop 不同形态的二分检索树对标识符的检索性能是不同的。 2018/11/16

57 2）二分检索树的检索 算法5.4 SEARCH(T,X,i) i←T while i≠0 do case
//为X检索二分检索树T，如果X不在T中，则置i=0； 否则i有IDENT(i)=X// i←T while i≠0 do case :X＜IDENT(i):i←LCHILD(i) //若X小于IDENT(i)，则在左子树中继续查找// :X＝IDENT(i):return //X等于IDENT(i)，则返回// :X＞IDENT(i):i←RCHILD(i) //若X大于IDENT(i)，则在右子树中继续查找// endcase repeat end SEARCH 2018/11/16

58 图(a)：最坏情况下查找标识符loop需要做4次比较； 成功检索平均需要做12/5次比较;
二分检索树的性能特征 ① 例 图(a)：最坏情况下查找标识符loop需要做4次比较； 成功检索平均需要做12/5次比较; 图(b):最坏情况下查找标识符loop/while需要做3次比较； 成功检索平均需要做11/5次比较 ② 查找概率 可以期望不同标识符的检索频率是不同的。如 Pfor＞Pwhile ＞ Ploop ③ 不成功检索 可以期望不成功检索出现的频率也是不同的。 2018/11/16

59 if for while repeat loop 2018/11/16

60 3）最优二分检索树问题 设给定的标识符集合是{a1,a2,…,an}，并假定a1＜a2 ＜ … ＜ an 。
设，P(i)是对ai检索的概率，Q(i)是正被检索的标识符X恰好满足： ai ＜ X＜ai+1，0≤i≤n（设a0=-∞,an+1=+∞)时的概率，即一种不成功检索情况下的概率。 则 表示所有成功检索的概率 表示所有不成功检索的概率 考虑所有可能的成功和不成功检索情况，共2n+1种可能的情况，有 2018/11/16

61 外结点：代表不成功检索情况，刚好有n＋1个 关于{a1,a2,…,an}的最优二分检索树含义如下：
2018/11/16

62 二分检索树的预期成本 预期成本：算法对于所有可能的成功检索情况和不成功检索情况，平均所要做的比较次数。根据期望值计算方法，
平均检索成本＝Σ每种情况出现的概率×该情况下所需的比较次数 平均检索成本的构成：成功检索成分＋不成功检索成分 ● 成功检索：在l级内结点终止的成功检索，需要做l次比较运算（基于二分检索树结构）。该级上的任意结点ai的检索的成本为： P(i)*level(ai) ； 其中，level(ai) = 结点ai 的级数=l 2018/11/16

63 不成功检索的等价类：每种不成功检索情况定义了一个等价类，共有n+1个等价类Ei(0≤i≤n)。其中， E0={X|X＜a1}
●不成功检索： 不成功检索的等价类：每种不成功检索情况定义了一个等价类，共有n+1个等价类Ei(0≤i≤n)。其中， E0={X|X＜a1} Ei={X|ai＜X＜ai+1(1≤i＜n)} En={X|X＞an} 若Ei处于l级，则算法需作l-1次迭代。则，l级上的外部结点的不成功检索的成本分担额为： Q(i)*(level(Ei)-1) 则预期总的成本公式表示如下： 2018/11/16

64 例5.9 标识符集合（a1,a2,a3）=（do,if,stop）。可能的二分检索树如下所示。
最优二分检索树问题： 求一棵使得预期成本最小的二分检索树 例5.9 标识符集合（a1,a2,a3）=（do,if,stop）。可能的二分检索树如下所示。 成 功 检 索：3种 不成功情况：4种 2018/11/16

65 stop do if (a) (b) (c) (d) (e) 2018/11/16

66 最优 最优 1) 等概率：P(i)=Q(i)=1/7 cost(a) = 15/7 cost(b) = 13/7
if do stop (b) (c) 1) 等概率：P(i)=Q(i)=1/7 cost(a) = 15/7 cost(b) = 13/7 cost(c) = 15/7 cost(d) = 15/7 cost(e) = 15/7 2）不等概率： P(1)= P(2)=0.1 P(3)=0.05 Q(0)= Q(1)=0.1 Q(2)= Q(3)=0.05 cost(a) = 2.65 cost(b) = 1.9 cost(c) = 1.5 cost(d) = 2.15 cost(e) = 1.6 最优 最优 2018/11/16

67 2. 多阶段决策过程 ak 把构造二分检索树的过程看成一系列决策的结果。
决策的策略：决策树根，如果{a1,a2,…,an}存在一棵二分检索树，ak是该树的根，则内结点a1,a2,…,ak-1和外部结点E0,E1,…,Ek-1将位于根ak的左子树中，而其余的结点将位于右子树中。 ak 由a1,a2,…,ak-1及E0,E1,…,Ek-1构成的二分检索树 由ak＋1, ak+2, …,an及Ek,Ek+1,…,En构成的二分检索树 2018/11/16

68 ● 左、右子树中所有结点的级数相对于子树的根测定，而相对于原树的根少1
定义： 含义： ● 左、右子树的预期成本——左、右子树的根处于第一级 ● 左、右子树中所有结点的级数相对于子树的根测定，而相对于原树的根少1 2018/11/16

69 COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n) 最优二分检索树：COST(T)有最小值
记： 则，原二分检索树的预期成本可表示为： 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、及ak＋1, 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/11/16

70 ★ 然后依次计算j-i=2,3,…,n的C(i,j)。 ★ C(0,n)=最优二分检索树的成本。 初始值 C(i,i) = 0
则， 对任何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)，0≤i≤n 2018/11/16

71 例４.10 设n=4,且(a1,a2,a3,a4)=(do,if,read,while)。
最优二分检索树的构造 ● 在计算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/11/16

72 且有，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)+min{C(0,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)+min{C(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)+min{C(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)+min{C(3,3)+C(4,4)} = 3 R(3,4) = 4 ① ② ③ ④ 2018/11/16

73 且有，W(i,j)=P(j)+Q(j)+W(i,j-1)
j-i=2 w(0,2)=p(2)+q(2)+w(0,1)=12 c(0,2)=w(0,2)+min{c(0,1)+c(2,2),c(0,0)+c(1,2)} = r(0,2)=1 w(1,3)=p(3)+q(3)+w(1,2)=9 c(1,3)=w(1,3)+min{c(1,1)+c(2,3) ,c(1,2)+c(3,3)} = r(1,3)=2 w(2,4)=p(4)+q(4)+w(2,3)=5 c(2,4)=w(1,4)+min{c(2,2)+c(3,4) ,c(2,3)+c(4,4)} = r(2,4)=3/4 2018/11/16

74 j-i=3 w(0,3)=P(3)+q(3)+w(0,2)=14
c(0,3)=w( 0,3 )+min{c(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 )+min{c(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)+min{c(0,0)+c(1,4), c(0,1)+c(2,4) , c(0,2)+c(3,4),c(0,3)+c(4,4)} = r(0,4)=2 2018/11/16

75 W(j,j+i),C(j,j+i),R(j,j+i)
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(右子树） 1 2 3 4 2,0,0 3,0,0 1,0,0 8,8,1 7,7,2 3,3,3 3,3,4 12,19,1 9,12,2 5,8,3 14,25,2 11,19,2 16,32,2 W(j,j+i),C(j,j+i),R(j,j+i) 2018/11/16

76 if 树的形态 do read while 2018/11/16

77 3.计算时间 ● 当j-i=m时，有n-m+1个C(i,j)要计算 ● C(i,j)的计算：Ｏ(m)
Ｏ(nm-m2) 对所有可能的m，总计算时间为： 一种改进措施（克努特）：最优的k∈[R(i,j-1),R(i+1,j)] 2018/11/16

78 4.算法描述 procedure OBST(P,Q,n)
//给定n个标识符a1＜a2＜…＜an。已知成功检索的概率P(i),不成功检索概率Q(i), 0≤i≤n。算法对于标识符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 i←0 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 m←2 to n do //找有m个结点的最优树// for i←0 to n-m do j←i+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 end OBST 2018/11/16

79 OBST算法的计算时间:Ｏ(n2) 2018/11/16

80 4.5 0/1背包问题 1. 问题描述 1) KNAP(1,j,X) 目标函数： 约束条件： 0/1背包问题：KNAP(1,n,M)
4.5 0/1背包问题 1. 问题描述 1) KNAP(1,j,X) 目标函数： 约束条件： 0/1背包问题：KNAP(1,n,M) 最优性原理对于0/1背包问题成立 求解策略：向前递推、向后递推 2018/11/16

81 2) 向后递推关系式 记fj(X)是KNAP(1,j,X)的最优解，则fn(M)有
fn(M) = max{fn-1(M),fn-1(M-wn)+pn} 对于任意的fi(X)，i＞0,有 fi(X) = max{fi-1(X),fi-1(X-wi)+pi} 递推过程： ★初始值 X≥0 f0= －∞ X＜0 ★求出所有可能的X对应的fi值。 ★ fn(M)=KNAP(1,n,M) 2018/11/16

82 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6 递推计算过程 －∞ X＜0 f0(X)=
fi(X) = max{fi-1(X),fi-1(X-wi)+pi} 例4.11 背包问题 n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5)，M=6 递推计算过程 －∞ X＜0 f0(X)= X≥0 －∞ X＜0 f1(X)= max{0,－∞+1}= ≤X＜2 max{0,0+1} = X≥2 ≤X＜2 f2(X)= ≤X＜3 max{1,0+2}= ≤X＜5 max{1,1+2} = X≥5 f3(M)= max{3,1+5} = 6 2018/11/16

83 解向量的推导 f3(M)=6 x3=1 ΔP=6-p3=1 X=(1,0,1) ΔM=6-w3=2 f2(ΔM)=1 x2=0
2018/11/16

84 1 2 3 4 5 6 7 f0(x)=0 x i:fi-1(x-wi) + pi i=0:函数不存在 1 2 3 4 5 6 7
f1,f2,f3计算过程（图解） 1 2 3 4 5 6 7 f0(x)=0 x i:fi-1(x-wi) + pi i=0:函数不存在 1 2 3 4 5 6 7 i＝1:f0(x-w1) + p1 x 1 2 3 4 5 6 7 f1(x) x 1 2 3 4 5 6 7 i＝2:f1(x-w2) + p2 x 1 2 3 4 5 6 7 x f2(x) 2018/11/16

85 ● fi-1(X-wi)+pi曲线的构造：将fi-1(X)的曲线在X轴上右移wi个单位，然后上移pi个单位而得到；
2 3 4 5 6 7 8 x 9 i＝3:f2(x-w3) + p3 1 2 3 4 5 6 7 8 x 9 f3(x) 10 注： ● fi-1(X-wi)+pi曲线的构造：将fi-1(X)的曲线在X轴上右移wi个单位，然后上移pi个单位而得到； ● fi(X)曲线的构造：由fi-1(X) 和fi-1(X-wi)+pi的曲线按X相同时取大值的规则归并而成 2018/11/16

86 2. 序偶表示 记 fi的序偶集合为 Si = {(Pj,Wj)|Wj是fi曲线中使得fi产生一次阶跃的X值，0≤j＜r} 即Pj=fi(Wj) ● (P0,W0)=(0,0) ●共有r个阶跃值，分别对应r个(Pj,Wj)序偶， 1≤j≤r ● 若Wj＜Wj+1,则Pj＜Pj+1，0≤j＜r ●若Wj≤X＜Wj+1，fi(X)=fi(Wj) ●若X≥Wr，fi(X)=fi(Wr) 2018/11/16

87 记 是fi-1(X-wi)+pi的所有序偶的集合，则
● Si的构造 记 是fi-1(X-wi)+pi的所有序偶的集合，则 其中，Si-1是fi-1的所有序偶的集合 Si的构造：由Si-1和 按照支配规则合并而成。 支配规则：如果Si-1和 之一有序偶(Pj,Wj),另一有(Pk,Wk)， 且有 Wj≥Wk , Pj≤ Pk， 则序偶(Pj,Wj)将被舍弃。 （即取最大值规则）。 注： ★ Si中的所有序偶是背包问题KNAP(1,i,X)在X各种 取值下的最优解 2018/11/16

88 例5.12 例5.11的序偶计算 S0={(0,0)} ={(1,2)} S1={(0,0),(1,2)} ={(2,3),(3,5)}
例5.12 例5.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)“支配”而删除 +(1,2) +(2,3) +(5,4) 2018/11/16

89 KNAP(1,n,M)问题的解 ★ Sn是KNAP(1,n,X)在0≤X≤M各种取值下的最优解
xi的推导 xn: 设Sn的最后一对有效序偶是(Pl,Wl)，则(Pl,Wl)或者 是Sn－1的最末一对序偶，或者是(Pj+pn,Wj+wn)，其中 (Pj,Wj)∈ Sn－1且Wj是Sn－1中满足Wj+wn≤M的最大值。 ● 若(Pl,Wl)∈ Sn－1，则Xn＝0；否则， ● (Pl－pn,Wl-wn)∈ Sn－1 ，Xn＝1 xn-1: 若xn=0，则判断(Pl,Wl)∈ Sn－2？，以确定Xn-1的值 若xn=1，则依据(Pl－pn,Wl-wn)∈ Sn－2？，以判断Xn-1的值 xn-2,…,x1将依次推导得出 2018/11/16

90 S0={(0,0)} S1={(0,0),(1,2)} S2={(0,0),(1,2), (2,3),(3,5)}
例5.13 （例5.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)} M=6，f3(6)由S3中的序偶(6,6)给出。 1) ∵(6,6) S2 ∴x3=1 2) ∵(6-p3,6-w3)=(1,2)∈S2且(1,2)∈S1 ∴x2=0 3) ∵(1,2) S0 ∴x1=1 2018/11/16

91 算法5.6 非形式的背包算法 procedure DKP(p,w,n,M) S0 ←{(0,0)} for i←1 to n-1 do
算法5.6 非形式的背包算法 procedure DKP(p,w,n,M) S0 ←{(0,0)} for i←1 to n-1 do ←{(P1,W1)|(P1-pi,W1-wi)∈ Si-1 and W1≤M} Si ←MERGE-PURGE(Si-1, ) repeat (PX,WX)← Sn-1的最末一个有效序偶 (PY,WY)←(P1＋pn,W1+wn)，其中，W1是Sn-1中使得W＋wn≤M的所有序偶中取最大值得W //沿Sn-1,…, S1回溯确定xn,xn-1,…,x1的取值// if PX＞PY then xn←0 //PX将是Sn的最末序偶// else xn←1 //PY将是Sn的最末序偶// endif 回溯确定xn-1,…,x1 end DKP 2018/11/16

92 3. DKP的实现 1)序偶集Si的存储结构 使用两个一维数组P和W存放所有的序偶(Pl,Wl),其中P存放Pl值，W存放Wl值
● 序偶集S0, S1,…, Sn-1顺序、连续存放于P和W中； ● 用指针F(i)表示Si中第一个元素在数组 (P,W)中的下标位置，0≤i≤n; ● F(n)＝Sn-1中最末元素位置＋1 P W F(0)F(1) F(2) F(3) 2018/11/16

93 ★ 中序偶的生成将与 和Si-1的合并同时进行 设 生成的下一序偶是(PQ,WQ)；对所有的(PQ,WQ)，根据支配规则处理如下：
2) 序偶的生成与合并 ★ Si的序偶将按照P和W的递增次序生成 ★ 中序偶的生成将与 和Si-1的合并同时进行 设 生成的下一序偶是(PQ,WQ)；对所有的(PQ,WQ)，根据支配规则处理如下： ⑴ 将Si-1中所有W值小于WQ的序偶直接计入Si中； ⑵ 根据支配规则，若Si-1中有W值小于WQ的序偶支配 (PQ,WQ)，则(PQ,WQ)将被舍弃，否则(PQ,WQ)计入Si中；并清除Si-1中所有可被支配的序偶，这些序偶有W≥WQ且P≤PQ ⑶ 对所有的(PQ,WQ)重复上述处理； ⑷ 将最后Si-1中剩余的序偶直接计入Si中； ⑸ 所有计入Si中的新序偶依次存放到由F(i)指示的Si的存放位 置上。 注：不需要存放 的专用空间 2018/11/16

94 3) 算法的实现 算法5.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// l←h←1 // S0 的首端和末端；l是Si-1的首端，h是Si-1的末端// F(1)←next←2 //P和W中第一个空位；next指示P/W中可以存放(P,W)序偶的第一个位置// for i←1 to n-1 do //生成Si// k←l u←在l≤r≤h中使得W(r)+wi≤M的最大r //u指示由Si-1生成 的最大有效位置// for j←l to u do //生成 ，同时进行归并// (pp,ww)←(P(j)+pi,W(j)+wi) //生成 中的下一个元素// while k≤h and W(k)＜ww do //从Si-1中取元素并归并// P(next)←P(k);W(next)←W(k) //所有W(k)＜ww 的序偶直接归并// next←next+1;k←k＋1 repeat 2018/11/16

95 //按照支配规则考虑(pp,ww)及Si-1中的序偶// if k≤h and W(k)=ww then
pp←max(pp,P(k)) k←k+1 endif if pp＞P(next-1) then (P(next), W(next))←(pp,ww) next←next+1 //清除Si-1中的序偶// while k≤h and P(k)≤P(next-1) do k←k+1 repeat repeat while k≤h do//将Si-1中剩余的元素并入Si // (P(next),W(next))←(P(k),W(k)) next←next+1; k←k+1 //对Si+1置初值 // l←h+1; h←next -1; F(i+1)←next CALL PARTS //递推求取Xn,Xn-1,…,x1// END DKNAP 2018/11/16

96 4. 过程DKNAP的分析 1) 空间复杂度 记Si中的序偶数为：|Si| 则有， |Si|≤ |Si-1|＋| |
故，DKNAP所需的空间复杂度（P、W数组）为:Ο(2n) 2018/11/16

97 且 2) 时间复杂度 由Si-1生成Si的时间为： ，0≤i≤n-1 故，DKNAP计算所有的Si所需的时间为： 注：
若每件物品的重量wi和效益值pi均为整数，则Si中每个序偶(P,W)的P值和W值也是整数，且有 ，W≤M 又，在任一Si中的所有序偶具有互异P值和W值，故有 且 2018/11/16

98 在所有wj和pj均为整数的情况下，DKNAP的时间和空间复杂度将为：
2018/11/16

99 5. 序偶集合的一种启发式生成策略 设L是最优解的估计值，且有fn(M)≥L 设PLEFT(i)=
若正在生成的序偶(P,W)有P＋PLEFT(i)＜L，则(P,W)将不计入Si中。 L的选择： ① 取Si的最末序偶(P,W)的P作为L，P≤fn(M) ② 将某些剩余物品的p值＋P作为L 2018/11/16

100 例5.15 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={0} S1={0,100} S2={0,50,100,150} S3={0,20,50,70,100,120,150} S4={0,10,20,30,50,60,70,80,100,110,120,130,150，160} S5={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} 则，f6(165)=163 注：每对序偶(P,W)仅用单一量P（或W）表示 2018/11/16

101 分析：将物品1,2,4,6装入背包，将占用163的重量并产生163的效益。 故，取期望值L＝163.
启发式规则求解 分析：将物品1,2,4,6装入背包，将占用163的重量并产生163的效益。 故，取期望值L＝163. 按照启发式生成规则，从Si中删除所有P＋PLEFT(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= (w3=20) S3={150} ={160} PLEFT(4)=p5+p6=10 S4={160} = Ø PLEFT(5)=p6= (w5=7) S5={160} PLEFT(6)=0 f6(165)=160+3 ＝ 163 2018/11/16

102 2018/11/16

103 3. 贪心方法的抽象化控制描述 procedure GREEDY(A,n) //A(1:n)包含n个输入//
solution←Φ //将解向量solution初始化为空// for i←1 to n do x←SELECT(A) //按照度量标准，从A中选择一个输入，其值赋予x 并将之从A中删除// if FEASIBLE(solution,x) then //判定x是否可以包含在解向量中， 即是否能共同构成可行解// solution←UNION(solution,x) //将x和当前的解向量合并成新的解 向量，并修改目标函数// endif repeat return(solution) end GREEDY 2018/11/16

104 procedure GREEDY－P(A,L,S) for i←1 to n do S(i)←0 //将解向量初始化为空// repeat
cu←L //cu是磁带的剩余容量// if a(i) > cu then exit endif S(i) ←1 cu ←cu-a(i) end GREEDY-KNAPSACK 2018/11/16

105 设n = 4，且(a1, a2, a3, a4) = (end, goto, print, stop)，又设P(1:4) = (1/20, 1/5, 1/10, 1/20)，Q(0:4) = (1/5, 1/10, 1/5, 1/20, 1/20)，利用动态规划方法，分别计算C(i,j), W(i,j), R(i,j)，并根据结果画出最优二分检索树。 2018/11/16