2009-7-27
第四章 动态规划
4.1 一般方法
1,多阶段决策问题多阶段决策过程,问题的活动过程分为若干相互联系的阶段，任一阶段 i以后的行为仅依赖于 i阶段的过程状态，而与 i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决策称为多阶段决策过程 (multistep decision process) 。
最优化问题,问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所 导致的问题的结果可能不同。
多阶段决策的最优化问题 就是：求能够获得问题最优解的决策序列 ——最优决策序列。
云 图
V
1
V
2
云 图
V
N
云 图
.,,
2009-7-27
2,多阶段决策过程的求解策略
1）枚举法穷举 可能的决策序列，从中选取可以获得最优解的决策序列
2）动态规划
20世纪 50年代初美国数学家 R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的 最优化原理 (principle of optimality)，
把 多阶段 过程转化为一系列 单阶段 问题，创立了解决这类过程优化问题的新方法 ——动态规划 。
动态规划 (dynamic programming)是 运筹学 的一个分支，是求解 决策过程 (decision process)最优化的数学方法。
应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、
资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
2009-7-27
3,最优性原理 (Principle of Optimality)
过程的 最优决策序列 具有如下性质：无论过程的 初始状态 和 初始决策 是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
利用动态规划求解问题的前提
1) 证明问题满足最优性原理如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题
2) 获得问题状态的递推关系式获得各阶段间的递推关系式是解决问题的关键。
2009-7-27
例 4.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∈V i，则 v∈V i＋ 1,
1?i?k － 1。
· 每条边 (u,v)均附有成本 c(u,v)。
s到 t的路径,从第 1段开始，至第 2段、第 3段,?,最后在第 k段终止。路径的 成本 是这条路径上边的成本和。
多段图问题,求由 s到 t的 最小成本路径 。
2009-7-27
1
2
3
4
5
6
7
8
9
10
11
12
9
7
3
2
4
2
2
7
11
11
8
1
4
5
6
3
5
6
4
2
5
V1 V2 V3 V4 V5
5段图
2009-7-27
多段图问题的 多阶段决策过程,生成从 s到 t的最小成本路径是在 k-2个阶段（除 s和 t外）进行某种决策的过程：从 s开始,第 i次决策决定 Vi+1(1≤i≤k-2)中的哪个结点在从 s到 t的最短路径上。
最优性原理对多段图问题成立假设 s,v2,v3,…,v k-1,t是一条由 s到 t的最短路径。
● 初始状态,s
● 初始决策,(s,v2),v2∈V 2
● 初始决策产生的状态,v2
则，其余的决策,v3,...,vk-1相对于 v2将构成一个最优决策序列 ——最优性原理成立。
反证,若不然，设 v2,q3,…,q k-1,t是一条由 v2到 t的更短的路径，
则 s,v2,q3,…,q k-1,t将是比 s,v2,v3,…,v k-1,t更短的从 s到 t的路径。与假设矛盾。
故，最优性原理成立
2009-7-27
例 4.2[0/1背包问题 ] KNAP(l,j,X)
目标函数,
约束条件,
0/1背包问题,KNAP(1,n,M)
ji
iixp
1
jiwpx
Xxw
iii
ji
ii
1,0,0,10
1
或
2009-7-27
最优性原理对 0/1背包问题成立：
设 y1,y2,…,y n是 x1,x2,…,x n的 0/1值最优序列。
若 y1＝ 0,KNAP(2,n,M)是初始决策产生的状态。则 y2,…,y n相对于 KNAP(2,n,M)将构成一个最优序列。否则,y1,y2,…,y n将不是
KNAP(1,n,M)的最优解若 y1＝ 1,KNAP(2,n,M－ w1)是初始决策产生的状态。则
y2,…,y n相对于 KNAP(2,n,M－ w1)将构成一个最优序列。
否则，设存在另一 0/1序列 z2,…,z n,使得且则序列 y1,z2,…,z n将是一个对于 KNAP(1,n,M)具有更大效益值得序列。
故，最优性原理成立
ni ii wMzw2 1
ni ni iiii ypzp2 2
2009-7-27
4,动态规划模型的基本要素一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：
1) 阶段阶段 (step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。
阶段变量一般用 k=1,2,..,n表示。
2009-7-27
2） 状态状态 (state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有 无后向性,即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，
即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。
描述状态的变量称 状态变量 (state variable)。变量允许取值的范围称允许 状态集合 (set of admissible states)。用 xk表示第 k阶段的状态变量，它可以是一个数或一个向量。用 Xk表示第 k阶段的允许状态集合。
状态变量简称为状态
2009-7-27
3）决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为 决策 (decision) 。
描述决策的变量称决策变量 (decision variable)。变量允许取值的范围称允许决策集合 (set of admissible decisions)。用 uk(xk)
表示第 k阶段处于状态 xk时的决策变量，它是 xk的函数，用 Uk(xk)
表示了 xk的允许决策集合。
决策变量简称决策。
2009-7-27
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)，用 P1,n(x1),Pk,n(xk),Pk,j(xk)表示。
2009-7-27
5) 状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知，
下阶段的状态便完全确定。用状态转移方程 (equation of
state)表示这种演变规律，写作
2009-7-27
6) 指标函数和最优值函数指标函数 (objective function)是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段 k到阶段 n的指标函数用 Vk,n(xk,pk,n(xk))表示,k=1,2,...,n。
能够用动态规划解决的问题的指标函数应具有可分离性，即 Vk,n可表为 xk,uk,Vk+1,n 的函数，记为：
2009-7-27
7.最优策略和最优轨线使指标函数 Vk,n达到最优值的策略是从 k开始的后部子过程的最优策略，记作 pk,n*={uk*,..un*},p1,n*又是全过程的最优策略，简称最优策略 (optimal policy)。从初始状态 x1(=x1*)出发，过程按照 p1,n*和状态转移方程演变所经历的状态序列
{x1*,x2*,..,xn+1*}称最优轨线 (optimal trajectory)。
2009-7-27
4,最优决策序列的表示设
● S0：问题的初始状态
● n次决策：问题需要做 n次决策
● xi,i阶段的决策值,1?i?n 。
设 X1={r1,1,r1,2,?,r 1,p1}是 x1可能的决策值的集合,S1,j1是在选择决策值 r1,j1之后所产生的状态 —— 初始决策所产生的状态 。
设 Γ 1,j1是相应于状态 S1,j1的最优决策序列。
则，相应于 S0的最优决策序列就是 {r1,j1Γ 1,j1|1?j 1?p 1}中最优的序列，记为
11,1,11 }{ 1111 rrO P T jjpj
2009-7-27
s0
r1,1
r1,2
.
.
.
r1,p1
sn
Γ1,j1
2009-7-27
若已经做了 k-1次决策,1?k -1＜ n，设 x1,x2,?,x k-1的最优决策值是 r1,r2,?,r k-1，所产生的状态依次为 S1,S2,?,S k-1。
设 Xk={rk,1,rk,2,?,r k,pk}是 xk可能的决策值的集合,Sk,jk是在选择决策值 rk,jk之后所产生的状态,1?j k?p k。 Γ k,jk是相应于状态 Sk,jk的最优决策序列。
则，相应于 Sk-1的最优决策序列是相应于 S0的最优决策序列为 r1,?,r k-1,rk,Γ k
kkjkjkpkj rrO P T kkk }{,,1
2009-7-27
5,递推策略
1）向前处理法列出根据 xi+1,…,x n的最优决策序列求取 xi决策值的关系式。
从最后一个阶段，逐步 向前 递推求出各阶段的决策值。决策序列 x1,x2,…,x n就是问题的最优解。
xn-1,1
…
xn-1,pn-1
xn
2009-7-27
例 4.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
2009-7-27
例 4.4 利用向前处理法求解 k段图问题设 ∈ V2,1≤j2≤p2,|V2|=p2;
是由 到 t的最短路径，则 s到 t的最短路径是
{s | ∈ V2,1≤j2≤p2}中最短的那条路径。
若 s,v2,v3,…,v i,…,v k-1,t是 s到 t的一条最短路径,vi是其中的一个中间点，则 s,v2,v3,…,v i和 vi,…,v k-1,t分别是由 s到 vi和 vi到 t
的最短路径（最优性原理）
从 Vi中的结点 ji到 t的最短路径将是：
min( { | ∈ Vi+1,1≤ji+1≤pi+1})
2,2jv?
2,2 jv
2,2 jv
2,2 jv? 2,2 jv
1,1 ijiv 1,1 ijivi
jiv,
2009-7-27
2） 向后处理法列出根据 x1,…,x i-1的最优决策序列求取 xi决策值的关系式。
从第一个阶段，逐步 向后 递推求出各阶段的决策值。决策序列 x1,x2,…,x n就是问题的最优解。
2009-7-27
例 4.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
2009-7-27
例 4.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,…,v i,…,v k-1,t是 s到 t的一条最短路径,vi是其中的一个中间点，则 s,v2,v3,…,v i和 vi,…,v k-1,t分别是由 s到 vi和 vi到 t
的最短路径（最优性原理）
从 s到 Vi中的结点 ji的最短路径将是：
min( { | ∈ Vi+1,1≤ji+1≤pi+1})
1,1 kjkv
1,1 kjkv 1,1 kjkv
1,1 kjkv 1,1 kjkv
1,1 ijiv 1,1 ijiv
ijiv,
2009-7-27
动态规划的基本思想：
（ 1）动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件。要做到这一点，必须将问题的过程分成几个相互联系的阶段，
恰当选择状态变量，决策变量和定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题的最优解，就是整个问题的最优解。
（ 2）在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前的效益和未来效益综合起来考虑的一种最优化方法。
因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。
（ 3）在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经的各段状态便可逐次变换得到，从而确定最优路线。
2009-7-27
关于动态规划求解策略的进一步说明
采用枚举法：若问题的决策序列由 n次决策构成，而每次决策有 p种选择，则可能的决策序列将有 pn个。
利用动态规划策略的求解过程中保存了所有子问题的最优解，而舍去了所有不能导致问题最优解的次优决策序列
动态规划：可能有多项式的计算复杂度。
2009-7-27
与非线性规划相比，动态规划的优点：
（ 1）易于确定全局最优解。动态规划方法是一种逐步改善法，它把原问题化为一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少的多，约束集合也要简单得多。
（ 2）能得到一族解，有利于分析结果
（ 3）能利用经验，提高求解的效率。动态规划方法反映了过程逐段演变的前后联系，较之非线性规划与实际过程联系得更紧密。
不足之处,
（ 1）没有一个统一的标准模型可供应用。
（ 2）应用的局限性。要求状态变量满足“无后效性”条件，不少实际问题在取其自然特征作为状态变量往往不能满足这条件。
（ 3）在数值求解中，存在“维数障碍”。在计算机中，每递推一段，必须把前一段的最优值函数在相应的状态集合上的全部值存入内存中。当维数增大时，所需的内存量成指数倍增长。
2009-7-27
4.2 多段图问题
1,问题的描述
● 在多段图中求从 s到 t的一条最小成本的路径，可以看作是在 k-2个段作出某种决策的结果。
● 第 i次决策决定 Vi+1中的哪个结点在这条路径上，这里
1?i?k -2；
● 最优性原理对多段图问题成立
2009-7-27
1
2
3
4
5
6
7
8
9
10
11
12
9
7
3
2
4
2
2
7
11
11
8
1
4
5
6
3
5
6
4
2
5
V1 V2 V3 V4 V5
5段图
2009-7-27
枚举 VS 向前处理法
1
10
432
7 39
9
10
9
8676 77
4
2
2
7
1
1
1
1
10
9
10
9 10
10 1111
10 9
5
4
3
5 5
6
4
3 6
6
5
4
3
2
8
1
8
8
6
5
11
6
10
5
12 121212
121212
1212
12
12
12
12121212
4
2
4
2
2
5
4
2
4
2
2
5
4
2
2
5
23 211718212521192216192117161920
7 5 7
7
9
18
15
2009-7-27
2,向前处理策略求解设 P(i,j)是一条从 Vi中的结点 j到汇点 t的最小成本路径，
COST(i,j)是这条路径的成本。
1) 向前递推式
2) 递推过程
★ 第 k-1段
c(j,t) <j,t>∈E
COST(k-1,j) =
∞
)},1(),({m in),(
),( 1
liC O STljcjiC O ST
Elj
vl i
Etj,
2009-7-27
l1
l2
.
.
.
lpi+1
t…
j
Vi Vi+1
2009-7-27
★ 各递推结果第 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) = 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
2009-7-27
★ 最小路径的求取记 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
2009-7-27
3) 算法描述
★ 结点的编号规则源点 s编号为 1,然后依次对 V2,V3?V k-1中的结点编号，
汇点 t编号为 n。
目的：使对 COST和 D的计算仅按 n-1,n-2,?,1 的次序计算即可,无需考虑 标示结点所在 段 的第一个下标。
★ 算法描述
2009-7-27
算法 4.1 多段图的向前处理算法
procedure FGRAPH(E,k,n,P)
//输入是按段的顺序给结点 编号 的，有 n个结点的 k段图。 E是边集,c(i,j)是边 <i,j>的成本。 P(1:k)带出最小成本路径 //
real COST(n); integer D(n-1),P(k),r,j,k,n
COST(n)←0
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)) //回溯求出该路径 //
repeat
end FGRAPH
2009-7-27
算法的时间复杂度若 G采用邻接表表示，总计算时间为：
)( en
2009-7-27
3,向后处理策略求解设 BP(i,j)是一条从源点 s到 Vi中的结点 j的最小成本路径，
BCOST(i,j)是这条路径的成本。
1) 向后递推式
2) 递推过程
★ 第 2段
c(1,j) <1,j>∈E
BCOST(2,j) =
∞
)},(),1({m in),(
),( 1
jlcliB C O STjiB C O ST
Ejl
vl i
Ej,1
2009-7-27
1
2
3
4
5
6
7
8
9
10
11
12
9
7
3
2
4
2
2
7
11
11
8
1
4
5
6
3
5
6
4
2
5
V1 V2 V3 V4 V5
5段图
2009-7-27
★ 各递推结果第 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
2009-7-27
★ 最小路径的求取记 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
2009-7-27
算法 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)) // 回溯求出该路径 //
repeat
end BGRAPH
2009-7-27
4,多段图问题的应用实例将 n个资源分配给 r个项目的问题：如果把 j个资源，
0?j?n,分配给项目 i，可以获得 N(i,j)的净利。
问题：如何将这 n个资源分配给 r个项目才能获得最大可能的净利。转换成一个多段图问题。
2009-7-27
用 r＋ 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)>,该边赋予成本：
)},({m a x0 prNjnp
2009-7-27
实例：将 4个资源分配给 3个项目。构成一个 4段图。
问题的解：资源的最优分配方案是由 s到 t的一条 最大成本 的路径给出 —
—改变边成本的 符号,从而将问题转换成为求取最小成本路径问题。
2009-7-27
4.3 每对结点之间的最短路径
1,问题描述设 G=(V,E)是一个有 n个结点的有向图,C是 G的成本邻接矩阵，
C中元素有：
0,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的 最短路径长度 。
E (G ), ji
2009-7-27
分析：
利用 单源最短路径 算法求解
● 计算 n个结点的单源最短路径。
● 时间复杂度,Ο(n3)
利用 动态规划 策略求解将求解 G中每对结点之间的最短路径问题转化成一个 多阶段决策过程 。
● 决策什么？
● 最优性原理对于该问题是否成立？
2009-7-27
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的最短路径。
故，最优性原理对于该问题成立。
2009-7-27
2） 多阶段决策过程设 k是由 i到 j的最短路径上编号（假设所有 n个结点依次有从 1到
n的编号）最高的中间结点：
i,...,k,…,j
k是编号最高的中间结点则由 i到 k的子路径上将不会有比编号 k-1更大的结点；同理，
由 k到 i的子路径上也将不会有比编号 k-1更大的结点。
构造 多阶段决策过程,对由 i到 j的最短路径，首先决策哪一个结点是该路径上具有 最大编号 的中间结点 k，然后再去求取由 i到 k
和由 k到 j的最短路径 ——其中应不包含比 k-1还大的中间结点。
2009-7-27
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结点
2009-7-27
对任意的 k,k?1,有，
Ak(i,j) = min{Ak-1(i,j),Ak-1(i,k) + Ak-1(k,j)}
不经过结点 k 刚好经过结点 k
初值,
A0(i,j)= C(i,j),1?i?n,1?j?n
递推计算,A1(i,j),A2(i,j),…,A n(i,j)= A (i,j)
2009-7-27
3,算法描述算法 4.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
repeat
for k←1 to n do
for i←1 to n do
for j←1 to n do
A (i,j) ← min{A (i,j),A (i,k) + A (k,j)}
repeat
repeat
repeat
end ALL-PATHS
2009-7-27
算法的设计说明
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）如何求每对结点之间的路径？
2009-7-27
例 4.8 有向图如图所示
A0 1 2 3
1 0 4 11
2 6 0 2
3 3 ∞ 0
A1 1 2 3
1 0 4 11
2 6 0 2
3 3 7 0
A2 1 2 3
1 0 4 6
2 6 0 2
3 3 7 0
A3 1 2 3
1 0 4 6
2 5 0 2
3 3 7 0
6
4
2113
v1 v2
v3
1 2 3
1 0 4 11
2 6 0 2
3 3 ∞ 0
求图中所有结点间的最短路径矩阵 A：
注,A(i,j) = ∞ 表明 G中从 i到 j没有有向路径
2009-7-27
性能分析计算时间＝
注：该时间与 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
repeat
repeat
)( 3n?
2009-7-27
∞ 的处理设 M是 E中最大成本的一条边的成本，则
An(i,j)<=(n-1)*M。因此，对于成本邻接矩阵中的
∞ 用一个大于 (n-1)*M的值代替。如果在算法结束时,A(I,j)> (n-1)*M，则表明 G中没有由 i到 j的有向路径 。
2009-7-27
4.4 最优二分检索树
1,问题的描述
1）二分检索树定义二分检索树Ｔ是一棵 二元树,它或者为 空,或者其每个结点含有一个可以比较大小的数据元素，且有：
· Ｔ的 左子树 的所有元素比根结点中的元素小；
· Ｔ的 右子树 的所有元素比根结点中的元素大；
· Ｔ的左子树和右子树也是二分检索树。
注：
· 二分检索树要求树中所有结点的元素值 互异
2009-7-27
if
for while
repeat
loop
if
for repeat
loop while
对于一个给定的 标识符 集合，可能有 若干棵 不同的二分检索树,
不同形态的二分检索树对标识符的 检索性能 是 不同 的。
2009-7-27
2）二分检索树的检索算法 4.4 SEARCH(T,X,i)
//为 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
2009-7-27
二分检索树的性能特征
① 例图 (a)：
最坏情况 下查找标识符 loop需要做 4次比较；
成功检索 平均 需要做 12/5次比较 ;
图 (b)：
最坏情况 下查找标识符 loop/while需要做 3次比较；
成功检索 平均 需要做 11/5次比较
② 查找概率可以期望不同标识符的 检索频率 是不同的。如
Pfor＞ Pwhile ＞ Ploop
③ 不成功检索可以期望不成功检索出现的 频率 也是不同的。
2009-7-27
3）最优二分检索树问题设给定的标识符集合是 {a1,a2,…,a n}，并假定 a1＜ a2 ＜ … ＜ an 。
设,P(i)是对 ai检索的概率,Q(i)是正被检索的标识符 X恰好满足：
ai ＜ X＜ ai+1,0?i?n （设 a0=-∞,a n+1=+∞) 时的概率，即一种不成功检索情况下的概率。
则 表示所有成功检索的概率表示所有不成功检索的概率考虑所有可能的成功和不成功检索情况，共 2n+1种可能的情况，有
ni i1 )(P
ni i0 )(Q
1Q (i)P (i)
ni0ni1
2009-7-27
二分检索树内结点,代表成功检索情况，刚好有 n个外结点,代表不成功检索情况，刚好有 n＋ 1个关于 {a1,a2,…,a n}的 最优二分检索树 含义如下：
2009-7-27
二分检索树的预期成本预期成本,算法对于所有可能的成功检索情况和不成功检索情况，平均所要做的比较次数。根据期望值计算方法，
平均检索成本 ＝ Σ 每种情况出现的 概率 × 该情况下所需的比较 次数平均检索成本的 构成,成功检索成分 ＋ 不成功检索成分
● 成功检索,在 l级内结点终止的成功检索，需要做 l次比较运算（基于二分检索树结构）。该级上的任意结点 ai的 成本检索的成本分担额 为：
P(i)*level(ai) ；
其中,level(ai) = 结点 ai 的级数 =l
2009-7-27
● 不成功检索,
不成功检索的 等价类,每种不成功检索情况定义了一个等价类，共有 n+1个等价类 Ei(0≤i≤n)。其中，
E0={X|X＜ a0}
Ei={X|ai＜ X＜ ai+1(1≤i＜ n)}
En={X|X＞ an}
若 Ei处于 l级，则算法需作 l-1次迭代。则,l级上的外部结点的 不成功检索的成本分担额 为：
Q(i)*(level(Ei)-1)
则预期总的成本公式表示如下：
)1)((*Q ( i))(*P ( i)
ni0ni1
Eil evelal evel i
2009-7-27
最优二分检索树问题,
求一棵使得 预期成本 最小 的二分检索树例 4.9 标识符集合（ a1,a2,a3） =（ do,if,stop）。可能的二分检索树如下所示。
成 功 检 索,3种
不成功情况,4种
2009-7-27
stop
do
if
do
if
stop
stop
if
do
if
do stop
do
stop
if
(a)
(b)
(c)
(d) (e)
2009-7-27
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)=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.6
if
do stop
do
stop
if
(b)
(c)
2009-7-27
2,多阶段决策过程把构造二分检索树的过程看成一系列决策的结果。
决策的策略：决策树根，如果 {a1,a2,…,a n}存在一棵二分检索树,ak是该树的根，则内结点 a1,a2,…,a k-1和外部结点
E0,E1,…,E k-1将位于根 ak的左子树中，而其余的结点将位于右子树中。
ak
由 ak＋ 1,ak+2,…,a n
及 Ek,Ek+1,…,E n构成的二分检索树由 a1,a2,…,a k-1及
E0,E1,…,E k-1构成的二分检索树
2009-7-27
定义：
含义：
● 左、右子树 的 预期成本 ——左、右子树的 根 处于 第一级
● 左、右子树中所有结点的级数相对于子树的根测定，而相对于原树的根少 1
ki
i
ki
i El eveliQal eveliPLCO S T
01
)1((*)()(*)()(
nik
i
nik
i El eve liQal eve liPRC O S T )1((*)()(*)()(
2009-7-27
记：
则，原二分检索树的预期成本可表示为：
COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n)
最优二分检索树,COST(T)有最小值最优性原理成立若 T最优二分检索树，则 COST(L)和 COST(R)将分别是包含
a1,a2,…,a k-1和 E0,E1,…,E k-1、及 ak＋ 1,ak+2,…,a n和 Ek,Ek+1,…,E n的最优二分检索 (子 )树。
记由 ai+1,ai+2,…,a j和 Ei,Ei+!,…,E j构成的二分检索树的成本为 C(i,j)，则对于最优二分检索树 T有，
COST(L) = C(0,k-1)
COST(R) = C(k,n)
ji lPlQiQjiW 1 ))()(()(),(
2009-7-27
则，
对任何 C(i,j)有，
向前递推过程：
★ 首先计算所有 j-i=1的 C(i,j)
★ 然后依次计算 j-i=2,3,…,0 的 C(i,j)。
★ C(0,n)=最优二分检索树的成本。
初始值
C(i,i) = 0
W(i,i) = Q(i),0?i?n
)},()1,0()(),()1,0({m in),0( 1 nkWkWkPnkCkCnC nk
)},()1,()(),()1,({m in),( jkWkiWkPjkCkiCjiC jki
),()},()1,({m in jiWjkCkiCjki
2009-7-27
最优二分检索树的构造
● 在计算 C(i,j)的过程中，记下使之取得最小值的 k值，
即树 Tij的根，记为 R(i,j)。
● 依据 R(0,n)…,推导树的形态
2009-7-27
例４,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)+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
①
②
③
④
2009-7-27
j-i=2
i=0,j=2 (do if)
W(0,2)=Q(0)+Q(1)+Q(2)+P(1)+P(2)=12
C(0,2)=min{c(0,0)+c(1,2),c(0,1)+C(2,2)} +12=19
R(0,2)=1
i=1,j=3 (if read)
W(1,3)= Q(1)+Q(2)+Q(3)+P(2)+P(3)= 9
C(1,3)=min{c(1,1)+c(2,3),c(1,2)+C(3,3)} +9=12
R(1,3)=2
i=2,j=4 (read while)
W(2,4)= Q(2)+Q(3)+Q(4)+P(3)+P(4)= 5
C(2,4)=min{c(2,2)+c(3,4),C(3,3)+C(4,4)} +5=8
R(2,4)=3
2009-7-27
j-i=3
i=0,j=3 (do if read)
W(0,3)=Q(0)+Q(1)+Q(2)+Q(3)+P(1)+P(2)+P(3)=14
C(0,3)=min{c(0,0)+c(1,3),c(0,1)+C(2,3),C(0,2)+C(3,3)}
+14=25
R(0,3)=2
i=1,j=4 (if read while)
W(1,4)= Q(1)+Q(2)+Q(3)+Q(4)+P(2)+P(3)+P(4)= 11
C(1,4)=min{c(1,1)+c(2,4),c(1,2)+C(3,4),C(1,3)+C(4,4)}
+11=19
R(1,4)=1
2009-7-27
j-i=4
i=0,j=4 (do if read while)
W(0,4)=…=16
C(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)} +16=32
R(0,4)=2
2009-7-27
计算结果则,C(0,4)=32
二分检索树：
T04=2 =>T01(左子树）,T24(右子树）
T01=1 =>T00(左子树）,T11(右子树）
T24=3 =>T22(左子树）,T34(右子树）
0 1 2 3 4
0 2,0,0 3,0,0 1,0,0 1,0,0 1,0,0
1 8,8,1 7,7,2 3,3,3 3,3,4
2 12,19,1 9,12,2 5,8,3
3 16,25,2 11,19,2
4 16,32,2 W(j,j+i),C(j,j+i),R(j,j+i)
2009-7-27
树的形态
if
do read
while
2009-7-27
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,总计算时间为,
一种改进措施（克努特）：最优的 k∈ [R(i,j-1),R(i+1,j)]
)()( 3
1
2 nmnm
nm
2009-7-27
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
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
repeat
end OBST
2009-7-27
OBST算法的计算时间,Ｏ (n2)
2009-7-27
1,问题描述
1) KNAP(1,j,X)
目标函数,
约束条件,
0/1背包问题,KNAP(1,n,M)
最优性原理 对于 0/1背包问题成立求解策略,向前递推,向后递推
ji
iixp
1
jiwpx
Xxw
iii
ji
ii
1,0,0,10
1
或
4.5 0/1背包问题
2009-7-27
为什么 3.2节的贪心策略不成功
n=5; M=100; W=(1,1,1,1,100);
P=(10,10,10,10,100)
背包问题,(1,1,1,1,96/100) 40+96
0/1背包问题,(1,1,1,1,0) 40 < 100
2009-7-27
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}
递推过程：
★ 初始值
0 X?0
f0=
－ ∞ X＜ 0
★ 求出所有可能的 X对应的 fi值。
★ fn(M)=KNAP(1,n,M)
2009-7-27
例 4.11 背包问题
n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5),M=6
递推计算过程
－ ∞ X＜ 0
f0(X)=
0 X≥0
－ ∞ X＜ 0
f1(X)= max{0,－ ∞+1}=0 0≤X＜ 2
max{0,0+1} = 1 X≥2
－ ∞ X＜ 0
0 0≤X＜ 2
f2(X)= 1 2≤X＜ 3
max{1,0+2}=2 3≤X＜ 5
max{1,1+2} = 3 X≥5
f3(M)= max{3,1+5} = 6
2009-7-27
f3(M)= max{3,1+5} = 6
f3(6)= max{f2(6),f2(6-4)+5} = 6
2009-7-27
解向量的推导
f3(M)=6 x3=1
ΔP=6-p3=1 KNAP(1,3,6)=6
ΔM=6-w3=2
X=(1,0,1)
f2(ΔM)=1 x2=0
f1(ΔM)=1 x1=1
2009-7-27
f1,f2,f3计算过程（图解）
1 2 3 4 5 6 70
1
2
f0(x)=0
i:fi-1(x-wi) + pi
i=0:函数不存在
1 2 3 4 5 6 70
1
2
i＝ 1:f0(x-w1) + p1
1 2 3 4 5 6 70
1
2
f1(x)
1 2 3 4 5 6 70
1
2
i＝ 2:f1(x-w2) + p2
3
x
x
x
x
1 2 3 4 5 6 70
1
2
3
x
f2(x)
2009-7-27
1 2 3 4 5 6 70
6
7
8
x
1
2
3
4
5
8 9
i＝ 3:f2(x-w3) + p3
1 2 3 4 5 6 70
6
7
8
x
1
2
3
4
5
8 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相同时 取大值 的规则归并而成
2009-7-27
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)
2009-7-27
● Si的构造记 是 fi-1(X-wj)+pj的所有序偶的集合，则其中,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各种取值下的最优解
}),(|),{( 11 iiii SwWpPWPS
iS1
iS1
iS1
2009-7-27
例 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)“支配” 而删除
11S
21S
31S
2009-7-27
KNAP(1,n,M)问题的解
★ Sn是 KNAP(1,n,X)在 0≤X≤M各种取值下的最优解
★ KNAP(1,n,M)的最优解由 Sn的最后一对 有效序偶 给出。
xi的推导
xn,设 Sn的最后一对 有效序偶 是 (P1,W1)，则 (P1,W1)或者是 Sn－ 1的最末一对序偶，或者是 (Pj+pn,Wj+wn)，其中
(Pj,Wj)∈ Sn－ 1且 Wj是 Sn－ 1中满足 Wj+wn≤M的最大值。
● 若 (P1,W1)∈ Sn－ 1，则 Xn＝ 0；否则，
● (P1－ pn,W1-wn)∈ Sn－ 1,Xn＝ 1
xn-1,若 xn=0，则判断 (P1,W1)∈ Sn－ 2？，以确定 Xn-1的值若 xn=1，则依据 (P1－ pn,W1-wn)∈ Sn－ 2？，以判断 Xn-1的值
xn-2,…,x 1将依次推导得出
2009-7-27
例 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)由 S3中的序偶 (6,6)给出。
1) ∵(6,6) S 2
∴x 3=1
2) ∵(6 -p3,6-w3)=(1,2)∈S 2且 (1,2)∈S 1
∴x 2=0
3) ∵(1,2) S 0
∴x 1=1
2009-7-27
算法 4.6 非形式的背包算法
procedure DKP(p,w,n,M)
S0 ←{(0,0)}
for i←1 to n -1 do
←{(P 1,W1)|(P1-pi,W1-wi)∈ Si-1 and W1≤M}
Si ←MERGE -PURGE(Si-1,)
repeat
(PX,WX)← S n-1的最末一个有效序偶
(PY,WY)←(P1 ＋ pn,W1+wn)，其中,W1是 Sn-1中使得 W＋ wn≤M的所有序偶中取最大值得 W
//沿 Sn-1,…,S 1回溯确定 xn,xn-1,…,x 1的取值 //
if PX＞ PY then xn←0 //PX 将是 Sn的最末序偶 //
else xn←1 //PY 将是 Sn的最末序偶 //
endif
回溯确定 xn-1,…,x 1
end DKP
iS1
iS1
2009-7-27
3,DKP的实现
1)序偶集 Si的存储结构使用两个一维数组 P和 W存放所有的序偶 (P1,W1),其中 P存放 P1值，
W存放 W1值
● 序偶集 S0,S1,…,S n-1顺序,连续 存放于 P和 W中；
● 用指针 F(i)表示 Si中第一个元素在数组
(P,W)中的下标位置,0? i? n;
● 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)
2009-7-27
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的存放位置上。
注：不需要存放 的 专用空间
iS1 iS1
iS1
iS1
2009-7-27
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 //S 0//
l←h←1 // S 0 的首端和末端； 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)+p i,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
iS1
iS1
iS1
2009-7-27
//按照支配规则考虑 (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
endif
//清除 Si-1中的序偶 //
while k≤h and P(k)≤P(next-1) do k←k+1 repeat
repeat
//将 Si-1中剩余的元素并入 Si //
while k≤h do
(P(next),W(next))←(P(k),W(k))
next←next+1; k←k+1
repeat
//对 Si+1置初值 //
l←h+1; h←next -1; F(i+1)←next
repeat
CALL PARTS //递推求取 Xn,Xn-1,…,x 1//
END DKNAP
2009-7-27
4,过程 DKNAP的分析
1) 空间复杂度记 Si中的序偶数为,|Si|
则有,|Si|? |Si-1|＋ | |
又,| |? |Si-1|
所以,|Si|?2 |Si-1|
最坏情况下有（由 Si-1生成 和 Si时没有序偶被支配）,
故,DKNAP所需的空间复杂度（ P,W数组）为,Ο(2n)
i1S
122||
1010
n
ni
i
ni
iS
i1S
i1S
2009-7-27
2) 时间复杂度由 Si-1生成 Si的时间为：,0?i? n-1
故,DKNAP计算所有的 Si所需的时间为：
注：
若每件物品的重量 wi和效益值 pi均为 整数,则 Si中每个序偶
(P,W)的 P值和 W值也是整数，且有,W?M
又，在任一 Si中的所有序偶具有互异 P值和 W值，故有且
|)S(| 1-i?
)2(||
10
1 n
ni
iS
ij jpP 0 ||
ij ji pS 0 ||1|| },||mi n {1|| 0 MwS ij ji
2009-7-27
在所有 wj和 pj均为 整数 的情况下,DKNAP的时间和空间复杂度将为：
}),||,2( m in {
1
nMpn
ni
i
n?
2009-7-27
5,序偶集合的一种启发式生成策略设 L是最优解的估计值，且有 fn(M)?L
设 PLEFT(i)=
若正在生成的序偶 (P,W)有 P＋ PLEFT(i)＜ L，则 (P,W)将不计入 Si中。
L的选择：
① 取 Si的最末序偶 (P,W)的 P作为 L,P?f n(M)
② 将某些剩余物品的 p值＋ P作为 L
nji jp
2009-7-27
例 4.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）表示
2009-7-27
启发式规则求解分析：将物品 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=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
11S
21S
31S
41S
51S
2009-7-27
第五章 基本检索与周游
1.检索与周游检索,以某种方法检查给定的数据对象，找出满足某些给定性质的结点的过程称为 检索周游,当检索过程必须检索到数据对象的每一个结点时，
则该检索过程称为 周游访问结点,当算法对一个结点的信息段进行处理时，称该结点 被访问 。
2009-7-27
2,二元树周游（遍历）
1）周游次序在二元树的周游中，以 D,L,R分别代表访问结点的信息段、访问左子树、访问右子树。则可能的顺序有：
★ LDR：中根次序周游（中根遍历）
★ LRD：后根次序周游（后根遍历）
★ DLR：先根次序周游（先根遍历）
★ RDL：逆中根次序周游
★ RLD：逆后根次序周游
★ DRL：逆先根次序周游
2009-7-27
2）二元树周游算法
⑴ 中根次序周游算法 5.1 中根次序周游的递归表示
procedure INORDER(T)
//T是一棵二元树。 T的每个结点有三个信息段,LCHILD,
DATA,RCHILD//
if T≠0 then
call INORDER(LCHILD(T))
call VISIT(T)
call INORDER(RCHILD(T))
endif
end INORDER
2009-7-27
⑵ 先根次序周游算法 5.2 先根次序周游的递归表示
procedure PREORDER(T)
//T是一棵二元树。 T的每个结点有三个信息段,LCHILD,
DATA,RCHILD//
if T≠0 then
call VISIT(T)
call PREORDER(LCHILD(T))
call PREORDER(RCHILD(T))
endif
end PREORDER
2009-7-27
⑵ 后根次序周游算法 5.2 后根次序周游的递归表示
procedure POSTORDER(T)
//T是一棵二元树。 T的每个结点有三个信息段,LCHILD,
DATA,RCHILD//
if T≠0 then
call POSTORDER(LCHILD(T))
call POSTORDER(RCHILD)
call VISIT(T)
endif
end PREORDER
2009-7-27
注：
一棵二元树可由中根遍历序列＋先根遍历序列、或中根遍历序列＋后根遍历序列 唯一 确定。但 不能 由先根遍历序列＋后根遍历序列唯一确定。
如已知一棵二元树的中根遍历次序是,DGBEAFHC
先根遍历次序是,ABDGECFH
则这棵二元树唯一确定如下,A
B
D E
G
C
F
H
2009-7-27
定理 5.1 当输入的树 T有 n?0 个结点时，设 t(n)和 s(n)分别表示这些周游算法中的任意一个算法所需要的最大时间和空间。如果访问 一个结点 所需要的时间和空间是 Θ(1)，则 t(n)=Θ(n),s(n)=Θ(n)。
证明：
时间,由于已知访问一个结点所需要的时间是 Θ(1)，故可用常数 c1限界。
设 T的左子树中的结点数是 n1，则 t(n)有：
t(n)=maxn1{t(n1)+t(n-n1-1)+c1} n?1
其中,t(0)?c 1。
归纳法证明 t(n)?c 2n+c1，其中 c2是一使得 c2?2c 1的常数。
1)当 n=0时，成立
2)假定当 n=0,1,?,m -1时均成立。则当 n=m时有，
设 T是一棵有 m个结点的树,T左子树结点数为 n1,则
t(n)＝ maxn1{t(n1)+t(n-n1-1)+c1}
max n1{c2n1+c1+c2(n-n1-1)+c1+c1}
＝ maxn1{c2n+3c1-c2}
c 2n+c1
同理，存在 c'2和 c'1有 t(n)?c' 2n+c'1。所以 t(n)=Θ(n)
空间,若 T的深度为 d，则所需空间为 Θ(d),d?n,所以 s(n)=Θ(n)。
2009-7-27
3,树的周游
1) 树的子树顺序无序 → 有序
2)树的周游
⑴ 树的先根次序周游
⑵ 树的中根次序周游
⑶ 树的后根次序周游
2009-7-27
4,图的检索和周游
4.1 宽度优先检索和周游
1) 宽度优先检索
① 从结点 v开始，给 v标上 已到达 （或 访问 ）标记 ——此时称结点 v还没有被 检测,而当算法访问了邻接于某结点的所有结点时，
称该结点被检测了。
② 访问邻接于 v且尚未被访问的所有结点 ——这些结点是新的未被检测的结点。将这些结点依次放置到一 未检测结点表 (队列
Q)中（末端插入） 。
③ 标记 v已被 检测 。
④ 若未检测结点表为空，则算法终止；否则
⑤ 从未检测结点表的表头取一结点作为下一个待检测结点，
重复上述过程。
2009-7-27
算法 5.6 宽度优先检索算法
procedure BFS(v)
//宽度优先检索 G，它从结点 v开始。所有已访问结点被标记为 VISITED(i)=1。 //
VISITED(v)←1;u←v //VISITED(n)是一个标示数组，初始值
VISITED(i)=0,1?i?n //
将 Q初始化为空 //Q是未检测结点的队列 //
loop
for 邻接于 u的所有结点 w do
if VISITED(w)=0 then //w未被检测 //
call ADDQ(w,Q) //ADDQ将 w加入到队列 Q的末端 //
VISITED(w)←1 //同时标示 w已被访问 //
endif
repeat
if Q 为空 then return endif
call DELETEQ(u,Q) //DELETEQ取出队列 Q的表头，并赋给变量 u//
repeat
end BFS
2009-7-27
定理 5.2 算法 BFS可以访问由 v可到达的所有结点证明：设 G=(V,E)是一个 (有向或无向 )图,v∈V 。
归纳法证明定理结论正确。
记 d(v,w)是由 v到达某一可到达结点 w(w∈V) 的最短路径长度。
⑴ 若 d(v,w)?1,则显然这样的所有 w都将被访问。
⑵ 假设对所有 d(v,w)?r 的结点都可被访问。则当 d(v,w)=r+1时有：
设 w是 V中 d(v,w)=r+1的一个结点设 u是从 v到 w的最短路径上紧挨着 w的 前一个 结点。则有
d(v,u)=r。
所以,u可通过 BFS被访问到。
假设 u≠v,且 r?1 。根据 BFS的处理规则,u将在被访问之前的某个时刻被放到未被检测结点队列 Q上，而在另一时刻 u将从队列 Q中移出。此时，所有邻接于 u且尚未被访问的结点将被访问。若结点 w在这之前未被访问，则此刻将被访问到。
由上，定理得证
2009-7-27
定理 5.3 设 t(n,e)和 s(n,e)是算法 BFS在任一具有 n个结点和 e条边的图 G上所花的最大时间和最大附加空间。
● 若 G由邻接表表示，则 t(n,e)=Θ(n+e)和 s(n,e)=Θ(n)。
● 若 G由邻接矩阵表示，则 t(n,e)=Θ(n2)和 s(n,e)=Θ(n)
证明：
1)空间分析根据算法的处理规则，结点 v不会放到队列 Q中。结点 w,w∈V 且 w≠v,
仅在 VISITED(w)=0时由 ADDQ(w,Q)加入队列，并置 VISITED(w)=1，所以每个结点（除 v)至多只有一次被放入队列 Q中。
至多有 n-1个这样的结点考虑，故总共至多做 n-1次结点加入队列的操作。需要的队列空间至多是 n-1。所以 s(n,e)=Ο(n)(其余变量所需的空间为 Ο(1))
当 G是一个具有 v与其余的 n-1个结点相连的图，则邻接于 v地全部 n-1个结点都将在,同一时刻,被放在队列上（ Q至少应有 Ω(n)的空间）。
同时,VISITED(n)本身需要 Θ(n) 的空间。
所以 s(n,e)=Θ(n)—— 这一结论与使用邻接表或邻接矩阵无关。
2009-7-27
2) 时间分析
● G采用邻接表表示判断邻接于 u的结点将在 d(u)时间内完成：若 G是无向图，则 d(u)是
u的度；若 G是有向图，则 d(u)是 u的出度。
> 所有结点的处理时间,Ο(Σ d(u))=Ο(e)。
注：嵌套循环中 对 G中的每一个结点 至多 考虑 一次 。
> VISITED数组的初始化时间,Ο(n)
> 算法总时间,Ο(n+e)。
● G采用邻接矩阵表示
> 判断邻接于 u的所有结点需要 的 时间,Θ(n)
> 所有结点的处理时间,Ο(n2)
> 算法总时间,Ο(n2)
● 如果 G是一个由 v可到达所有结点的图，则将检测到 V中的所有结点，
所以上两种情况所需的总时间至少应是 Ω(n+e)和 Ω(n2)。
所以,t(n,e)=Θ(n+e) 使用邻接表表示或,t(n,e)=Θ(n2) 使用邻接矩阵表示
2009-7-27
2) 宽度优先周游算法 5.7 宽度优先图的周游算法
procedure BFT(G,n)
//G的宽度优先周游 //
int VISITED(n)
for i←1 to n do VISITED(i)←0 repeat
for i←1 to n do // 反复调用 BFS//
if VISITED(i)=0 then call BFS(i) endif
repeat
end BFT
注：若 G是无向连通图或强连通有向图，则 一次 调用 BFS即可完成对 T的周游。否则，需要 多次 调用。
2009-7-27
图周游算法的应用
●判定图 G的 连通性,若调用 BFS的次数多于 1次，则 G为非连通的
●生成图 G的 连通分图,一次调用 BFS中可以访问到的所有结点及连接这些结点的边构成一个连通分图。
●无向图 自反传递闭包矩阵 A*
● 宽度优先生成树向前边,BFS中由 u达到未访问结点 w的边 (u,w)称为向前边。
记 T是 BFS中所处理的所有向前边集合。
宽度优先生成树,若 G是连通图，则 BFS终止时,T构成一棵生成树。
1
2 3
4 5 6 7
8 无向图 G
1
2 3
4 5 6 7
8 G的宽度优先生成树
2009-7-27
定理 5.4 修改算法 BFS，在第 1行和第 6行分别增加语句 T← Φ和
T←T ∪{(u,w)} 。修改后的算法称为 BFS*。若 v是无向图中任一结点，调用 BFS*，算法终止时,T中的边组成 G的一棵生成树。
procedure BFS*(v)
VISITED(v)←1;u←v
T← Φ
将 Q初始化为空
loop
for 邻接于 u的所有结点 w do
if VISITED(w)=0 then //w未被检测 //
T←T ∪{(u,w)}
call ADDQ(w,Q) //ADDQ将 w加入到队列 Q的末端 //
VISITED(w)←1 //同时标示 w已被访问 //
endif
repeat
if Q 为空 then return endif
call DELETEQ(u,Q) //DELETEQ取出队列 Q的表头，并赋给变量 u//
repeat
end BFS*
2009-7-27
证明：
若 G是 n个结点的连通图，则这 n个结点都要被访问。除起始点
v以外，其它 n-1个结点都将被放且仅将被放到队列 Q上一次，从而
T将正好包含 n-1条边，且这些边是各不相同的。即 T是关于 n个结点 n-1边的无向图。
同时，对于连通图 G,T将包含由起始结点 v到其它结点的路径，
所以 T是 连通 的。
则 T是 G的一棵 生成树 。
注：对于 n个结点且正好有 n-1条边的连通图是一棵 树 。
2009-7-27
4.2 深度优先检索和周游
1) 深度优先检索从结点 v开始，首先给 v标上 已到达 （或 访问 ）标记，同时中止对 v的检测，
并开始对邻接于 v且尚未被访问的结点 u检测。在这样的 u均被检测后，再恢复对 v的检测。当所有可到达的结点全部被检测完毕后，算法终止。
算法 5.8 图的深度优先检索
procedure DFS(v)
//已知一个 n结点的无向（或有向）图 G＝ (V,E)以及初值已置为零的数组 VISITED(1:n)。
这个算法访问由 v可以到达的所有结点。 //
VISITED(v)←1
for 邻接于 v的每个结点 w do
if VISITED(w)＝ 0 then call DFS(w) endif
repeat
end DFS
2009-7-27
性质：
① DFS可以访问由 v可到达的所有结点
② 如果 t(n,e)和 s(n,e)表示 DFS对一 n结点 e条边的图所花的最大时间和最大附加空间，则
● s(n,e)=Θ(n)
● t(n,e)= Θ(n+e) G采用 邻接表 表示，或
● t(n,e)= Θ(n2) G采用 邻接矩阵 表示
2) 深度优先周游算法 DFT
反复调用 DFS,直到所有结点均被检测到。
应用：
① 判定图 G的连通性
② 连通分图
③ 无向图自反传递闭包矩阵
④ 深度优先生成树
2009-7-27
深度优先生成树算法
procedure DFS*(v)
T← Φ
VISITED(v)←1
for 邻接于 v的每个结点 w do
if VISITED(w)＝ 0 then
T←T ∪{(u,w)}
call DFS(w)
endif
repeat
end DFS*
2009-7-27
1
2 3
4 5 6 7
8 无向图 G
1
2 3
4 5 6 7
8 G的宽度优先生成树
1
2 3
4 5 6 7
8 G的深度优先生成树
2009-7-27
4.3 BFS,DFS,D_Search算法比较
BFS：使用 队列 保存未被检测的结点。结点按照 宽度优先 的次序被访问和进、出队列。
DFS：使用 栈 保存未被检测的结点，结点按照 深度优先 的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。
D_Search：使用 栈 保存未被检测的结点，结点按照 宽度优先的次序被访问并被依次压入栈中，然后以相反的次序出栈进行新的检测。新的检测结点是最新被访问但未被检测的结点。
BFS检测序列,1 2 3 4 5 6 7 8
DFS检测序列,1 2 4 8 5 6 3 7
D_Search检测序列,1 3 7 8 5 4 6 2
1
2 3
4 5 6 7
8 无向图 G
第四章 动态规划
4.1 一般方法
1,多阶段决策问题多阶段决策过程,问题的活动过程分为若干相互联系的阶段，任一阶段 i以后的行为仅依赖于 i阶段的过程状态，而与 i阶段之前的过程如何达到这种状态的方式无关。在每一个阶段都要做出决策，这一系列的决策称为多阶段决策过程 (multistep decision process) 。
最优化问题,问题的每一阶段可能有多种可供选择的决策，必须从中选择一种决策。各阶段的决策构成一个决策序列。决策序列不同，所 导致的问题的结果可能不同。
多阶段决策的最优化问题 就是：求能够获得问题最优解的决策序列 ——最优决策序列。
云 图
V
1
V
2
云 图
V
N
云 图
.,,
2009-7-27
2,多阶段决策过程的求解策略
1）枚举法穷举 可能的决策序列，从中选取可以获得最优解的决策序列
2）动态规划
20世纪 50年代初美国数学家 R.E.Bellman等人在研究多阶段决策过程的优化问题时，提出了著名的 最优化原理 (principle of optimality)，
把 多阶段 过程转化为一系列 单阶段 问题，创立了解决这类过程优化问题的新方法 ——动态规划 。
动态规划 (dynamic programming)是 运筹学 的一个分支，是求解 决策过程 (decision process)最优化的数学方法。
应用领域：动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、
资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。
2009-7-27
3,最优性原理 (Principle of Optimality)
过程的 最优决策序列 具有如下性质：无论过程的 初始状态 和 初始决策 是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。
利用动态规划求解问题的前提
1) 证明问题满足最优性原理如果对所求解问题证明满足最优性原理，则说明用动态规划方法有可能解决该问题
2) 获得问题状态的递推关系式获得各阶段间的递推关系式是解决问题的关键。
2009-7-27
例 4.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∈V i，则 v∈V i＋ 1,
1?i?k － 1。
· 每条边 (u,v)均附有成本 c(u,v)。
s到 t的路径,从第 1段开始，至第 2段、第 3段,?,最后在第 k段终止。路径的 成本 是这条路径上边的成本和。
多段图问题,求由 s到 t的 最小成本路径 。
2009-7-27
1
2
3
4
5
6
7
8
9
10
11
12
9
7
3
2
4
2
2
7
11
11
8
1
4
5
6
3
5
6
4
2
5
V1 V2 V3 V4 V5
5段图
2009-7-27
多段图问题的 多阶段决策过程,生成从 s到 t的最小成本路径是在 k-2个阶段（除 s和 t外）进行某种决策的过程：从 s开始,第 i次决策决定 Vi+1(1≤i≤k-2)中的哪个结点在从 s到 t的最短路径上。
最优性原理对多段图问题成立假设 s,v2,v3,…,v k-1,t是一条由 s到 t的最短路径。
● 初始状态,s
● 初始决策,(s,v2),v2∈V 2
● 初始决策产生的状态,v2
则，其余的决策,v3,...,vk-1相对于 v2将构成一个最优决策序列 ——最优性原理成立。
反证,若不然，设 v2,q3,…,q k-1,t是一条由 v2到 t的更短的路径，
则 s,v2,q3,…,q k-1,t将是比 s,v2,v3,…,v k-1,t更短的从 s到 t的路径。与假设矛盾。
故，最优性原理成立
2009-7-27
例 4.2[0/1背包问题 ] KNAP(l,j,X)
目标函数,
约束条件,
0/1背包问题,KNAP(1,n,M)
ji
iixp
1
jiwpx
Xxw
iii
ji
ii
1,0,0,10
1
或
2009-7-27
最优性原理对 0/1背包问题成立：
设 y1,y2,…,y n是 x1,x2,…,x n的 0/1值最优序列。
若 y1＝ 0,KNAP(2,n,M)是初始决策产生的状态。则 y2,…,y n相对于 KNAP(2,n,M)将构成一个最优序列。否则,y1,y2,…,y n将不是
KNAP(1,n,M)的最优解若 y1＝ 1,KNAP(2,n,M－ w1)是初始决策产生的状态。则
y2,…,y n相对于 KNAP(2,n,M－ w1)将构成一个最优序列。
否则，设存在另一 0/1序列 z2,…,z n,使得且则序列 y1,z2,…,z n将是一个对于 KNAP(1,n,M)具有更大效益值得序列。
故，最优性原理成立
ni ii wMzw2 1
ni ni iiii ypzp2 2
2009-7-27
4,动态规划模型的基本要素一个多阶段决策过程最优化问题的动态规划模型通常包含以下要素：
1) 阶段阶段 (step)是对整个过程的自然划分。通常根据时间顺序或空间特征来划分阶段，以便按阶段的次序解优化问题。
阶段变量一般用 k=1,2,..,n表示。
2009-7-27
2） 状态状态 (state)表示每个阶段开始时过程所处的自然状况。它应该能够描述过程的特征并且具有 无后向性,即当某阶段的状态给定时，这个阶段以后过程的演变与该阶段以前各阶段的状态无关，
即每个状态都是过去历史的一个完整总结。通常还要求状态是直接或间接可以观测的。
描述状态的变量称 状态变量 (state variable)。变量允许取值的范围称允许 状态集合 (set of admissible states)。用 xk表示第 k阶段的状态变量，它可以是一个数或一个向量。用 Xk表示第 k阶段的允许状态集合。
状态变量简称为状态
2009-7-27
3）决策当一个阶段的状态确定后，可以作出各种选择从而演变到下一阶段的某个状态，这种选择手段称为 决策 (decision) 。
描述决策的变量称决策变量 (decision variable)。变量允许取值的范围称允许决策集合 (set of admissible decisions)。用 uk(xk)
表示第 k阶段处于状态 xk时的决策变量，它是 xk的函数，用 Uk(xk)
表示了 xk的允许决策集合。
决策变量简称决策。
2009-7-27
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)，用 P1,n(x1),Pk,n(xk),Pk,j(xk)表示。
2009-7-27
5) 状态转移方程在确定性过程中，一旦某阶段的状态和决策为已知，
下阶段的状态便完全确定。用状态转移方程 (equation of
state)表示这种演变规律，写作
2009-7-27
6) 指标函数和最优值函数指标函数 (objective function)是衡量过程优劣的数量指标，它是关于策略的数量函数，从阶段 k到阶段 n的指标函数用 Vk,n(xk,pk,n(xk))表示,k=1,2,...,n。
能够用动态规划解决的问题的指标函数应具有可分离性，即 Vk,n可表为 xk,uk,Vk+1,n 的函数，记为：
2009-7-27
7.最优策略和最优轨线使指标函数 Vk,n达到最优值的策略是从 k开始的后部子过程的最优策略，记作 pk,n*={uk*,..un*},p1,n*又是全过程的最优策略，简称最优策略 (optimal policy)。从初始状态 x1(=x1*)出发，过程按照 p1,n*和状态转移方程演变所经历的状态序列
{x1*,x2*,..,xn+1*}称最优轨线 (optimal trajectory)。
2009-7-27
4,最优决策序列的表示设
● S0：问题的初始状态
● n次决策：问题需要做 n次决策
● xi,i阶段的决策值,1?i?n 。
设 X1={r1,1,r1,2,?,r 1,p1}是 x1可能的决策值的集合,S1,j1是在选择决策值 r1,j1之后所产生的状态 —— 初始决策所产生的状态 。
设 Γ 1,j1是相应于状态 S1,j1的最优决策序列。
则，相应于 S0的最优决策序列就是 {r1,j1Γ 1,j1|1?j 1?p 1}中最优的序列，记为
11,1,11 }{ 1111 rrO P T jjpj
2009-7-27
s0
r1,1
r1,2
.
.
.
r1,p1
sn
Γ1,j1
2009-7-27
若已经做了 k-1次决策,1?k -1＜ n，设 x1,x2,?,x k-1的最优决策值是 r1,r2,?,r k-1，所产生的状态依次为 S1,S2,?,S k-1。
设 Xk={rk,1,rk,2,?,r k,pk}是 xk可能的决策值的集合,Sk,jk是在选择决策值 rk,jk之后所产生的状态,1?j k?p k。 Γ k,jk是相应于状态 Sk,jk的最优决策序列。
则，相应于 Sk-1的最优决策序列是相应于 S0的最优决策序列为 r1,?,r k-1,rk,Γ k
kkjkjkpkj rrO P T kkk }{,,1
2009-7-27
5,递推策略
1）向前处理法列出根据 xi+1,…,x n的最优决策序列求取 xi决策值的关系式。
从最后一个阶段，逐步 向前 递推求出各阶段的决策值。决策序列 x1,x2,…,x n就是问题的最优解。
xn-1,1
…
xn-1,pn-1
xn
2009-7-27
例 4.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
2009-7-27
例 4.4 利用向前处理法求解 k段图问题设 ∈ V2,1≤j2≤p2,|V2|=p2;
是由 到 t的最短路径，则 s到 t的最短路径是
{s | ∈ V2,1≤j2≤p2}中最短的那条路径。
若 s,v2,v3,…,v i,…,v k-1,t是 s到 t的一条最短路径,vi是其中的一个中间点，则 s,v2,v3,…,v i和 vi,…,v k-1,t分别是由 s到 vi和 vi到 t
的最短路径（最优性原理）
从 Vi中的结点 ji到 t的最短路径将是：
min( { | ∈ Vi+1,1≤ji+1≤pi+1})
2,2jv?
2,2 jv
2,2 jv
2,2 jv? 2,2 jv
1,1 ijiv 1,1 ijivi
jiv,
2009-7-27
2） 向后处理法列出根据 x1,…,x i-1的最优决策序列求取 xi决策值的关系式。
从第一个阶段，逐步 向后 递推求出各阶段的决策值。决策序列 x1,x2,…,x n就是问题的最优解。
2009-7-27
例 4.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
2009-7-27
例 4.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,…,v i,…,v k-1,t是 s到 t的一条最短路径,vi是其中的一个中间点，则 s,v2,v3,…,v i和 vi,…,v k-1,t分别是由 s到 vi和 vi到 t
的最短路径（最优性原理）
从 s到 Vi中的结点 ji的最短路径将是：
min( { | ∈ Vi+1,1≤ji+1≤pi+1})
1,1 kjkv
1,1 kjkv 1,1 kjkv
1,1 kjkv 1,1 kjkv
1,1 ijiv 1,1 ijiv
ijiv,
2009-7-27
动态规划的基本思想：
（ 1）动态规划方法的关键在于正确写出基本的递推关系式和恰当的边界条件。要做到这一点，必须将问题的过程分成几个相互联系的阶段，
恰当选择状态变量，决策变量和定义最优值函数，从而把一个大问题化成一族同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题的最优解，就是整个问题的最优解。
（ 2）在多阶段决策过程中，动态规划方法是既把当前一段和未来各段分开，又把当前的效益和未来效益综合起来考虑的一种最优化方法。
因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的。
（ 3）在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经的各段状态便可逐次变换得到，从而确定最优路线。
2009-7-27
关于动态规划求解策略的进一步说明
采用枚举法：若问题的决策序列由 n次决策构成，而每次决策有 p种选择，则可能的决策序列将有 pn个。
利用动态规划策略的求解过程中保存了所有子问题的最优解，而舍去了所有不能导致问题最优解的次优决策序列
动态规划：可能有多项式的计算复杂度。
2009-7-27
与非线性规划相比，动态规划的优点：
（ 1）易于确定全局最优解。动态规划方法是一种逐步改善法，它把原问题化为一系列结构相似的最优化子问题，而每个子问题的变量个数比原问题少的多，约束集合也要简单得多。
（ 2）能得到一族解，有利于分析结果
（ 3）能利用经验，提高求解的效率。动态规划方法反映了过程逐段演变的前后联系，较之非线性规划与实际过程联系得更紧密。
不足之处,
（ 1）没有一个统一的标准模型可供应用。
（ 2）应用的局限性。要求状态变量满足“无后效性”条件，不少实际问题在取其自然特征作为状态变量往往不能满足这条件。
（ 3）在数值求解中，存在“维数障碍”。在计算机中，每递推一段，必须把前一段的最优值函数在相应的状态集合上的全部值存入内存中。当维数增大时，所需的内存量成指数倍增长。
2009-7-27
4.2 多段图问题
1,问题的描述
● 在多段图中求从 s到 t的一条最小成本的路径，可以看作是在 k-2个段作出某种决策的结果。
● 第 i次决策决定 Vi+1中的哪个结点在这条路径上，这里
1?i?k -2；
● 最优性原理对多段图问题成立
2009-7-27
1
2
3
4
5
6
7
8
9
10
11
12
9
7
3
2
4
2
2
7
11
11
8
1
4
5
6
3
5
6
4
2
5
V1 V2 V3 V4 V5
5段图
2009-7-27
枚举 VS 向前处理法
1
10
432
7 39
9
10
9
8676 77
4
2
2
7
1
1
1
1
10
9
10
9 10
10 1111
10 9
5
4
3
5 5
6
4
3 6
6
5
4
3
2
8
1
8
8
6
5
11
6
10
5
12 121212
121212
1212
12
12
12
12121212
4
2
4
2
2
5
4
2
4
2
2
5
4
2
2
5
23 211718212521192216192117161920
7 5 7
7
9
18
15
2009-7-27
2,向前处理策略求解设 P(i,j)是一条从 Vi中的结点 j到汇点 t的最小成本路径，
COST(i,j)是这条路径的成本。
1) 向前递推式
2) 递推过程
★ 第 k-1段
c(j,t) <j,t>∈E
COST(k-1,j) =
∞
)},1(),({m in),(
),( 1
liC O STljcjiC O ST
Elj
vl i
Etj,
2009-7-27
l1
l2
.
.
.
lpi+1
t…
j
Vi Vi+1
2009-7-27
★ 各递推结果第 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) = 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
2009-7-27
★ 最小路径的求取记 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
2009-7-27
3) 算法描述
★ 结点的编号规则源点 s编号为 1,然后依次对 V2,V3?V k-1中的结点编号，
汇点 t编号为 n。
目的：使对 COST和 D的计算仅按 n-1,n-2,?,1 的次序计算即可,无需考虑 标示结点所在 段 的第一个下标。
★ 算法描述
2009-7-27
算法 4.1 多段图的向前处理算法
procedure FGRAPH(E,k,n,P)
//输入是按段的顺序给结点 编号 的，有 n个结点的 k段图。 E是边集,c(i,j)是边 <i,j>的成本。 P(1:k)带出最小成本路径 //
real COST(n); integer D(n-1),P(k),r,j,k,n
COST(n)←0
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)) //回溯求出该路径 //
repeat
end FGRAPH
2009-7-27
算法的时间复杂度若 G采用邻接表表示，总计算时间为：
)( en
2009-7-27
3,向后处理策略求解设 BP(i,j)是一条从源点 s到 Vi中的结点 j的最小成本路径，
BCOST(i,j)是这条路径的成本。
1) 向后递推式
2) 递推过程
★ 第 2段
c(1,j) <1,j>∈E
BCOST(2,j) =
∞
)},(),1({m in),(
),( 1
jlcliB C O STjiB C O ST
Ejl
vl i
Ej,1
2009-7-27
1
2
3
4
5
6
7
8
9
10
11
12
9
7
3
2
4
2
2
7
11
11
8
1
4
5
6
3
5
6
4
2
5
V1 V2 V3 V4 V5
5段图
2009-7-27
★ 各递推结果第 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
2009-7-27
★ 最小路径的求取记 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
2009-7-27
算法 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)) // 回溯求出该路径 //
repeat
end BGRAPH
2009-7-27
4,多段图问题的应用实例将 n个资源分配给 r个项目的问题：如果把 j个资源，
0?j?n,分配给项目 i，可以获得 N(i,j)的净利。
问题：如何将这 n个资源分配给 r个项目才能获得最大可能的净利。转换成一个多段图问题。
2009-7-27
用 r＋ 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)>,该边赋予成本：
)},({m a x0 prNjnp
2009-7-27
实例：将 4个资源分配给 3个项目。构成一个 4段图。
问题的解：资源的最优分配方案是由 s到 t的一条 最大成本 的路径给出 —
—改变边成本的 符号,从而将问题转换成为求取最小成本路径问题。
2009-7-27
4.3 每对结点之间的最短路径
1,问题描述设 G=(V,E)是一个有 n个结点的有向图,C是 G的成本邻接矩阵，
C中元素有：
0,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的 最短路径长度 。
E (G ), ji
2009-7-27
分析：
利用 单源最短路径 算法求解
● 计算 n个结点的单源最短路径。
● 时间复杂度,Ο(n3)
利用 动态规划 策略求解将求解 G中每对结点之间的最短路径问题转化成一个 多阶段决策过程 。
● 决策什么？
● 最优性原理对于该问题是否成立？
2009-7-27
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的最短路径。
故，最优性原理对于该问题成立。
2009-7-27
2） 多阶段决策过程设 k是由 i到 j的最短路径上编号（假设所有 n个结点依次有从 1到
n的编号）最高的中间结点：
i,...,k,…,j
k是编号最高的中间结点则由 i到 k的子路径上将不会有比编号 k-1更大的结点；同理，
由 k到 i的子路径上也将不会有比编号 k-1更大的结点。
构造 多阶段决策过程,对由 i到 j的最短路径，首先决策哪一个结点是该路径上具有 最大编号 的中间结点 k，然后再去求取由 i到 k
和由 k到 j的最短路径 ——其中应不包含比 k-1还大的中间结点。
2009-7-27
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结点
2009-7-27
对任意的 k,k?1,有，
Ak(i,j) = min{Ak-1(i,j),Ak-1(i,k) + Ak-1(k,j)}
不经过结点 k 刚好经过结点 k
初值,
A0(i,j)= C(i,j),1?i?n,1?j?n
递推计算,A1(i,j),A2(i,j),…,A n(i,j)= A (i,j)
2009-7-27
3,算法描述算法 4.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
repeat
for k←1 to n do
for i←1 to n do
for j←1 to n do
A (i,j) ← min{A (i,j),A (i,k) + A (k,j)}
repeat
repeat
repeat
end ALL-PATHS
2009-7-27
算法的设计说明
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）如何求每对结点之间的路径？
2009-7-27
例 4.8 有向图如图所示
A0 1 2 3
1 0 4 11
2 6 0 2
3 3 ∞ 0
A1 1 2 3
1 0 4 11
2 6 0 2
3 3 7 0
A2 1 2 3
1 0 4 6
2 6 0 2
3 3 7 0
A3 1 2 3
1 0 4 6
2 5 0 2
3 3 7 0
6
4
2113
v1 v2
v3
1 2 3
1 0 4 11
2 6 0 2
3 3 ∞ 0
求图中所有结点间的最短路径矩阵 A：
注,A(i,j) = ∞ 表明 G中从 i到 j没有有向路径
2009-7-27
性能分析计算时间＝
注：该时间与 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
repeat
repeat
)( 3n?
2009-7-27
∞ 的处理设 M是 E中最大成本的一条边的成本，则
An(i,j)<=(n-1)*M。因此，对于成本邻接矩阵中的
∞ 用一个大于 (n-1)*M的值代替。如果在算法结束时,A(I,j)> (n-1)*M，则表明 G中没有由 i到 j的有向路径 。
2009-7-27
4.4 最优二分检索树
1,问题的描述
1）二分检索树定义二分检索树Ｔ是一棵 二元树,它或者为 空,或者其每个结点含有一个可以比较大小的数据元素，且有：
· Ｔ的 左子树 的所有元素比根结点中的元素小；
· Ｔ的 右子树 的所有元素比根结点中的元素大；
· Ｔ的左子树和右子树也是二分检索树。
注：
· 二分检索树要求树中所有结点的元素值 互异
2009-7-27
if
for while
repeat
loop
if
for repeat
loop while
对于一个给定的 标识符 集合，可能有 若干棵 不同的二分检索树,
不同形态的二分检索树对标识符的 检索性能 是 不同 的。
2009-7-27
2）二分检索树的检索算法 4.4 SEARCH(T,X,i)
//为 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
2009-7-27
二分检索树的性能特征
① 例图 (a)：
最坏情况 下查找标识符 loop需要做 4次比较；
成功检索 平均 需要做 12/5次比较 ;
图 (b)：
最坏情况 下查找标识符 loop/while需要做 3次比较；
成功检索 平均 需要做 11/5次比较
② 查找概率可以期望不同标识符的 检索频率 是不同的。如
Pfor＞ Pwhile ＞ Ploop
③ 不成功检索可以期望不成功检索出现的 频率 也是不同的。
2009-7-27
3）最优二分检索树问题设给定的标识符集合是 {a1,a2,…,a n}，并假定 a1＜ a2 ＜ … ＜ an 。
设,P(i)是对 ai检索的概率,Q(i)是正被检索的标识符 X恰好满足：
ai ＜ X＜ ai+1,0?i?n （设 a0=-∞,a n+1=+∞) 时的概率，即一种不成功检索情况下的概率。
则 表示所有成功检索的概率表示所有不成功检索的概率考虑所有可能的成功和不成功检索情况，共 2n+1种可能的情况，有
ni i1 )(P
ni i0 )(Q
1Q (i)P (i)
ni0ni1
2009-7-27
二分检索树内结点,代表成功检索情况，刚好有 n个外结点,代表不成功检索情况，刚好有 n＋ 1个关于 {a1,a2,…,a n}的 最优二分检索树 含义如下：
2009-7-27
二分检索树的预期成本预期成本,算法对于所有可能的成功检索情况和不成功检索情况，平均所要做的比较次数。根据期望值计算方法，
平均检索成本 ＝ Σ 每种情况出现的 概率 × 该情况下所需的比较 次数平均检索成本的 构成,成功检索成分 ＋ 不成功检索成分
● 成功检索,在 l级内结点终止的成功检索，需要做 l次比较运算（基于二分检索树结构）。该级上的任意结点 ai的 成本检索的成本分担额 为：
P(i)*level(ai) ；
其中,level(ai) = 结点 ai 的级数 =l
2009-7-27
● 不成功检索,
不成功检索的 等价类,每种不成功检索情况定义了一个等价类，共有 n+1个等价类 Ei(0≤i≤n)。其中，
E0={X|X＜ a0}
Ei={X|ai＜ X＜ ai+1(1≤i＜ n)}
En={X|X＞ an}
若 Ei处于 l级，则算法需作 l-1次迭代。则,l级上的外部结点的 不成功检索的成本分担额 为：
Q(i)*(level(Ei)-1)
则预期总的成本公式表示如下：
)1)((*Q ( i))(*P ( i)
ni0ni1
Eil evelal evel i
2009-7-27
最优二分检索树问题,
求一棵使得 预期成本 最小 的二分检索树例 4.9 标识符集合（ a1,a2,a3） =（ do,if,stop）。可能的二分检索树如下所示。
成 功 检 索,3种
不成功情况,4种
2009-7-27
stop
do
if
do
if
stop
stop
if
do
if
do stop
do
stop
if
(a)
(b)
(c)
(d) (e)
2009-7-27
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)=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.6
if
do stop
do
stop
if
(b)
(c)
2009-7-27
2,多阶段决策过程把构造二分检索树的过程看成一系列决策的结果。
决策的策略：决策树根，如果 {a1,a2,…,a n}存在一棵二分检索树,ak是该树的根，则内结点 a1,a2,…,a k-1和外部结点
E0,E1,…,E k-1将位于根 ak的左子树中，而其余的结点将位于右子树中。
ak
由 ak＋ 1,ak+2,…,a n
及 Ek,Ek+1,…,E n构成的二分检索树由 a1,a2,…,a k-1及
E0,E1,…,E k-1构成的二分检索树
2009-7-27
定义：
含义：
● 左、右子树 的 预期成本 ——左、右子树的 根 处于 第一级
● 左、右子树中所有结点的级数相对于子树的根测定，而相对于原树的根少 1
ki
i
ki
i El eveliQal eveliPLCO S T
01
)1((*)()(*)()(
nik
i
nik
i El eve liQal eve liPRC O S T )1((*)()(*)()(
2009-7-27
记：
则，原二分检索树的预期成本可表示为：
COST(T)=P(k)+COST(L)+COST(R)+W(0,k-1)+W(k,n)
最优二分检索树,COST(T)有最小值最优性原理成立若 T最优二分检索树，则 COST(L)和 COST(R)将分别是包含
a1,a2,…,a k-1和 E0,E1,…,E k-1、及 ak＋ 1,ak+2,…,a n和 Ek,Ek+1,…,E n的最优二分检索 (子 )树。
记由 ai+1,ai+2,…,a j和 Ei,Ei+!,…,E j构成的二分检索树的成本为 C(i,j)，则对于最优二分检索树 T有，
COST(L) = C(0,k-1)
COST(R) = C(k,n)
ji lPlQiQjiW 1 ))()(()(),(
2009-7-27
则，
对任何 C(i,j)有，
向前递推过程：
★ 首先计算所有 j-i=1的 C(i,j)
★ 然后依次计算 j-i=2,3,…,0 的 C(i,j)。
★ C(0,n)=最优二分检索树的成本。
初始值
C(i,i) = 0
W(i,i) = Q(i),0?i?n
)},()1,0()(),()1,0({m in),0( 1 nkWkWkPnkCkCnC nk
)},()1,()(),()1,({m in),( jkWkiWkPjkCkiCjiC jki
),()},()1,({m in jiWjkCkiCjki
2009-7-27
最优二分检索树的构造
● 在计算 C(i,j)的过程中，记下使之取得最小值的 k值，
即树 Tij的根，记为 R(i,j)。
● 依据 R(0,n)…,推导树的形态
2009-7-27
例４,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)+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
①
②
③
④
2009-7-27
j-i=2
i=0,j=2 (do if)
W(0,2)=Q(0)+Q(1)+Q(2)+P(1)+P(2)=12
C(0,2)=min{c(0,0)+c(1,2),c(0,1)+C(2,2)} +12=19
R(0,2)=1
i=1,j=3 (if read)
W(1,3)= Q(1)+Q(2)+Q(3)+P(2)+P(3)= 9
C(1,3)=min{c(1,1)+c(2,3),c(1,2)+C(3,3)} +9=12
R(1,3)=2
i=2,j=4 (read while)
W(2,4)= Q(2)+Q(3)+Q(4)+P(3)+P(4)= 5
C(2,4)=min{c(2,2)+c(3,4),C(3,3)+C(4,4)} +5=8
R(2,4)=3
2009-7-27
j-i=3
i=0,j=3 (do if read)
W(0,3)=Q(0)+Q(1)+Q(2)+Q(3)+P(1)+P(2)+P(3)=14
C(0,3)=min{c(0,0)+c(1,3),c(0,1)+C(2,3),C(0,2)+C(3,3)}
+14=25
R(0,3)=2
i=1,j=4 (if read while)
W(1,4)= Q(1)+Q(2)+Q(3)+Q(4)+P(2)+P(3)+P(4)= 11
C(1,4)=min{c(1,1)+c(2,4),c(1,2)+C(3,4),C(1,3)+C(4,4)}
+11=19
R(1,4)=1
2009-7-27
j-i=4
i=0,j=4 (do if read while)
W(0,4)=…=16
C(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)} +16=32
R(0,4)=2
2009-7-27
计算结果则,C(0,4)=32
二分检索树：
T04=2 =>T01(左子树）,T24(右子树）
T01=1 =>T00(左子树）,T11(右子树）
T24=3 =>T22(左子树）,T34(右子树）
0 1 2 3 4
0 2,0,0 3,0,0 1,0,0 1,0,0 1,0,0
1 8,8,1 7,7,2 3,3,3 3,3,4
2 12,19,1 9,12,2 5,8,3
3 16,25,2 11,19,2
4 16,32,2 W(j,j+i),C(j,j+i),R(j,j+i)
2009-7-27
树的形态
if
do read
while
2009-7-27
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,总计算时间为,
一种改进措施（克努特）：最优的 k∈ [R(i,j-1),R(i+1,j)]
)()( 3
1
2 nmnm
nm
2009-7-27
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
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
repeat
end OBST
2009-7-27
OBST算法的计算时间,Ｏ (n2)
2009-7-27
1,问题描述
1) KNAP(1,j,X)
目标函数,
约束条件,
0/1背包问题,KNAP(1,n,M)
最优性原理 对于 0/1背包问题成立求解策略,向前递推,向后递推
ji
iixp
1
jiwpx
Xxw
iii
ji
ii
1,0,0,10
1
或
4.5 0/1背包问题
2009-7-27
为什么 3.2节的贪心策略不成功
n=5; M=100; W=(1,1,1,1,100);
P=(10,10,10,10,100)
背包问题,(1,1,1,1,96/100) 40+96
0/1背包问题,(1,1,1,1,0) 40 < 100
2009-7-27
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}
递推过程：
★ 初始值
0 X?0
f0=
－ ∞ X＜ 0
★ 求出所有可能的 X对应的 fi值。
★ fn(M)=KNAP(1,n,M)
2009-7-27
例 4.11 背包问题
n=3,(w1,w2,w3)=(2,3,4),(p1,p2,p3)=(1,2,5),M=6
递推计算过程
－ ∞ X＜ 0
f0(X)=
0 X≥0
－ ∞ X＜ 0
f1(X)= max{0,－ ∞+1}=0 0≤X＜ 2
max{0,0+1} = 1 X≥2
－ ∞ X＜ 0
0 0≤X＜ 2
f2(X)= 1 2≤X＜ 3
max{1,0+2}=2 3≤X＜ 5
max{1,1+2} = 3 X≥5
f3(M)= max{3,1+5} = 6
2009-7-27
f3(M)= max{3,1+5} = 6
f3(6)= max{f2(6),f2(6-4)+5} = 6
2009-7-27
解向量的推导
f3(M)=6 x3=1
ΔP=6-p3=1 KNAP(1,3,6)=6
ΔM=6-w3=2
X=(1,0,1)
f2(ΔM)=1 x2=0
f1(ΔM)=1 x1=1
2009-7-27
f1,f2,f3计算过程（图解）
1 2 3 4 5 6 70
1
2
f0(x)=0
i:fi-1(x-wi) + pi
i=0:函数不存在
1 2 3 4 5 6 70
1
2
i＝ 1:f0(x-w1) + p1
1 2 3 4 5 6 70
1
2
f1(x)
1 2 3 4 5 6 70
1
2
i＝ 2:f1(x-w2) + p2
3
x
x
x
x
1 2 3 4 5 6 70
1
2
3
x
f2(x)
2009-7-27
1 2 3 4 5 6 70
6
7
8
x
1
2
3
4
5
8 9
i＝ 3:f2(x-w3) + p3
1 2 3 4 5 6 70
6
7
8
x
1
2
3
4
5
8 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相同时 取大值 的规则归并而成
2009-7-27
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)
2009-7-27
● Si的构造记 是 fi-1(X-wj)+pj的所有序偶的集合，则其中,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各种取值下的最优解
}),(|),{( 11 iiii SwWpPWPS
iS1
iS1
iS1
2009-7-27
例 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)“支配” 而删除
11S
21S
31S
2009-7-27
KNAP(1,n,M)问题的解
★ Sn是 KNAP(1,n,X)在 0≤X≤M各种取值下的最优解
★ KNAP(1,n,M)的最优解由 Sn的最后一对 有效序偶 给出。
xi的推导
xn,设 Sn的最后一对 有效序偶 是 (P1,W1)，则 (P1,W1)或者是 Sn－ 1的最末一对序偶，或者是 (Pj+pn,Wj+wn)，其中
(Pj,Wj)∈ Sn－ 1且 Wj是 Sn－ 1中满足 Wj+wn≤M的最大值。
● 若 (P1,W1)∈ Sn－ 1，则 Xn＝ 0；否则，
● (P1－ pn,W1-wn)∈ Sn－ 1,Xn＝ 1
xn-1,若 xn=0，则判断 (P1,W1)∈ Sn－ 2？，以确定 Xn-1的值若 xn=1，则依据 (P1－ pn,W1-wn)∈ Sn－ 2？，以判断 Xn-1的值
xn-2,…,x 1将依次推导得出
2009-7-27
例 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)由 S3中的序偶 (6,6)给出。
1) ∵(6,6) S 2
∴x 3=1
2) ∵(6 -p3,6-w3)=(1,2)∈S 2且 (1,2)∈S 1
∴x 2=0
3) ∵(1,2) S 0
∴x 1=1
2009-7-27
算法 4.6 非形式的背包算法
procedure DKP(p,w,n,M)
S0 ←{(0,0)}
for i←1 to n -1 do
←{(P 1,W1)|(P1-pi,W1-wi)∈ Si-1 and W1≤M}
Si ←MERGE -PURGE(Si-1,)
repeat
(PX,WX)← S n-1的最末一个有效序偶
(PY,WY)←(P1 ＋ pn,W1+wn)，其中,W1是 Sn-1中使得 W＋ wn≤M的所有序偶中取最大值得 W
//沿 Sn-1,…,S 1回溯确定 xn,xn-1,…,x 1的取值 //
if PX＞ PY then xn←0 //PX 将是 Sn的最末序偶 //
else xn←1 //PY 将是 Sn的最末序偶 //
endif
回溯确定 xn-1,…,x 1
end DKP
iS1
iS1
2009-7-27
3,DKP的实现
1)序偶集 Si的存储结构使用两个一维数组 P和 W存放所有的序偶 (P1,W1),其中 P存放 P1值，
W存放 W1值
● 序偶集 S0,S1,…,S n-1顺序,连续 存放于 P和 W中；
● 用指针 F(i)表示 Si中第一个元素在数组
(P,W)中的下标位置,0? i? n;
● 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)
2009-7-27
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的存放位置上。
注：不需要存放 的 专用空间
iS1 iS1
iS1
iS1
2009-7-27
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 //S 0//
l←h←1 // S 0 的首端和末端； 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)+p i,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
iS1
iS1
iS1
2009-7-27
//按照支配规则考虑 (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
endif
//清除 Si-1中的序偶 //
while k≤h and P(k)≤P(next-1) do k←k+1 repeat
repeat
//将 Si-1中剩余的元素并入 Si //
while k≤h do
(P(next),W(next))←(P(k),W(k))
next←next+1; k←k+1
repeat
//对 Si+1置初值 //
l←h+1; h←next -1; F(i+1)←next
repeat
CALL PARTS //递推求取 Xn,Xn-1,…,x 1//
END DKNAP
2009-7-27
4,过程 DKNAP的分析
1) 空间复杂度记 Si中的序偶数为,|Si|
则有,|Si|? |Si-1|＋ | |
又,| |? |Si-1|
所以,|Si|?2 |Si-1|
最坏情况下有（由 Si-1生成 和 Si时没有序偶被支配）,
故,DKNAP所需的空间复杂度（ P,W数组）为,Ο(2n)
i1S
122||
1010
n
ni
i
ni
iS
i1S
i1S
2009-7-27
2) 时间复杂度由 Si-1生成 Si的时间为：,0?i? n-1
故,DKNAP计算所有的 Si所需的时间为：
注：
若每件物品的重量 wi和效益值 pi均为 整数,则 Si中每个序偶
(P,W)的 P值和 W值也是整数，且有,W?M
又，在任一 Si中的所有序偶具有互异 P值和 W值，故有且
|)S(| 1-i?
)2(||
10
1 n
ni
iS
ij jpP 0 ||
ij ji pS 0 ||1|| },||mi n {1|| 0 MwS ij ji
2009-7-27
在所有 wj和 pj均为 整数 的情况下,DKNAP的时间和空间复杂度将为：
}),||,2( m in {
1
nMpn
ni
i
n?
2009-7-27
5,序偶集合的一种启发式生成策略设 L是最优解的估计值，且有 fn(M)?L
设 PLEFT(i)=
若正在生成的序偶 (P,W)有 P＋ PLEFT(i)＜ L，则 (P,W)将不计入 Si中。
L的选择：
① 取 Si的最末序偶 (P,W)的 P作为 L,P?f n(M)
② 将某些剩余物品的 p值＋ P作为 L
nji jp
2009-7-27
例 4.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）表示
2009-7-27
启发式规则求解分析：将物品 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=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
11S
21S
31S
41S
51S
2009-7-27
第五章 基本检索与周游
1.检索与周游检索,以某种方法检查给定的数据对象，找出满足某些给定性质的结点的过程称为 检索周游,当检索过程必须检索到数据对象的每一个结点时，
则该检索过程称为 周游访问结点,当算法对一个结点的信息段进行处理时，称该结点 被访问 。
2009-7-27
2,二元树周游（遍历）
1）周游次序在二元树的周游中，以 D,L,R分别代表访问结点的信息段、访问左子树、访问右子树。则可能的顺序有：
★ LDR：中根次序周游（中根遍历）
★ LRD：后根次序周游（后根遍历）
★ DLR：先根次序周游（先根遍历）
★ RDL：逆中根次序周游
★ RLD：逆后根次序周游
★ DRL：逆先根次序周游
2009-7-27
2）二元树周游算法
⑴ 中根次序周游算法 5.1 中根次序周游的递归表示
procedure INORDER(T)
//T是一棵二元树。 T的每个结点有三个信息段,LCHILD,
DATA,RCHILD//
if T≠0 then
call INORDER(LCHILD(T))
call VISIT(T)
call INORDER(RCHILD(T))
endif
end INORDER
2009-7-27
⑵ 先根次序周游算法 5.2 先根次序周游的递归表示
procedure PREORDER(T)
//T是一棵二元树。 T的每个结点有三个信息段,LCHILD,
DATA,RCHILD//
if T≠0 then
call VISIT(T)
call PREORDER(LCHILD(T))
call PREORDER(RCHILD(T))
endif
end PREORDER
2009-7-27
⑵ 后根次序周游算法 5.2 后根次序周游的递归表示
procedure POSTORDER(T)
//T是一棵二元树。 T的每个结点有三个信息段,LCHILD,
DATA,RCHILD//
if T≠0 then
call POSTORDER(LCHILD(T))
call POSTORDER(RCHILD)
call VISIT(T)
endif
end PREORDER
2009-7-27
注：
一棵二元树可由中根遍历序列＋先根遍历序列、或中根遍历序列＋后根遍历序列 唯一 确定。但 不能 由先根遍历序列＋后根遍历序列唯一确定。
如已知一棵二元树的中根遍历次序是,DGBEAFHC
先根遍历次序是,ABDGECFH
则这棵二元树唯一确定如下,A
B
D E
G
C
F
H
2009-7-27
定理 5.1 当输入的树 T有 n?0 个结点时，设 t(n)和 s(n)分别表示这些周游算法中的任意一个算法所需要的最大时间和空间。如果访问 一个结点 所需要的时间和空间是 Θ(1)，则 t(n)=Θ(n),s(n)=Θ(n)。
证明：
时间,由于已知访问一个结点所需要的时间是 Θ(1)，故可用常数 c1限界。
设 T的左子树中的结点数是 n1，则 t(n)有：
t(n)=maxn1{t(n1)+t(n-n1-1)+c1} n?1
其中,t(0)?c 1。
归纳法证明 t(n)?c 2n+c1，其中 c2是一使得 c2?2c 1的常数。
1)当 n=0时，成立
2)假定当 n=0,1,?,m -1时均成立。则当 n=m时有，
设 T是一棵有 m个结点的树,T左子树结点数为 n1,则
t(n)＝ maxn1{t(n1)+t(n-n1-1)+c1}
max n1{c2n1+c1+c2(n-n1-1)+c1+c1}
＝ maxn1{c2n+3c1-c2}
c 2n+c1
同理，存在 c'2和 c'1有 t(n)?c' 2n+c'1。所以 t(n)=Θ(n)
空间,若 T的深度为 d，则所需空间为 Θ(d),d?n,所以 s(n)=Θ(n)。
2009-7-27
3,树的周游
1) 树的子树顺序无序 → 有序
2)树的周游
⑴ 树的先根次序周游
⑵ 树的中根次序周游
⑶ 树的后根次序周游
2009-7-27
4,图的检索和周游
4.1 宽度优先检索和周游
1) 宽度优先检索
① 从结点 v开始，给 v标上 已到达 （或 访问 ）标记 ——此时称结点 v还没有被 检测,而当算法访问了邻接于某结点的所有结点时，
称该结点被检测了。
② 访问邻接于 v且尚未被访问的所有结点 ——这些结点是新的未被检测的结点。将这些结点依次放置到一 未检测结点表 (队列
Q)中（末端插入） 。
③ 标记 v已被 检测 。
④ 若未检测结点表为空，则算法终止；否则
⑤ 从未检测结点表的表头取一结点作为下一个待检测结点，
重复上述过程。
2009-7-27
算法 5.6 宽度优先检索算法
procedure BFS(v)
//宽度优先检索 G，它从结点 v开始。所有已访问结点被标记为 VISITED(i)=1。 //
VISITED(v)←1;u←v //VISITED(n)是一个标示数组，初始值
VISITED(i)=0,1?i?n //
将 Q初始化为空 //Q是未检测结点的队列 //
loop
for 邻接于 u的所有结点 w do
if VISITED(w)=0 then //w未被检测 //
call ADDQ(w,Q) //ADDQ将 w加入到队列 Q的末端 //
VISITED(w)←1 //同时标示 w已被访问 //
endif
repeat
if Q 为空 then return endif
call DELETEQ(u,Q) //DELETEQ取出队列 Q的表头，并赋给变量 u//
repeat
end BFS
2009-7-27
定理 5.2 算法 BFS可以访问由 v可到达的所有结点证明：设 G=(V,E)是一个 (有向或无向 )图,v∈V 。
归纳法证明定理结论正确。
记 d(v,w)是由 v到达某一可到达结点 w(w∈V) 的最短路径长度。
⑴ 若 d(v,w)?1,则显然这样的所有 w都将被访问。
⑵ 假设对所有 d(v,w)?r 的结点都可被访问。则当 d(v,w)=r+1时有：
设 w是 V中 d(v,w)=r+1的一个结点设 u是从 v到 w的最短路径上紧挨着 w的 前一个 结点。则有
d(v,u)=r。
所以,u可通过 BFS被访问到。
假设 u≠v,且 r?1 。根据 BFS的处理规则,u将在被访问之前的某个时刻被放到未被检测结点队列 Q上，而在另一时刻 u将从队列 Q中移出。此时，所有邻接于 u且尚未被访问的结点将被访问。若结点 w在这之前未被访问，则此刻将被访问到。
由上，定理得证
2009-7-27
定理 5.3 设 t(n,e)和 s(n,e)是算法 BFS在任一具有 n个结点和 e条边的图 G上所花的最大时间和最大附加空间。
● 若 G由邻接表表示，则 t(n,e)=Θ(n+e)和 s(n,e)=Θ(n)。
● 若 G由邻接矩阵表示，则 t(n,e)=Θ(n2)和 s(n,e)=Θ(n)
证明：
1)空间分析根据算法的处理规则，结点 v不会放到队列 Q中。结点 w,w∈V 且 w≠v,
仅在 VISITED(w)=0时由 ADDQ(w,Q)加入队列，并置 VISITED(w)=1，所以每个结点（除 v)至多只有一次被放入队列 Q中。
至多有 n-1个这样的结点考虑，故总共至多做 n-1次结点加入队列的操作。需要的队列空间至多是 n-1。所以 s(n,e)=Ο(n)(其余变量所需的空间为 Ο(1))
当 G是一个具有 v与其余的 n-1个结点相连的图，则邻接于 v地全部 n-1个结点都将在,同一时刻,被放在队列上（ Q至少应有 Ω(n)的空间）。
同时,VISITED(n)本身需要 Θ(n) 的空间。
所以 s(n,e)=Θ(n)—— 这一结论与使用邻接表或邻接矩阵无关。
2009-7-27
2) 时间分析
● G采用邻接表表示判断邻接于 u的结点将在 d(u)时间内完成：若 G是无向图，则 d(u)是
u的度；若 G是有向图，则 d(u)是 u的出度。
> 所有结点的处理时间,Ο(Σ d(u))=Ο(e)。
注：嵌套循环中 对 G中的每一个结点 至多 考虑 一次 。
> VISITED数组的初始化时间,Ο(n)
> 算法总时间,Ο(n+e)。
● G采用邻接矩阵表示
> 判断邻接于 u的所有结点需要 的 时间,Θ(n)
> 所有结点的处理时间,Ο(n2)
> 算法总时间,Ο(n2)
● 如果 G是一个由 v可到达所有结点的图，则将检测到 V中的所有结点，
所以上两种情况所需的总时间至少应是 Ω(n+e)和 Ω(n2)。
所以,t(n,e)=Θ(n+e) 使用邻接表表示或,t(n,e)=Θ(n2) 使用邻接矩阵表示
2009-7-27
2) 宽度优先周游算法 5.7 宽度优先图的周游算法
procedure BFT(G,n)
//G的宽度优先周游 //
int VISITED(n)
for i←1 to n do VISITED(i)←0 repeat
for i←1 to n do // 反复调用 BFS//
if VISITED(i)=0 then call BFS(i) endif
repeat
end BFT
注：若 G是无向连通图或强连通有向图，则 一次 调用 BFS即可完成对 T的周游。否则，需要 多次 调用。
2009-7-27
图周游算法的应用
●判定图 G的 连通性,若调用 BFS的次数多于 1次，则 G为非连通的
●生成图 G的 连通分图,一次调用 BFS中可以访问到的所有结点及连接这些结点的边构成一个连通分图。
●无向图 自反传递闭包矩阵 A*
● 宽度优先生成树向前边,BFS中由 u达到未访问结点 w的边 (u,w)称为向前边。
记 T是 BFS中所处理的所有向前边集合。
宽度优先生成树,若 G是连通图，则 BFS终止时,T构成一棵生成树。
1
2 3
4 5 6 7
8 无向图 G
1
2 3
4 5 6 7
8 G的宽度优先生成树
2009-7-27
定理 5.4 修改算法 BFS，在第 1行和第 6行分别增加语句 T← Φ和
T←T ∪{(u,w)} 。修改后的算法称为 BFS*。若 v是无向图中任一结点，调用 BFS*，算法终止时,T中的边组成 G的一棵生成树。
procedure BFS*(v)
VISITED(v)←1;u←v
T← Φ
将 Q初始化为空
loop
for 邻接于 u的所有结点 w do
if VISITED(w)=0 then //w未被检测 //
T←T ∪{(u,w)}
call ADDQ(w,Q) //ADDQ将 w加入到队列 Q的末端 //
VISITED(w)←1 //同时标示 w已被访问 //
endif
repeat
if Q 为空 then return endif
call DELETEQ(u,Q) //DELETEQ取出队列 Q的表头，并赋给变量 u//
repeat
end BFS*
2009-7-27
证明：
若 G是 n个结点的连通图，则这 n个结点都要被访问。除起始点
v以外，其它 n-1个结点都将被放且仅将被放到队列 Q上一次，从而
T将正好包含 n-1条边，且这些边是各不相同的。即 T是关于 n个结点 n-1边的无向图。
同时，对于连通图 G,T将包含由起始结点 v到其它结点的路径，
所以 T是 连通 的。
则 T是 G的一棵 生成树 。
注：对于 n个结点且正好有 n-1条边的连通图是一棵 树 。
2009-7-27
4.2 深度优先检索和周游
1) 深度优先检索从结点 v开始，首先给 v标上 已到达 （或 访问 ）标记，同时中止对 v的检测，
并开始对邻接于 v且尚未被访问的结点 u检测。在这样的 u均被检测后，再恢复对 v的检测。当所有可到达的结点全部被检测完毕后，算法终止。
算法 5.8 图的深度优先检索
procedure DFS(v)
//已知一个 n结点的无向（或有向）图 G＝ (V,E)以及初值已置为零的数组 VISITED(1:n)。
这个算法访问由 v可以到达的所有结点。 //
VISITED(v)←1
for 邻接于 v的每个结点 w do
if VISITED(w)＝ 0 then call DFS(w) endif
repeat
end DFS
2009-7-27
性质：
① DFS可以访问由 v可到达的所有结点
② 如果 t(n,e)和 s(n,e)表示 DFS对一 n结点 e条边的图所花的最大时间和最大附加空间，则
● s(n,e)=Θ(n)
● t(n,e)= Θ(n+e) G采用 邻接表 表示，或
● t(n,e)= Θ(n2) G采用 邻接矩阵 表示
2) 深度优先周游算法 DFT
反复调用 DFS,直到所有结点均被检测到。
应用：
① 判定图 G的连通性
② 连通分图
③ 无向图自反传递闭包矩阵
④ 深度优先生成树
2009-7-27
深度优先生成树算法
procedure DFS*(v)
T← Φ
VISITED(v)←1
for 邻接于 v的每个结点 w do
if VISITED(w)＝ 0 then
T←T ∪{(u,w)}
call DFS(w)
endif
repeat
end DFS*
2009-7-27
1
2 3
4 5 6 7
8 无向图 G
1
2 3
4 5 6 7
8 G的宽度优先生成树
1
2 3
4 5 6 7
8 G的深度优先生成树
2009-7-27
4.3 BFS,DFS,D_Search算法比较
BFS：使用 队列 保存未被检测的结点。结点按照 宽度优先 的次序被访问和进、出队列。
DFS：使用 栈 保存未被检测的结点，结点按照 深度优先 的次序被访问并依次被压入栈中，并以相反的次序出栈进行新的检测。
D_Search：使用 栈 保存未被检测的结点，结点按照 宽度优先的次序被访问并被依次压入栈中，然后以相反的次序出栈进行新的检测。新的检测结点是最新被访问但未被检测的结点。
BFS检测序列,1 2 3 4 5 6 7 8
DFS检测序列,1 2 4 8 5 6 3 7
D_Search检测序列,1 3 7 8 5 4 6 2
1
2 3
4 5 6 7
8 无向图 G
