2009-7-27
第三章 贪心方法
2009-7-27
3.1 一般方法
1,问题的一般特征问题有 n个输入，问题的解是由这 n个输入的某个 子集 组成，这个子集必须满足某些事先给定的条件。
约束条件,子集必须满足的条件；
可行解,满足约束条件的子集；可行解可能不唯一；
目标函数,用来衡量可行解优劣的标准，一般以函数的形式给出；
最优解,能够使目标函数取极值（极大或极小）的可行解。
分类,根据描述问题约束条件和目标函数的 数学模型 的特性和问题的 求解方法 的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。
—— 最优化问题求解贪心方法,一种改进的 分级 的处理方法，可对满足上述特征的某些问题方便地求解。
2009-7-27
例 [找零钱 ] 一个小孩买了价值少于 1美元的糖，并将 1
美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为 25美分,10美分,5美分及 1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪心算法如下：每一次选择应使零钱数尽量增大。为确保解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。
假设需要找给小孩 67美分，首先入选的是两枚
25美分的硬币，第三枚入选的不能是 25美分的硬币，
否则将不可行（零钱总数超过 67美分），第三枚应选择 10美分的硬币，然后是 5美分的，最后加入两个 1美分的硬币。
贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）
2009-7-27
2,贪心方法的一般策略问题的一般特征：问题的解是由 n个输入的、满足某些事先给定的条件的子集组成。
1）一般方法根据题意，选取一种 度量标准 。然后按照这种度量标准对 n
个输入 排序,并按序一次输入一个量。
如果这个输入和当前已构成在这种量度意义下的 部分最优解 加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的 新的部分解 。
2）贪心方法这种能够得到某种量度意义下的最优解的 分级处理 方法称为贪心方法注：
贪心解 最优解
直接将目标函数作为 量度标准 也不一定能够得到问题的最优解
3）使用贪心策略求解的关键选取能够得到问题最优解的量度标准。
？＝
2009-7-27
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
end GREEDY
2009-7-27
3.2 背包问题
1.问题的描述已知 n种物品具有重量 (w1,w2,…,w n)和效益值 (p1,p2,…,p n),
及一个可容纳 M重量的背包；设当物品 i全部或一部分 xi放入背包将得到 pi xi的效益，这里,0≤ xi ≤1,p i >0。
问题,采用怎样的装包方法才能使装入背包的物品的 总效益最大？
分析,
① 装入背包的总重量 不能超过 M
② 如果所有物品的 总重量 不超过 M，即 ≤ M，则把 所有 的物品都装入背包中将获得最大可能的效益值
③ 如果物品的总重量 超过了 M，则将有物品不能（全部）
装 入背包中。由于 0≤x i≤1,所以可以把物品的一部分装入背包，所以最终背包中可刚好装入重量为 M的若干物品（整个或一部分）
目标,使装入背包的物品的 总效益 达到 最大 。
ni iixw1
2009-7-27
问题的形式描述目标函数,
约束条件,
可 行 解,满足上述约束条件的 任一集合 (x1,x2,…,x n) 都是问题的一个可行解 —— 可行解可能为多个。
(x1,x2,…,x n)称为问题的一个 解向量最 优 解,能够使目标函数取 最大值 的可行解是问题的最优解 —— 最优解也可能为多个。
ni
iixp
1
niwpx
Mxw
iii
ni
ii
1,0,0,10
1
2009-7-27
例 3.1 背包问题的实例设,n=3,M=20，
(p1,p2,p3) = (25,24,15),(w1,w2,w3) =
(18,15,10)。
可能的可行解如下：
(x1,x2,x3)
① (1/2,1/3,1/4) 16.5 24.25 //没有放满背包 //
② (1,2/15,0 ) 20 28.2
③ (0,2/3,1) 20 31
④ (0,1,1/2) 20 31.5
iixp? iixw
2009-7-27
2,贪心策略求解度量标准的选择：三种不同的选择
1）以 目标函数 作为度量标准即，每装入一件物品，就使背包背包获得 最大 可能的效益增量。
该度量标准下的 处理规则：
● 按效益值的非增次序将物品一件件地放入到背包；
● 如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量标准，
则在 剩下 的物品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。
如：若 Δ M=2,背包外还剩两件物品 i,j，且有 (pi＝ 4,wi＝ 4)
和 (pj＝ 3,wj＝ 2)，则下一步应选择 j而非 i放入背包：
pi/2 = 2 ＜ pj＝ 3
2009-7-27
实例分析（例 3.1)
∵ p1＞ p2＞ p3
∴ 首先将 物品 1放入背包，此时 x1＝ 1，背包获得 p1＝ 25的效益增量，
同时背包容量减少 w1＝ 18个单位，剩余空间 Δ M=2。
其次考虑 物品 2和 3。就 Δ M=2而言有，只能选择物品 2或 3的 一部分 装入背包。
物品 2,若 x2＝ 2/15,则 p2 x2＝ 16/5＝ 3.1
物品 3,若 x3＝ 2/10,则 p3 x3＝ 3
为使背包的效益有最大的增量，应选择 物品 2的 2/15装包，即
x2＝ 2/15
最后，背包装满,Δ M=0，故 物品 3将不能装入背包,x3＝ 0 。
背包最终可以获得 效益值 ＝ x1 p1 ＋ x2 p2＋ x3 p3
＝ 28.2 (次优解,非问题的最优解 )
2009-7-27
2）以 容量 作为度量标准以 目标函数 作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而不能装入,更多” 的物品。
改进：让背包 容量 尽可能慢地消耗，从而可以尽量装入“更多”的物品。
即，新的标准是：以 容量 作为度量标准该度量标准下的处理规则：
● 按物品 重量的非降次序 将物品装入到背包；
● 如果正在考虑的物品放不进去，则只取其一部分装满背包；
2009-7-27
实例分析（例 3.1)
∵ w3＜ w2 ＜ w1
∴ 首先将 物品 3放入背包，此时 x3＝ 1，背包容量减少 w3
＝ 10个单位，还剩余空间 Δ M=10。同时,背包获得 p3＝
15的效益增量 。
其次考虑 物品 1和 2。就 Δ M=10而言有，也只能选择物品 1或 2的 一部分 装入背包。 为使背包的按照“统一”的规则，下一步将放入 物品 2的 10/15装包，即
x2＝ 10/15＝ 2/3
最后，背包装满 Δ M=0，故 物品 1将不能装入背包,x1
＝ 0 。
背包最终可以获得 效益值 ＝ x1 p1 ＋ x2 p2＋ x3 p3
＝ 31 (次优解,非问题的最优解
2009-7-27
3）最优的度量标准影响背包效益值得因素：
背包的 容量 M
放入背包中的物品的重量及其可能带来的效益值可能的策略 是：在背包效益值的增长速率和背包容量消耗速率之间取得 平衡,即每次装入的物品应使它所占用的每一 单位容量 能获得当前最大的单位效益。
在这种策略下的 量度 是：已装入的物品的累计效益值与所用容量之比。
故，新的 量度标准 是：每次装入要使累计效益值与所用容量的比值有最多的增加（首次装入）和最小的减小（其后的装入）。
此时，将按照物品的单位效益值,pi/wi 比值（密度）的非增次序考虑。
2009-7-27
实例分析（例 3.1)
∵ p1/w1＜ p3/w3 ＜ p2/w2
∴ 首先将 物品 2放入背包，此时 x2＝ 1，背包容量减少 w2
＝ 15个单位，还剩余空间 Δ M=5。同时,背包获得 p2＝
24的效益增量 。
其次考虑 物品 1和 3。此时，应选择物品 3,且就 Δ M=5而言有，也只能放入物品 3的 一部分 到背包中 。 即
x3＝ 5/10＝ 1/2
最后，背包装满 Δ M=0，故 物品 1将不能装入背包,x1
＝ 0 。
背包最终可以获得 效益值 ＝ x1 p1 ＋ x2 p2＋ x3 p3
＝ 31.5 (最优解 )
2009-7-27
3,背包问题的贪心求解算法算法 3.2 背包问题的贪心算法
procedure GREEDY－ KNAPSACK(P,W,M,X,n)
//p(1:n)和 w(1:n)分别含有按 P(i)/W(i)≥P(i＋ 1)/W(i＋ 1)排序的 n
件物品的效益值和重量。 M是背包的容量大小，而
x(1:n)是解向量 //
real P(1:n),W(1:n),X(1:n),M,cu;
integer I,n
X←0 // 将解向量初始化为空 //
cu←M //cu 是背包的剩余容量 //
for i←1 to n do
if W(i) > cu then exit endif
X(i) ←1
cu ←cu -W(i)
repeat
if i≤n then X(i) ←cu/W(i) endif
end GREEDY-KNAPSACK
2009-7-27
4,最优解的证明即证明：由第三种策略所得到的贪心解是问题的 最优解 。
最优解 的含义：在满足约束条件的情况下，可使目标函数取极
（大或小）值的可行解。贪心解是可行解，故只需证明：贪心解可使目标函数取得极值。
证明的 基本思想,将此贪心解与（假设中的）任一最优解 相比较 。
● 如果这两个解相同，则显然贪心解就是最优解。否则，
● 这两个解不同，就去找开始 不同 的第一个分量位置 i，然后设法用贪心解的这个 xi去 替换 最优解的那个 xi,并证明最优解在分量代换前后总的效益值没有任何变化。
可反复进行代换，直到新产生的最优解与贪心解完全一样。这一代换过程中，最优解的 效益值没有任何损失,从而证明贪心解的效益值与代换前后最优解的效益值相同。即，贪心解如同最优解一样可取得目标函数的最大 /最小值。
从而得证：该 贪心解 也即问题的 最优解 。
2009-7-27
定理 3.1 如果 p1/w1≥ p2/w2≥…≥ p n/wn,则算法
GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。
证明,
设 X=(x1,x2,…,x n)是 GREEDY-KNAPSACK所生成的 贪心解 。
① 如果所有的 xi都等于 1,则显然 X就是问题的 最优解 。否则，
② 设 j是使 xi≠1的最小下标。由算法可知，
xi=1 1≤i＜ j,
0≤xj ＜ 1
xi=0 j＜ i≤n
若 X不是问题的最优解，则必定存在一个可行解 Y=(y1,
y2,…,y n),使得：
且应有：
iiii xpyp
Myp ii
2009-7-27
设 k是使得 yk≠ xk的最小下标，则有 yk＜ xk:
a) 若 k<j，则 xk=1。因为 yk≠ xk,从而有 yk ＜ xk
b) 若 k=j，由于,且对 1≤i＜ j，有 yi=xi=1,而对 j＜ i≤n,
有 xi＝ 0；故此时若 yk＞ xk，则将有,与 Y是可行解相矛盾。
而 yk≠ xk,所以 yk ＜ xk
c) 若 k＞ j，则,不能成立在 Y中作以下调整：将 yk增加到 xk，因为 yk < xk,为保持解的可行性，必须从 ( yk+1,…,y n)中减去同样多的量。设调整后的解为
Z=(z1,z2,…,z n)，其中 zi＝ xi,1≤i≤k，且有：
则对于 Z有：
Mxw ii
Myw ii
Myw ii
nik kkkiii yzwzyw )()(
ni iiinik iikkkkkiini ii wpwzywpwyzypzp 11 /)(/)(
ni kkinik iikkkii wpwzywyzyp1 /])()[(
ni ii yp1
2009-7-27
由以上分析得，
若,则 Y将不是最优解；
若,则或者 Z=X，则 X就是最优解；
或者 Z≠X,则重复以上替代过程，或者证明 Y不是最优解，或者把 Y转换成 X，从而证明 X是最优解
iiii ypzp
iiii ypzp
2009-7-27
3.3 带有限期的作业排序
1,问题描述假定在一台机器上处理 n个作业，每个作业均可在单位时间内完成；同时每个作业 i都有一个 截至期限 di>0,当且仅当作业 i在其截至期限以前被完成时，则获得 pi>0的效益。
问题,求这 n个作业的一个子集 J，其中的所有作业都可在其截至期限内完成。 —— J是问题的一个可行解。
可行解 J中的 所有作业的效益之和是,具有 最大效益值的 可行解是该问题的最优解。
如果所有的作业都能在其期限之内完成则显然可以获得当前最大效益值；否则，将有作业无法完成 —— 决策应该执行哪些作业，
以获得最大可能的效益值。
目标函数：
约束条件,所有的作业都应在其期限之前完成
Ji ip
Ji ip
2009-7-27
例 3.2 n=4,(p1,p2,p3,p4)＝ (100,10,15,20)和 (d1,d2，
d3,d4)＝ (2,1,2,1)。可行解如下表所示：
问题的最优解是 ⑦。所允许的处理次序是：先处理作业 4再处理作业 1。
可行解 处理顺序 效益值
① （ 1） 1 100
② （ 2） 2 10
③ （ 3） 3 15
④ （ 4） 4 20
⑤ （ 1,2） 2,1 110
⑥ （ 1,3） 1,3或 3,1 115
⑦ （ 1,4） 4,1 120
⑧ （ 2,3） 2,3 25
⑨ （ 3,4） 4,3 35
2009-7-27
1,带有限期的作业排序算法
1) 度量标准的选择以目标函数 作为量度。
量度标准：下一个要计入的作业将是使得在满足所产生的 J是一个可行解的限制条件下让得到最大增加的作业。
处理规则：按 pi的非增次序来考虑这些作业。
Ji i
p
Ji i
p
2009-7-27
例：例 3.2求解
① 首先令 J=Φ,
② 作业 1具有当前的最大效益值，且 {1}是可行解，所以作业 1计入 J；
③ 在剩下的作业中，作业 4具有最大效益值，
且 {1,4}也是可行解，故作业 4计入 J，即 J={1,4}；
④ 考虑 {1,3,4}和 {1,2,4}均不能构成新的可行解，作业 3和 2将被舍弃。
故最后的 J={1,4}，最终效益值＝ 120（问题的最优解 ）
0
Ji i
p
2009-7-27
2)作业排序算法的概略描述算法 3.3
procedure GREEDY-JOB(D,J,n)
//作业按 p1≥p2≥…≥p n的次序输入，它们的期限值 D(i)≥1,
1≤i≤n,n≥1。 J是在它们的截止期限完成的作业的集合 //
J←{1}
for i←2 to n do
if J∪ {i}的所有作业能在它们的截止期限前完成
then J←J ∪ {i}
endif
repeat
end GREEDY-JOB
2009-7-27
2,最优解证明定理 3.2 算法 3.3对于作业排序问题总是得到问题的一个 最优解证明,
设 J是由算法所得的 贪心解 作业集合,I是一个 最优解的作业集合。
① 若 I=J，则 J就是最优解；否则
②,即至少存在两个作业 a和 b，使得 a∈ J
且,b∈ I且 。
并设 a是这样的一个具有 最高效益值 的作业，且由算法的处理规则可得：对于在 I中而不在 J中的作业所有 b，
有：
pa≥pb
Ia? Jb?
IJJI 且
2009-7-27
设 SJ和 SI分别是 J和 I的可行的 调度表 。因为 J和 I都是可行解，故这样的调度表一定存在；
设 i是既属于 J又属于 I的一个作业，并 i设在调度表 SJ中的调度时刻是 [t,t+1],而在 SI中的调度时刻是 [t’,t’+1]。
在 SJ和 SI中作如下调整：
● 若 t＜ t’,则将 SJ中在 [t’,t’+1]时刻调度的那个作业
（如果有的话）与 i相交换。如果 J中在 [t’,t’+1]时刻没有作业调度，则直接将 i移到 [t’,t’+1]调度。 —— 新的调度表也是可行的。反之，
● 若 t’＜ t，则在 SI中作类似的调换，即将 SI中在 [t，
t+1]时刻调度的那个作业（如果有的话）与 i相交换。如果 I
中在 [t,t+1]时刻没有作业调度，则直接将 i移到 [t,t+1]调度。 —— 同样，新的调度表也是可行的。
对 J和 I中共有的所有作业作上述的调整。设调整后得到的调度表为 S’J和 S’I，则在 S’J和 S’I中 J和 I中 共有 的所有作业将在相同的时间被调度。
2009-7-27
设 a在 S’J中的调度时刻是 [ta,ta+1],b是 S’I中该时刻调度的作业。根据以上的讨论有,pa≥pb。
在 S’I中，去掉作业 b，而去调度作业 a，得到的是作业集合 I’=I-{b} ∪ {a}的 一个可行的调度表，且 I’的效益值不小于 I的效益值。而 I’中比 I少了一个与 J不同的作业。
重复上述的转换，可使 I在 不减 效益值的情况下转换成 J。从而 J至少有和 I一样的效益值。所以 J也是最优解。
证毕。
2009-7-27
3,如何判断 J的可行性方法一,检验 J中作业所有可能的排列，对于任一种次序排列的作业排列，判断这些作业是否能够在其期限前完成 —
— 若 J
中有 k个作业，则将要检查 k!个序列方法二,检查 J中作业的一个 特定序列 就可判断 J的可行性：
对于所给出的一个排列 σ ＝ i1i2?i k,由于作业 ij完成的最早时间是 j，因此只要判断出 σ 排列中的每个作业
dij≥j,就可得知 σ 是一个允许的调度序列，从而 J
是一个可行解。反之，如果 σ 排列中有一个 dij＜ j,则 σ 将
2009-7-27
定理 3.3 设 J是 k个作业的集合,σ＝ i1i2…i k是 J中作业的一种排列，它使得 di1≤di2≤…≤d ik。 J是一个可行解,当且仅当 J中的作业可以按照 σ的次序而又不违反任何一个期限的情况来处理。
证明：
① 如果 J中的作业可以按照 σ的次序而又不违反任何一个期限的情况来处理，则 J是一个可行解
② 若 J是一个可行解，则必存在序列 σ’＝ r1r2…r k，使得 drj≥ j,
1≤j≤k。
★ 若 σ＝ σ’，则 σ即是可行解。否则，
★ σ≠σ’，令 a是使得 ra≠ia的最小下标，并设 rb=ia。则有：
b＞ a 且 dra≥drb (为什么?)
在 σ’中调换 ra与 rb，所得的新序列 σ’’＝ s1s2…s k的处理次序不违反任何一个期限。
重复上述过程，则可将 σ’转换成 σ且不违反任何一个期限。故 σ
是一个 可行 的调度序列故定理得证 。
2009-7-27
5,带有限期的作业排序算法的实现对当前正在考虑的作业 j，按限期大小采用一种,插入排序” 的方式，尝试将其“插入”到一个按限期从小到大顺序构造的作业调度序列中，以此判断是否能够合并到当前部分解 J中。如果可以，则插入到序列中，形成新的可行解序列。否则，舍弃该作业。
具体如下：
假设 n个作业已经按照效益值从大到小的次序，即
p1≥p2≥…≥p n的顺序排列好，每个作业可以在 单位时间 内完成，并具有相应的时间期限；且至少有一个单位时间可以执行作业首先，将作业 1存入部分解 J中，此时 J是可行的；
然后，依次考虑作业 2到 n。假设已经处理了 i-1个作业，
其中有 k个作业计入了部分解 J中,J(1),J(2),…,J(k),且有
D(J(1))≤D(J(2))≤…≤D(J(k))
2009-7-27
对当前正在考虑的作业 i,将 D(i)依次和 D(J(k)),
D(J(k-1)),?,D(J(1))相比较，直到找到位置 q：使得
★ D(i)＜ D(J(l)),q＜ l≤k,且
★ D(J(q))≤ D(i)
此时，若 D(J(l))＞ l,q＜ l≤k,即说明 q位置之后的所有作业均可 推迟 一个单位时间执行，而又不违反各自的执行期限。
最后，将 q位置之后的所有作业后移一位，将作业 i插入 到位置 q＋ 1处，从而得到一个包含 k+1个作业的新的可行解。
若找不到这样的 q，作业 i将被舍弃。
对 i之后的其它作业重复上述过程直到 n个作业处理完毕。最后 J中所包含的作业集合是此时算法的贪心解，也是问题的最优解。
2009-7-27
σ＝ i1 i2 … ia … … ic … ik
σ’＝ r1 r2 … ra … rb … r k
★ a＜ b
★ dra≥drb
2009-7-27
算法 3.4 带有限期和效益的单位时间的作业排序贪心算法
procedure JS(D,J,n,k)
//D(1),…,D(n) 是期限值。 n≥1。作业已按 p1≥p2≥…≥p n的顺序排序。 J(i)是最优解中的第 i个作业,1≤i≤k。终止时,D(J(i))≤D(J(i＋ 1)),1≤i＜ k//
integer D(0:n),J(0:n),i,k,n,r
D(0)←J(0)←0 // 初始化 //
k←1;J(1)←1 // 计入作业 1//
for i←2 to n do //按 p的非增次序考虑作业。找 i的位置并检查插入的可行性 //
r←k
while D(J(r))＞ D(i) and D(J(r)) ≠r do
r←r -1
repeat
If D(J(r))≤D(i) and D(i)＞ r then //把 i插入到 J中 //
for i←k to r+1 by -1 do
J(i+1) ←J(i) // 将插入点的作业后移一位 //
repeat
J(r+1) ←I;k←k+1
endif
repeat
end JS
2009-7-27
计算时间分析
for i←2 to n do? 将循环 n-1次－－－－－－－－－－－－－－－－－－
①
r←k
while D(J(r))＞ D(i) and D(J(r)) ≠r do? 至多循环 k次，
k是当前计入 J中的作业数 －－－
②
r←r -1
repeat
If D(J(r))≤D(i) and D(i)＞ r then
for i←k to r+1 by -1 do? 循环 k-r次,r是插入点的位置 －－－－
－ ③
J(i+1) ←J(i)
repeat
J(r+1) ←I;k←k+1
endif
repeat
设 s是最终计入 J中的作业数，则算法 JS所需要的总时间是 O(sn)。
s≤n,故最坏情况,TJS = О(n2)，特例情况,pi=di=n-i+1,1≤i≤n
2009-7-27
6,一种“更快”的作业排序问题使用不相交集合的 UNION和 FIND算法
（见 1.4.3节），可以将 JS的计算时间降低到数量级接近 О(n)。
（略）
2009-7-27
3.4 最优归并模式
1,问题的描述
1）两个文件的归并问题两个已知文件的一次归并所需的计算时间＝ O(两个文件的元素总数 )
例：
n个记录的文件
＋ (n+m) 个记录的文件
m个记录的文件 О(n+m)
2）多个文件的归并已知 n个文件，将之归并成一个单一的文件例：假定文件 X1,X2,X3,X4，采用两两归并的方式，可能的归并模式有：
① X1+X2=Y1+X3= Y2+X4= Y3
② X1+X2 = Y1
+ → Y3
X3+X4=Y2
2009-7-27
二路归并模式：每次仅作两个文件的归并；当有多个文件时，采用两两归并的模式，最终得到一个完整的记录文件。
二元归并树：二路归并模式的归并过程可以用一个二元树的形式描述，
称之为二元归并树。
如归并树的构造外结点,n个原始文件内结点：一次归并后得到的文件在两路归并模式下，每个内结点刚好有两个儿子，代表把它的两个儿子表示的文件归并成其本身所代表的文件
60
50
30 20
10
X1
Z1
X
X3
X2
2009-7-27
不同的归并顺序带来的计算时间是不同的。
例 3.5 已知 X1,X2,X3是分别为 30,20,10个记录长度的已分类文件。将这 3个文件归并成长度为 60的文件。可能的归并过程和相应的记录移动次数如下：
问题：采用怎样的归并顺序才能使归并过程中元素的移动次数最小（或执行的速度最快）
X
X3
X2
X1
移动 50次移动 60次
X
X1
X2
X3
移动 30次移动 60次总移动次数,110次总移动次数,90次
2009-7-27
2,贪心求解
1) 度量标准的选择
★ 任意两个文件的归并所需的 元素移动次数 与这两个文件的 长度之和 成 正比；
★ 度量标准,每次选择需要移动次数最少的两个集合进行归并；
★ 处理规则,每次选择长度最小的两个文件进行归并。
95
35
5
20 30
60
3015
10
F4 F3
Z1
Z2
Z4
Z3
F1 F5 F2
(F1,F2,F3,F4,F5) = (20,30,10,5,30)
2009-7-27
2) 目标函数目标,元素移动的次数最少实例：为得到归并树根结点表示的归并文件，外部结点中每个文件记录需要移动的次数＝该外部结点到根的距离，即根到该外部结点路径的长度。如，
F4,
则 F4中所有记录在整个归并过程中移动的总量＝ |F4|*3
带权外部路径长度,记 di是由根到代表文件 Fi的外部结点的距离,qi是 Fi的长度，则这棵树的代表的归并过程的元素移动总量是：
最优的二路归并模式,与一棵具有 最小外部带权路径长度的二元树相对应。
F4 Z1 Z2 Z4
ni iidq1
2009-7-27
算法 3.6 生成二元归并树的算法
procedure TREE(L,n)
//L是 n个单结点的二元树表 //
for i←1 to n -1 do
call GETNODE(T) //构造一颗新树 T//
LCHILD(T) ←LEAST(L) //从表 L中选当前根 WEIGHT最小的树，
并从中删除 //
RCHILD(T) ←LEAST(L)
WEIGHT(T)
←WEIGHT(LCHILD(T))+WEIGHT(RCHILD(T))
call INSERT(L,T) //将归并的树 T加入到表 L中 //
repeat
return (LEAST(L)) //此时,L中的树即为归并的结果 //
end TREE
2009-7-27
例 3.6 已知六个初始文件，长度分别为,2,3,5,7,9,13。
采用算法 TREE，各阶段的工作状态如图所示：
L迭代
2 3 5 7 9 130
2 3
5 7 9 131 5
2 3
5 7 9 132 5
10
2009-7-27
2 3
5 7 9 133 5
10 16
2 3
5 7 9
13
4
5
10 16
23
2 3
5
7 9 13
5
5
10
16 23
39
2009-7-27
时间分析
1) 循环体,n-1次
2) L以有序序列表示
LEAST(L),О(1)
INSERT(L,T),О(n)
总时间,О(n2)
3) L以 min-堆表示
LEAST(L),О(logn)
INSERT(L,T),О(logn)
总时间,О(nlogn)
2009-7-27
3,最优解的证明定理 3.4 若 L最初包含 n≥1个单结点的树，这些树有 WEIGHT
值为 (q1,q2,…,q n)，则算法 TREE对于具有这些长度的 n个文件生成一棵最优的二元归并树。
证明,归纳法 证明
① 当 n=1时，返回一棵没有内部结点的树。定理得证。
② 假定算法对所有的 (q1,q2,…,q m),1≤m＜ n,生成一棵最优二元归并树。
③ 对于 n,假定 q1≤q2≤…≤q n,则 q1和 q2将是在 for循环的第一次迭代中首先选出的具有最小 WEIGHT值的两棵树（的 WEIGHT
值）；如图所示,T是由这样的两棵树构成的子树：
q1 q2
q1+q2T
2009-7-27
■ 设 T’是一棵对于 (q1,q2,…,q n)的最优二元归并树。
■ 设 P是 T’中距离根 最远 的一个 内部结点 。
若 P的两棵子树不是 q1和 q2，则用 q1和 q2代换 P当前的子树而不会增加 T’的带权外部路径长度。
故,T应是最优归并树中的子树。
则在 T’中用一个权值为 q1＋ q2的外部结点代换 T，得到的是一棵关于 (q1＋ q2,…,q n)最优归并树 T”。
而由归纳假设，在用权值为 q1＋ q2的外部结点代换了
T之后，过程 TREE将针对 (q1＋ q2,…,q n)得到一棵最优归并树。将 T带入该树，根据以上讨论，将得到关于
(q1,q2,…,q n)的最优归并树。
故,TREE生成一棵关于 (q1,q2,…,q n)的 最优归并树 。
2009-7-27
5,k路归并模式
每次 同时 归并 k个文件。
k元归并树：可能需要增加,虚” 结点，以补充不足的外部结点。
★ 如果一棵树的所有内部结点的度都为 k，则外部结点数 n满足 n mod (k-1) = 1
★ 对于满足 n mod (k－ 1) =1的整数 n，存在一棵具有 n个外部结点的 k元树 T，且 T中所有结点的度为 k。
至多需要增加 k-2个外部结点。
k路最优归并模式得贪心规则：每一步选取 k棵具有最小长度的子树归并。
2009-7-27
3.5 最小生成树
1,问题的描述生成树,设 G=(V,E)是一个无向连通图。如果 G的生成子图 T=(V,E')是一棵树，则称 T是 G的一棵生成树 (spanning tree)．
最小生成树,
2,贪心策略度量标准：选择能使迄今为止所计入的边的 成本和 有最小增加 的那条边。
● Prim算法
● Kruskal算法
2009-7-27
3,Prim算法策略：使得迄今所选择的边的集合 A构成一棵树；对将要计入到 A中的下一条边 (u,v)，应是 E中一条当前不在 A中且使得
A∪{(u,v)} 也是一棵树的最小成本边。
1
4
6
2
5
3
10
30
20
45
25 55
40
50
15
35
1 2
1
6
2
1
6
2 3
1
6
2 3
4
边
(1,2)
(2,6)
(3,6)
(6,4)
成本
10
25
15
20
2009-7-27
1
4
6
2
5
3
10
20
25
15
35边
(3,5)
成本
35
V(TP) = {1,2,3,4,5,6}
E(TP) = { (1,2),(2,6),(3,5),(4,6),(3,6) }
2009-7-27
算法 3.7 Prim最小生成树算法
procedure PRIM(E,COST,n,T,mincost)
//E是 G的边集。 COST(n,n)是 n结点图 G的成本邻接矩阵，矩阵元素
COST(i,j)是一个正实数，如果不存在边 (i,j)，则为＋ ∞。计算一棵最小生成树并把它作为一个集合存放到数组 T(1:n-1,2)中 (T(i,1),T(i,2))是最小成本生成树的一条边。最小成本生成树的总成本最后赋给 mincost//
real COST(n,n),mincost
integer NEAR(n),n,i,k,l,T(1:n-1,2)
(k,l)← 具有最小成本的边
mincost←COST(k,l)
(T(1,1),T(1,2)) ←(k,l)
for i←1 to n do // 将 NEAR置初值 //
if COST(i,l) ＜ COST(i,k) then NEAR(i)←l
else NEAR(i) ←k
endif
repeat
2009-7-27
NEAR(k)←NEAR(l)←0
for i←2 to n -1 do //找 T的其余 n-2条边 //
设 j是 NEAR(j)≠0 且 COST(j,NEAR(j))最小的下标
(T(i,1),T(i,2))←(j,NEAR(j))
mincost←mincost+COST(j,NEAR(j))
NEAR(j)←0
for k←1 to n do // 修改 NEAR//
if NEAR(k)≠0 and COST(k,NEAR(k))＞ COST(k,j)
then NEAR(k)←j
endif
repeat
repeat
if mincost＞ ∞ then print(‘no spanning tree’) endif
end PRIM
2009-7-27
计算复杂性：
第 3行花费 Θ (e)(e=|E|)时间，第 4行花费 Θ (1)时间；
第 6－ 9行的循环花费 Θ (n)时间；第 12行和第 16－ 20
行的循环要求 Θ (n)时间，因此第 11－ 21行循环要花费 Θ (n)时间。
所以 PRIM算法具有 的时间复杂度
)( 2n?
2009-7-27
最小生成树中包含了与每个结点 v相关的一条最小成本边证明略
方法：从一棵包含任何一个随意指定的结点而没有边的树开始这一算法，
然后再逐条增加边。
2009-7-27
4,Kruskal算法
（连通）图的边按成本的非降次序排列，下一条计入生成树 T
中的边是还没有计入的边中具有最小成本、且和 T中现有的边不会构成环路的边。
1
4
6
2
5
3
10
30
20
45
25 55
40
50
15
35
1 2
1
6
2
1
6
2 3
1
6
2 3
4
边
(1,2)
(3,6)
(4,6)
(2,6)
成本
10
15
20
25
1
6
2
3 4 5
63 4 5
3 4 5
4
5
5
2009-7-27
1
4
6
2
5
3
10
20
25
15
35边
(1,4)
(3,5)
成本
30 舍弃
35
V(TK) = {1,2,3,4,5,6}
E(TK) = { (1,2),(2,6),(3,5),(4,6),(3,6) }
2009-7-27
如何判断加入的边不构成环
把 T的同一连通分图中所有结点放到一个集合中。
T中的两个结点是连通的，当且仅当它们在同一个集合中。
如：考虑边 (2,6)时，这些集合是 {1,2},{3,4,6}和 {5}。
结点 2和 6在不同的集合中，因此这些集合可以合并为 {1,2,3,4,6}和 {5}。下一条边是 (1,4),1和 4在同一个集合中，因此舍弃。
2009-7-27
算法 3.9 Kruskal算法
procedure KRUSKAL(E,COST,N,T,mincost)
//G有 n个结点,E是 G的边集。 COST(u,v)是边 (u,v)的成本。 T是最小成本生成树的边集,mincost是它的成本 //
real mincost,COST(1:n,1:n); integer PARENT(1:n),T(1:n-1,2),n
以边成本为元素构造一个 min堆
PARENT← － 1//每个结点都在不同的集合中 //
i←mincost←0
while i＜ n-1 and 堆非空 do
从堆中删去最小成本边 (u,v)并重新构造堆
j←FIND(u); k←FIND(v)
if(j≠k) then i←i+1
T(i,1) ←u; T(i,2) ←v
mincost←mincost + COST(u,v)
call UNION(j,k)
endif
repeat
if i≠n-1 then print(‘no spanning tree’) endif
return
end KRUSKAL
2009-7-27
注：
● 边集以 min-堆的形式保存，一条当前最小成本边可以在 О(loge)的时间内找到；
● 当 i=n-1；此时算法具有最坏的执行时间；
● 算法的计算时间是 О(eloge)
2009-7-27
定理 3.5 Kruskal算法对于每一个无向连通图 G产生一棵最小成本生成树。
证明,设 G是任一无向连通图,T是用 Kruskal算法产生的 G的生成树,T’是 G的最小成本生成树。现要证明 T和 T’具有相同的成本。
设 E(T)和 E(T’)分别是 T和 T’中的边集。若 n是 G中的结点数，则 T
和 T’都有 n-1条边。
若 E(T)＝ E(T’)，则 T就是最小成本生成树
否则，设 e是一条使得 e∈ E(T)和 e E(T’)的最小成本生成边。
显然，这样的 e必定存在。由引理 3.1，把 e加入到 T’就产生一个唯一的环。假设 e,e1,e2,…,ek 是这个唯一的环。这些边 ei,至少有一条不在 E(T)中，如不然，则 T也将包含这个环。设 ej是这环中使得 ej E(T)中的一条边。若 ej比 e有更小的成本，则
Kruskal算法就会在 e之前考虑 ej,并把 ej计入 T。因此,c(ej)
≥ c(e)
现在，在具有边集 E(T’) ∪ {e}的图。去掉环 e,e1,e2,…,ek 上的任意一条边则留下一棵树 T’’。特别是，如果删去边 ej,T’’的成本将不比 T’的成本大。 T’’也是一棵最小成本树。
通过反复上述转换，树 T’可以转换成 T而成本没有增加。故 T是一棵最小成本生成树。
2009-7-27
3.6 单源最短路径
1,问题描述
最短路径问题：
● 每对结点之间的路径问题
● 特定线路下的最短路径问题
● 单源最短路径问题等
单源最短路径问题已知一个 n结点有向图 G=(V,E)和边的权函数
c(e)，求由 G中某指定结点 v0到其它各结点的最短路径。
假定边的权值为正。
2009-7-27
例 3.10 如图所示。设 v0是起始点，求 v0到其它各结点的最短路径。
路径 长度
(1) v0v2 10
(2) v0v2v3 25
(3) v0v2v3v1 45
(4) v0v4 45
注：路径按照长度的 非降次序 给出
v0
v1
v4
v5v3v2
45
45 10
15
20 10
15 3
3520 30
2009-7-27
2,贪心策略求解
1) 度量标准量度的选择：迄今已生成的 所有路径长度之和 ——
为使之达到最小，其中任意一条路径都应具有最小长度：
假定已经构造了 i条最短路径，则下一条要构造的路径应是下一条最短的路径。
处理规则：按照 路径长度 的 非降次序 依次生成从结点 v0到其它各结点的最短路径。
例：
v0→v 2
v0→v 2→v 3
v0→v 2→v 3→v 1
v0→v 4
2009-7-27
需要做什么?
确定与 v0生成最短路径的下一个结点
确定 v0与该结点的最短路径
如何确定？
2009-7-27
2) 贪心算法
设 S是已经对其生成了最短路径的 结点集合 （包括 v0)。
对于当前不在 S中的结点 w，记 DIST(w)是从 v0开始,只经过 S中的结点而在 w结束的那条最短路径的长度。
则有，
SW
2009-7-27
① 如果下一条最短路径是到结点 u，则这条路径是从结点 v0出发在 u处终止，且 只经过 那些在 S中的结点,即由 v0
至 u的这条最短路径上的所有 中间结点 都是 S中的结点,
设 w是这条路径上的任意中间结点，则从 v0到 u的路径也包含了一条从 v0到 w的路径，且其长度小于从 v0到 u
的路径长度。
v0,s1,s2,?,w,?,s m-1,u
均在 S中根据 生成规则,最短路径是按照路径长度的非降次序生成的，因此从 v0到 w的最短路径应该已经生成。从而 w也应该在 S中。
故,不存在 不在 S中的中间结点。
2009-7-27
② 所生成的下一条路径的终点 u必定是所有不在 S内的结点中且具有最小距离 DIST(u)
的结点。
2009-7-27
③ 如果选出了这样结点 u并生成了从 v0到 u的最短路径之后，结点 u将成为 S中的一个成员。此时，那些从 v0出发，
只经过 S中的结点并且在 S外的结点 w处结束的最短路径可能会 减少 —— DIST(w)的值变小：
如果这样的路径的长度发生了改变，则这些路径必定是一条从 v0开始，经过 u然后到 w的 更短 的路所致。
S W
uv
0
2009-7-27
根据 DIST(w)的定义，它所表示的 v0至 w的最短路径上的所有中间结点都在 S中；
只考虑 <u,w>∈E 和 的情况
u是从 v0至 w的最短路径上所经过的结点。
则有,DIST(w) = DIST(u) + c(u,w)
Ewu,
2009-7-27
算法 3.10 生成最短路径的贪心算法
procedure SHORTEST-PATHS(v,COST,DIST,n)
//G是一个 n结点有向图，它由其成本邻接矩阵 COST(n,n)表示 DIST(j)被置以结点 v到结点 j的最短路径长度，这里 1≤j≤n。 DIST(v)被置成零 //
boolean S(1:n);real COST(1:n,1:n),DIST(1:n)
integer u,v,n,num,I,w
for i←1 to n do // 将集合 S初始化为空 //
S(i) ←0;DIST(i) ←COST(v,i)
repeat
S(v) ←1;DIST(v) ←0 // 结点 v计入 S//
for num←2 to n -1 do //确定由结点 v出发的 n-1条路 //
选取结点 u,它使得 DIST(u)=
S(u) ←1 // 结点 u计入 S//
for 所有 S(w)＝ 0的结点 w do //修改 DIST(w)//
DIST(w) = min(DIST(w),DIST(u) + COST(u,w))
repeat
repeat
end SHORTEST-PATHS
)}({m in 0)( wD ISTwS?
2009-7-27
3) 计算时间
⑴ 算法 3.10的计算时间是,О(n2)
⑴ for i←1 to n do
S(i) ←0;DIST(i) ←COST(v,i)
repeat
⑵ for num←2 to n -1 do
选取结点 u,它使得 DIST(u)=
S(u) ←1
for 所有 S(w)＝ 0的结点 w do
DIST(w) = min(DIST(w),DIST(u) + COST(u,w))
repeat
repeat
⑵ 最短路径算法的时间复杂度由于任何一条边 都有可能 是最短路径中的边，所以求任何最短路径的算法都必须至少检查图中的每条边一次，所以这样的算法的最小时间是 О(e)。
邻接矩阵表示的图,О(n2)
)}({m in 0)( wD ISTwS?
)(n?
)2( －n?
)(n?
)(n?
2009-7-27
例 3.11 求下图中从 v1出发到其余各结点的最短路径
v1
v2
v4
v3
v5
v6 v7
20
50
25 70
50
70
10
50
55
40
30 25
图的成本邻接矩阵：
0 20 50 30 +∞ +∞
+∞
+∞ 0 25 +∞ +∞ 70
+∞
+∞ +∞ 0 40 25 50
+∞
+∞ +∞ +∞ 0 55 +∞
+∞
+∞ +∞ +∞ +∞ 0 10
70
2009-7-27
算法的执行轨迹描述迭代 选取的结点
S DIST
(1) (2) (3) (4) (5) (6) (7)
置初值
1
2
3
4
5
－
2
4
3
5
6
1
1,2
1,2,4
1,2,4,3
1,2,4,3,5
1,2,4,3,5,6
0 20 50 30 +∞ +∞ +∞
0 20 45 30 +∞ 90 +∞
0 20 45 30 85 90 +∞
0 20 45 30 70 90 +∞
0 20 45 30 70 90 140
0 20 45 30 70 90 130
算法的执行在有 n-1个结点加入到 S中后终止
2009-7-27
3,最短路径生成树对于无向连通图 G，由结点 v到其余各结点的最短路径的边构成 G的一棵 生成树,称为 最短路径生成树 。
注：不同起点 v的生成树可能不同。
2
1
3
5
6
7
4 8
55
5
25
40
35
15
10
5020
45
30
2
1
3
5
6
7
4 8
5
25
40
15
10
20
30
2
1
3
5
6
7
4 8
55
5
25
15
10
45
30
原始图 由结点 1出发的最短路径生成树 最小成本生成树
第三章 贪心方法
2009-7-27
3.1 一般方法
1,问题的一般特征问题有 n个输入，问题的解是由这 n个输入的某个 子集 组成，这个子集必须满足某些事先给定的条件。
约束条件,子集必须满足的条件；
可行解,满足约束条件的子集；可行解可能不唯一；
目标函数,用来衡量可行解优劣的标准，一般以函数的形式给出；
最优解,能够使目标函数取极值（极大或极小）的可行解。
分类,根据描述问题约束条件和目标函数的 数学模型 的特性和问题的 求解方法 的不同，可分为：线性规划、整数规划、非线性规划、动态规划等。
—— 最优化问题求解贪心方法,一种改进的 分级 的处理方法，可对满足上述特征的某些问题方便地求解。
2009-7-27
例 [找零钱 ] 一个小孩买了价值少于 1美元的糖，并将 1
美元的钱交给售货员。售货员希望用数目最少的硬币找给小孩。假设提供数目不限的面值为 25美分,10美分,5美分及 1美分的硬币。售货员分步骤组成要找的零钱数，每次加入一个硬币。选择硬币时所采用的贪心算法如下：每一次选择应使零钱数尽量增大。为确保解法的可行性（即：所给的零钱等于要找的零钱数），所选择的硬币不应使零钱总数超过最终所需的数目。
假设需要找给小孩 67美分，首先入选的是两枚
25美分的硬币，第三枚入选的不能是 25美分的硬币，
否则将不可行（零钱总数超过 67美分），第三枚应选择 10美分的硬币，然后是 5美分的，最后加入两个 1美分的硬币。
贪心算法有种直觉的倾向，在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）
2009-7-27
2,贪心方法的一般策略问题的一般特征：问题的解是由 n个输入的、满足某些事先给定的条件的子集组成。
1）一般方法根据题意，选取一种 度量标准 。然后按照这种度量标准对 n
个输入 排序,并按序一次输入一个量。
如果这个输入和当前已构成在这种量度意义下的 部分最优解 加在一起不能产生一个可行解，则不把此输入加到这部分解中。否则，将当前输入合并到部分解中从而得到包含当前输入的 新的部分解 。
2）贪心方法这种能够得到某种量度意义下的最优解的 分级处理 方法称为贪心方法注：
贪心解 最优解
直接将目标函数作为 量度标准 也不一定能够得到问题的最优解
3）使用贪心策略求解的关键选取能够得到问题最优解的量度标准。
？＝
2009-7-27
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
end GREEDY
2009-7-27
3.2 背包问题
1.问题的描述已知 n种物品具有重量 (w1,w2,…,w n)和效益值 (p1,p2,…,p n),
及一个可容纳 M重量的背包；设当物品 i全部或一部分 xi放入背包将得到 pi xi的效益，这里,0≤ xi ≤1,p i >0。
问题,采用怎样的装包方法才能使装入背包的物品的 总效益最大？
分析,
① 装入背包的总重量 不能超过 M
② 如果所有物品的 总重量 不超过 M，即 ≤ M，则把 所有 的物品都装入背包中将获得最大可能的效益值
③ 如果物品的总重量 超过了 M，则将有物品不能（全部）
装 入背包中。由于 0≤x i≤1,所以可以把物品的一部分装入背包，所以最终背包中可刚好装入重量为 M的若干物品（整个或一部分）
目标,使装入背包的物品的 总效益 达到 最大 。
ni iixw1
2009-7-27
问题的形式描述目标函数,
约束条件,
可 行 解,满足上述约束条件的 任一集合 (x1,x2,…,x n) 都是问题的一个可行解 —— 可行解可能为多个。
(x1,x2,…,x n)称为问题的一个 解向量最 优 解,能够使目标函数取 最大值 的可行解是问题的最优解 —— 最优解也可能为多个。
ni
iixp
1
niwpx
Mxw
iii
ni
ii
1,0,0,10
1
2009-7-27
例 3.1 背包问题的实例设,n=3,M=20，
(p1,p2,p3) = (25,24,15),(w1,w2,w3) =
(18,15,10)。
可能的可行解如下：
(x1,x2,x3)
① (1/2,1/3,1/4) 16.5 24.25 //没有放满背包 //
② (1,2/15,0 ) 20 28.2
③ (0,2/3,1) 20 31
④ (0,1,1/2) 20 31.5
iixp? iixw
2009-7-27
2,贪心策略求解度量标准的选择：三种不同的选择
1）以 目标函数 作为度量标准即，每装入一件物品，就使背包背包获得 最大 可能的效益增量。
该度量标准下的 处理规则：
● 按效益值的非增次序将物品一件件地放入到背包；
● 如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量标准，
则在 剩下 的物品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。
如：若 Δ M=2,背包外还剩两件物品 i,j，且有 (pi＝ 4,wi＝ 4)
和 (pj＝ 3,wj＝ 2)，则下一步应选择 j而非 i放入背包：
pi/2 = 2 ＜ pj＝ 3
2009-7-27
实例分析（例 3.1)
∵ p1＞ p2＞ p3
∴ 首先将 物品 1放入背包，此时 x1＝ 1，背包获得 p1＝ 25的效益增量，
同时背包容量减少 w1＝ 18个单位，剩余空间 Δ M=2。
其次考虑 物品 2和 3。就 Δ M=2而言有，只能选择物品 2或 3的 一部分 装入背包。
物品 2,若 x2＝ 2/15,则 p2 x2＝ 16/5＝ 3.1
物品 3,若 x3＝ 2/10,则 p3 x3＝ 3
为使背包的效益有最大的增量，应选择 物品 2的 2/15装包，即
x2＝ 2/15
最后，背包装满,Δ M=0，故 物品 3将不能装入背包,x3＝ 0 。
背包最终可以获得 效益值 ＝ x1 p1 ＋ x2 p2＋ x3 p3
＝ 28.2 (次优解,非问题的最优解 )
2009-7-27
2）以 容量 作为度量标准以 目标函数 作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而不能装入,更多” 的物品。
改进：让背包 容量 尽可能慢地消耗，从而可以尽量装入“更多”的物品。
即，新的标准是：以 容量 作为度量标准该度量标准下的处理规则：
● 按物品 重量的非降次序 将物品装入到背包；
● 如果正在考虑的物品放不进去，则只取其一部分装满背包；
2009-7-27
实例分析（例 3.1)
∵ w3＜ w2 ＜ w1
∴ 首先将 物品 3放入背包，此时 x3＝ 1，背包容量减少 w3
＝ 10个单位，还剩余空间 Δ M=10。同时,背包获得 p3＝
15的效益增量 。
其次考虑 物品 1和 2。就 Δ M=10而言有，也只能选择物品 1或 2的 一部分 装入背包。 为使背包的按照“统一”的规则，下一步将放入 物品 2的 10/15装包，即
x2＝ 10/15＝ 2/3
最后，背包装满 Δ M=0，故 物品 1将不能装入背包,x1
＝ 0 。
背包最终可以获得 效益值 ＝ x1 p1 ＋ x2 p2＋ x3 p3
＝ 31 (次优解,非问题的最优解
2009-7-27
3）最优的度量标准影响背包效益值得因素：
背包的 容量 M
放入背包中的物品的重量及其可能带来的效益值可能的策略 是：在背包效益值的增长速率和背包容量消耗速率之间取得 平衡,即每次装入的物品应使它所占用的每一 单位容量 能获得当前最大的单位效益。
在这种策略下的 量度 是：已装入的物品的累计效益值与所用容量之比。
故，新的 量度标准 是：每次装入要使累计效益值与所用容量的比值有最多的增加（首次装入）和最小的减小（其后的装入）。
此时，将按照物品的单位效益值,pi/wi 比值（密度）的非增次序考虑。
2009-7-27
实例分析（例 3.1)
∵ p1/w1＜ p3/w3 ＜ p2/w2
∴ 首先将 物品 2放入背包，此时 x2＝ 1，背包容量减少 w2
＝ 15个单位，还剩余空间 Δ M=5。同时,背包获得 p2＝
24的效益增量 。
其次考虑 物品 1和 3。此时，应选择物品 3,且就 Δ M=5而言有，也只能放入物品 3的 一部分 到背包中 。 即
x3＝ 5/10＝ 1/2
最后，背包装满 Δ M=0，故 物品 1将不能装入背包,x1
＝ 0 。
背包最终可以获得 效益值 ＝ x1 p1 ＋ x2 p2＋ x3 p3
＝ 31.5 (最优解 )
2009-7-27
3,背包问题的贪心求解算法算法 3.2 背包问题的贪心算法
procedure GREEDY－ KNAPSACK(P,W,M,X,n)
//p(1:n)和 w(1:n)分别含有按 P(i)/W(i)≥P(i＋ 1)/W(i＋ 1)排序的 n
件物品的效益值和重量。 M是背包的容量大小，而
x(1:n)是解向量 //
real P(1:n),W(1:n),X(1:n),M,cu;
integer I,n
X←0 // 将解向量初始化为空 //
cu←M //cu 是背包的剩余容量 //
for i←1 to n do
if W(i) > cu then exit endif
X(i) ←1
cu ←cu -W(i)
repeat
if i≤n then X(i) ←cu/W(i) endif
end GREEDY-KNAPSACK
2009-7-27
4,最优解的证明即证明：由第三种策略所得到的贪心解是问题的 最优解 。
最优解 的含义：在满足约束条件的情况下，可使目标函数取极
（大或小）值的可行解。贪心解是可行解，故只需证明：贪心解可使目标函数取得极值。
证明的 基本思想,将此贪心解与（假设中的）任一最优解 相比较 。
● 如果这两个解相同，则显然贪心解就是最优解。否则，
● 这两个解不同，就去找开始 不同 的第一个分量位置 i，然后设法用贪心解的这个 xi去 替换 最优解的那个 xi,并证明最优解在分量代换前后总的效益值没有任何变化。
可反复进行代换，直到新产生的最优解与贪心解完全一样。这一代换过程中，最优解的 效益值没有任何损失,从而证明贪心解的效益值与代换前后最优解的效益值相同。即，贪心解如同最优解一样可取得目标函数的最大 /最小值。
从而得证：该 贪心解 也即问题的 最优解 。
2009-7-27
定理 3.1 如果 p1/w1≥ p2/w2≥…≥ p n/wn,则算法
GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。
证明,
设 X=(x1,x2,…,x n)是 GREEDY-KNAPSACK所生成的 贪心解 。
① 如果所有的 xi都等于 1,则显然 X就是问题的 最优解 。否则，
② 设 j是使 xi≠1的最小下标。由算法可知，
xi=1 1≤i＜ j,
0≤xj ＜ 1
xi=0 j＜ i≤n
若 X不是问题的最优解，则必定存在一个可行解 Y=(y1,
y2,…,y n),使得：
且应有：
iiii xpyp
Myp ii
2009-7-27
设 k是使得 yk≠ xk的最小下标，则有 yk＜ xk:
a) 若 k<j，则 xk=1。因为 yk≠ xk,从而有 yk ＜ xk
b) 若 k=j，由于,且对 1≤i＜ j，有 yi=xi=1,而对 j＜ i≤n,
有 xi＝ 0；故此时若 yk＞ xk，则将有,与 Y是可行解相矛盾。
而 yk≠ xk,所以 yk ＜ xk
c) 若 k＞ j，则,不能成立在 Y中作以下调整：将 yk增加到 xk，因为 yk < xk,为保持解的可行性，必须从 ( yk+1,…,y n)中减去同样多的量。设调整后的解为
Z=(z1,z2,…,z n)，其中 zi＝ xi,1≤i≤k，且有：
则对于 Z有：
Mxw ii
Myw ii
Myw ii
nik kkkiii yzwzyw )()(
ni iiinik iikkkkkiini ii wpwzywpwyzypzp 11 /)(/)(
ni kkinik iikkkii wpwzywyzyp1 /])()[(
ni ii yp1
2009-7-27
由以上分析得，
若,则 Y将不是最优解；
若,则或者 Z=X，则 X就是最优解；
或者 Z≠X,则重复以上替代过程，或者证明 Y不是最优解，或者把 Y转换成 X，从而证明 X是最优解
iiii ypzp
iiii ypzp
2009-7-27
3.3 带有限期的作业排序
1,问题描述假定在一台机器上处理 n个作业，每个作业均可在单位时间内完成；同时每个作业 i都有一个 截至期限 di>0,当且仅当作业 i在其截至期限以前被完成时，则获得 pi>0的效益。
问题,求这 n个作业的一个子集 J，其中的所有作业都可在其截至期限内完成。 —— J是问题的一个可行解。
可行解 J中的 所有作业的效益之和是,具有 最大效益值的 可行解是该问题的最优解。
如果所有的作业都能在其期限之内完成则显然可以获得当前最大效益值；否则，将有作业无法完成 —— 决策应该执行哪些作业，
以获得最大可能的效益值。
目标函数：
约束条件,所有的作业都应在其期限之前完成
Ji ip
Ji ip
2009-7-27
例 3.2 n=4,(p1,p2,p3,p4)＝ (100,10,15,20)和 (d1,d2，
d3,d4)＝ (2,1,2,1)。可行解如下表所示：
问题的最优解是 ⑦。所允许的处理次序是：先处理作业 4再处理作业 1。
可行解 处理顺序 效益值
① （ 1） 1 100
② （ 2） 2 10
③ （ 3） 3 15
④ （ 4） 4 20
⑤ （ 1,2） 2,1 110
⑥ （ 1,3） 1,3或 3,1 115
⑦ （ 1,4） 4,1 120
⑧ （ 2,3） 2,3 25
⑨ （ 3,4） 4,3 35
2009-7-27
1,带有限期的作业排序算法
1) 度量标准的选择以目标函数 作为量度。
量度标准：下一个要计入的作业将是使得在满足所产生的 J是一个可行解的限制条件下让得到最大增加的作业。
处理规则：按 pi的非增次序来考虑这些作业。
Ji i
p
Ji i
p
2009-7-27
例：例 3.2求解
① 首先令 J=Φ,
② 作业 1具有当前的最大效益值，且 {1}是可行解，所以作业 1计入 J；
③ 在剩下的作业中，作业 4具有最大效益值，
且 {1,4}也是可行解，故作业 4计入 J，即 J={1,4}；
④ 考虑 {1,3,4}和 {1,2,4}均不能构成新的可行解，作业 3和 2将被舍弃。
故最后的 J={1,4}，最终效益值＝ 120（问题的最优解 ）
0
Ji i
p
2009-7-27
2)作业排序算法的概略描述算法 3.3
procedure GREEDY-JOB(D,J,n)
//作业按 p1≥p2≥…≥p n的次序输入，它们的期限值 D(i)≥1,
1≤i≤n,n≥1。 J是在它们的截止期限完成的作业的集合 //
J←{1}
for i←2 to n do
if J∪ {i}的所有作业能在它们的截止期限前完成
then J←J ∪ {i}
endif
repeat
end GREEDY-JOB
2009-7-27
2,最优解证明定理 3.2 算法 3.3对于作业排序问题总是得到问题的一个 最优解证明,
设 J是由算法所得的 贪心解 作业集合,I是一个 最优解的作业集合。
① 若 I=J，则 J就是最优解；否则
②,即至少存在两个作业 a和 b，使得 a∈ J
且,b∈ I且 。
并设 a是这样的一个具有 最高效益值 的作业，且由算法的处理规则可得：对于在 I中而不在 J中的作业所有 b，
有：
pa≥pb
Ia? Jb?
IJJI 且
2009-7-27
设 SJ和 SI分别是 J和 I的可行的 调度表 。因为 J和 I都是可行解，故这样的调度表一定存在；
设 i是既属于 J又属于 I的一个作业，并 i设在调度表 SJ中的调度时刻是 [t,t+1],而在 SI中的调度时刻是 [t’,t’+1]。
在 SJ和 SI中作如下调整：
● 若 t＜ t’,则将 SJ中在 [t’,t’+1]时刻调度的那个作业
（如果有的话）与 i相交换。如果 J中在 [t’,t’+1]时刻没有作业调度，则直接将 i移到 [t’,t’+1]调度。 —— 新的调度表也是可行的。反之，
● 若 t’＜ t，则在 SI中作类似的调换，即将 SI中在 [t，
t+1]时刻调度的那个作业（如果有的话）与 i相交换。如果 I
中在 [t,t+1]时刻没有作业调度，则直接将 i移到 [t,t+1]调度。 —— 同样，新的调度表也是可行的。
对 J和 I中共有的所有作业作上述的调整。设调整后得到的调度表为 S’J和 S’I，则在 S’J和 S’I中 J和 I中 共有 的所有作业将在相同的时间被调度。
2009-7-27
设 a在 S’J中的调度时刻是 [ta,ta+1],b是 S’I中该时刻调度的作业。根据以上的讨论有,pa≥pb。
在 S’I中，去掉作业 b，而去调度作业 a，得到的是作业集合 I’=I-{b} ∪ {a}的 一个可行的调度表，且 I’的效益值不小于 I的效益值。而 I’中比 I少了一个与 J不同的作业。
重复上述的转换，可使 I在 不减 效益值的情况下转换成 J。从而 J至少有和 I一样的效益值。所以 J也是最优解。
证毕。
2009-7-27
3,如何判断 J的可行性方法一,检验 J中作业所有可能的排列，对于任一种次序排列的作业排列，判断这些作业是否能够在其期限前完成 —
— 若 J
中有 k个作业，则将要检查 k!个序列方法二,检查 J中作业的一个 特定序列 就可判断 J的可行性：
对于所给出的一个排列 σ ＝ i1i2?i k,由于作业 ij完成的最早时间是 j，因此只要判断出 σ 排列中的每个作业
dij≥j,就可得知 σ 是一个允许的调度序列，从而 J
是一个可行解。反之，如果 σ 排列中有一个 dij＜ j,则 σ 将
2009-7-27
定理 3.3 设 J是 k个作业的集合,σ＝ i1i2…i k是 J中作业的一种排列，它使得 di1≤di2≤…≤d ik。 J是一个可行解,当且仅当 J中的作业可以按照 σ的次序而又不违反任何一个期限的情况来处理。
证明：
① 如果 J中的作业可以按照 σ的次序而又不违反任何一个期限的情况来处理，则 J是一个可行解
② 若 J是一个可行解，则必存在序列 σ’＝ r1r2…r k，使得 drj≥ j,
1≤j≤k。
★ 若 σ＝ σ’，则 σ即是可行解。否则，
★ σ≠σ’，令 a是使得 ra≠ia的最小下标，并设 rb=ia。则有：
b＞ a 且 dra≥drb (为什么?)
在 σ’中调换 ra与 rb，所得的新序列 σ’’＝ s1s2…s k的处理次序不违反任何一个期限。
重复上述过程，则可将 σ’转换成 σ且不违反任何一个期限。故 σ
是一个 可行 的调度序列故定理得证 。
2009-7-27
5,带有限期的作业排序算法的实现对当前正在考虑的作业 j，按限期大小采用一种,插入排序” 的方式，尝试将其“插入”到一个按限期从小到大顺序构造的作业调度序列中，以此判断是否能够合并到当前部分解 J中。如果可以，则插入到序列中，形成新的可行解序列。否则，舍弃该作业。
具体如下：
假设 n个作业已经按照效益值从大到小的次序，即
p1≥p2≥…≥p n的顺序排列好，每个作业可以在 单位时间 内完成，并具有相应的时间期限；且至少有一个单位时间可以执行作业首先，将作业 1存入部分解 J中，此时 J是可行的；
然后，依次考虑作业 2到 n。假设已经处理了 i-1个作业，
其中有 k个作业计入了部分解 J中,J(1),J(2),…,J(k),且有
D(J(1))≤D(J(2))≤…≤D(J(k))
2009-7-27
对当前正在考虑的作业 i,将 D(i)依次和 D(J(k)),
D(J(k-1)),?,D(J(1))相比较，直到找到位置 q：使得
★ D(i)＜ D(J(l)),q＜ l≤k,且
★ D(J(q))≤ D(i)
此时，若 D(J(l))＞ l,q＜ l≤k,即说明 q位置之后的所有作业均可 推迟 一个单位时间执行，而又不违反各自的执行期限。
最后，将 q位置之后的所有作业后移一位，将作业 i插入 到位置 q＋ 1处，从而得到一个包含 k+1个作业的新的可行解。
若找不到这样的 q，作业 i将被舍弃。
对 i之后的其它作业重复上述过程直到 n个作业处理完毕。最后 J中所包含的作业集合是此时算法的贪心解，也是问题的最优解。
2009-7-27
σ＝ i1 i2 … ia … … ic … ik
σ’＝ r1 r2 … ra … rb … r k
★ a＜ b
★ dra≥drb
2009-7-27
算法 3.4 带有限期和效益的单位时间的作业排序贪心算法
procedure JS(D,J,n,k)
//D(1),…,D(n) 是期限值。 n≥1。作业已按 p1≥p2≥…≥p n的顺序排序。 J(i)是最优解中的第 i个作业,1≤i≤k。终止时,D(J(i))≤D(J(i＋ 1)),1≤i＜ k//
integer D(0:n),J(0:n),i,k,n,r
D(0)←J(0)←0 // 初始化 //
k←1;J(1)←1 // 计入作业 1//
for i←2 to n do //按 p的非增次序考虑作业。找 i的位置并检查插入的可行性 //
r←k
while D(J(r))＞ D(i) and D(J(r)) ≠r do
r←r -1
repeat
If D(J(r))≤D(i) and D(i)＞ r then //把 i插入到 J中 //
for i←k to r+1 by -1 do
J(i+1) ←J(i) // 将插入点的作业后移一位 //
repeat
J(r+1) ←I;k←k+1
endif
repeat
end JS
2009-7-27
计算时间分析
for i←2 to n do? 将循环 n-1次－－－－－－－－－－－－－－－－－－
①
r←k
while D(J(r))＞ D(i) and D(J(r)) ≠r do? 至多循环 k次，
k是当前计入 J中的作业数 －－－
②
r←r -1
repeat
If D(J(r))≤D(i) and D(i)＞ r then
for i←k to r+1 by -1 do? 循环 k-r次,r是插入点的位置 －－－－
－ ③
J(i+1) ←J(i)
repeat
J(r+1) ←I;k←k+1
endif
repeat
设 s是最终计入 J中的作业数，则算法 JS所需要的总时间是 O(sn)。
s≤n,故最坏情况,TJS = О(n2)，特例情况,pi=di=n-i+1,1≤i≤n
2009-7-27
6,一种“更快”的作业排序问题使用不相交集合的 UNION和 FIND算法
（见 1.4.3节），可以将 JS的计算时间降低到数量级接近 О(n)。
（略）
2009-7-27
3.4 最优归并模式
1,问题的描述
1）两个文件的归并问题两个已知文件的一次归并所需的计算时间＝ O(两个文件的元素总数 )
例：
n个记录的文件
＋ (n+m) 个记录的文件
m个记录的文件 О(n+m)
2）多个文件的归并已知 n个文件，将之归并成一个单一的文件例：假定文件 X1,X2,X3,X4，采用两两归并的方式，可能的归并模式有：
① X1+X2=Y1+X3= Y2+X4= Y3
② X1+X2 = Y1
+ → Y3
X3+X4=Y2
2009-7-27
二路归并模式：每次仅作两个文件的归并；当有多个文件时，采用两两归并的模式，最终得到一个完整的记录文件。
二元归并树：二路归并模式的归并过程可以用一个二元树的形式描述，
称之为二元归并树。
如归并树的构造外结点,n个原始文件内结点：一次归并后得到的文件在两路归并模式下，每个内结点刚好有两个儿子，代表把它的两个儿子表示的文件归并成其本身所代表的文件
60
50
30 20
10
X1
Z1
X
X3
X2
2009-7-27
不同的归并顺序带来的计算时间是不同的。
例 3.5 已知 X1,X2,X3是分别为 30,20,10个记录长度的已分类文件。将这 3个文件归并成长度为 60的文件。可能的归并过程和相应的记录移动次数如下：
问题：采用怎样的归并顺序才能使归并过程中元素的移动次数最小（或执行的速度最快）
X
X3
X2
X1
移动 50次移动 60次
X
X1
X2
X3
移动 30次移动 60次总移动次数,110次总移动次数,90次
2009-7-27
2,贪心求解
1) 度量标准的选择
★ 任意两个文件的归并所需的 元素移动次数 与这两个文件的 长度之和 成 正比；
★ 度量标准,每次选择需要移动次数最少的两个集合进行归并；
★ 处理规则,每次选择长度最小的两个文件进行归并。
95
35
5
20 30
60
3015
10
F4 F3
Z1
Z2
Z4
Z3
F1 F5 F2
(F1,F2,F3,F4,F5) = (20,30,10,5,30)
2009-7-27
2) 目标函数目标,元素移动的次数最少实例：为得到归并树根结点表示的归并文件，外部结点中每个文件记录需要移动的次数＝该外部结点到根的距离，即根到该外部结点路径的长度。如，
F4,
则 F4中所有记录在整个归并过程中移动的总量＝ |F4|*3
带权外部路径长度,记 di是由根到代表文件 Fi的外部结点的距离,qi是 Fi的长度，则这棵树的代表的归并过程的元素移动总量是：
最优的二路归并模式,与一棵具有 最小外部带权路径长度的二元树相对应。
F4 Z1 Z2 Z4
ni iidq1
2009-7-27
算法 3.6 生成二元归并树的算法
procedure TREE(L,n)
//L是 n个单结点的二元树表 //
for i←1 to n -1 do
call GETNODE(T) //构造一颗新树 T//
LCHILD(T) ←LEAST(L) //从表 L中选当前根 WEIGHT最小的树，
并从中删除 //
RCHILD(T) ←LEAST(L)
WEIGHT(T)
←WEIGHT(LCHILD(T))+WEIGHT(RCHILD(T))
call INSERT(L,T) //将归并的树 T加入到表 L中 //
repeat
return (LEAST(L)) //此时,L中的树即为归并的结果 //
end TREE
2009-7-27
例 3.6 已知六个初始文件，长度分别为,2,3,5,7,9,13。
采用算法 TREE，各阶段的工作状态如图所示：
L迭代
2 3 5 7 9 130
2 3
5 7 9 131 5
2 3
5 7 9 132 5
10
2009-7-27
2 3
5 7 9 133 5
10 16
2 3
5 7 9
13
4
5
10 16
23
2 3
5
7 9 13
5
5
10
16 23
39
2009-7-27
时间分析
1) 循环体,n-1次
2) L以有序序列表示
LEAST(L),О(1)
INSERT(L,T),О(n)
总时间,О(n2)
3) L以 min-堆表示
LEAST(L),О(logn)
INSERT(L,T),О(logn)
总时间,О(nlogn)
2009-7-27
3,最优解的证明定理 3.4 若 L最初包含 n≥1个单结点的树，这些树有 WEIGHT
值为 (q1,q2,…,q n)，则算法 TREE对于具有这些长度的 n个文件生成一棵最优的二元归并树。
证明,归纳法 证明
① 当 n=1时，返回一棵没有内部结点的树。定理得证。
② 假定算法对所有的 (q1,q2,…,q m),1≤m＜ n,生成一棵最优二元归并树。
③ 对于 n,假定 q1≤q2≤…≤q n,则 q1和 q2将是在 for循环的第一次迭代中首先选出的具有最小 WEIGHT值的两棵树（的 WEIGHT
值）；如图所示,T是由这样的两棵树构成的子树：
q1 q2
q1+q2T
2009-7-27
■ 设 T’是一棵对于 (q1,q2,…,q n)的最优二元归并树。
■ 设 P是 T’中距离根 最远 的一个 内部结点 。
若 P的两棵子树不是 q1和 q2，则用 q1和 q2代换 P当前的子树而不会增加 T’的带权外部路径长度。
故,T应是最优归并树中的子树。
则在 T’中用一个权值为 q1＋ q2的外部结点代换 T，得到的是一棵关于 (q1＋ q2,…,q n)最优归并树 T”。
而由归纳假设，在用权值为 q1＋ q2的外部结点代换了
T之后，过程 TREE将针对 (q1＋ q2,…,q n)得到一棵最优归并树。将 T带入该树，根据以上讨论，将得到关于
(q1,q2,…,q n)的最优归并树。
故,TREE生成一棵关于 (q1,q2,…,q n)的 最优归并树 。
2009-7-27
5,k路归并模式
每次 同时 归并 k个文件。
k元归并树：可能需要增加,虚” 结点，以补充不足的外部结点。
★ 如果一棵树的所有内部结点的度都为 k，则外部结点数 n满足 n mod (k-1) = 1
★ 对于满足 n mod (k－ 1) =1的整数 n，存在一棵具有 n个外部结点的 k元树 T，且 T中所有结点的度为 k。
至多需要增加 k-2个外部结点。
k路最优归并模式得贪心规则：每一步选取 k棵具有最小长度的子树归并。
2009-7-27
3.5 最小生成树
1,问题的描述生成树,设 G=(V,E)是一个无向连通图。如果 G的生成子图 T=(V,E')是一棵树，则称 T是 G的一棵生成树 (spanning tree)．
最小生成树,
2,贪心策略度量标准：选择能使迄今为止所计入的边的 成本和 有最小增加 的那条边。
● Prim算法
● Kruskal算法
2009-7-27
3,Prim算法策略：使得迄今所选择的边的集合 A构成一棵树；对将要计入到 A中的下一条边 (u,v)，应是 E中一条当前不在 A中且使得
A∪{(u,v)} 也是一棵树的最小成本边。
1
4
6
2
5
3
10
30
20
45
25 55
40
50
15
35
1 2
1
6
2
1
6
2 3
1
6
2 3
4
边
(1,2)
(2,6)
(3,6)
(6,4)
成本
10
25
15
20
2009-7-27
1
4
6
2
5
3
10
20
25
15
35边
(3,5)
成本
35
V(TP) = {1,2,3,4,5,6}
E(TP) = { (1,2),(2,6),(3,5),(4,6),(3,6) }
2009-7-27
算法 3.7 Prim最小生成树算法
procedure PRIM(E,COST,n,T,mincost)
//E是 G的边集。 COST(n,n)是 n结点图 G的成本邻接矩阵，矩阵元素
COST(i,j)是一个正实数，如果不存在边 (i,j)，则为＋ ∞。计算一棵最小生成树并把它作为一个集合存放到数组 T(1:n-1,2)中 (T(i,1),T(i,2))是最小成本生成树的一条边。最小成本生成树的总成本最后赋给 mincost//
real COST(n,n),mincost
integer NEAR(n),n,i,k,l,T(1:n-1,2)
(k,l)← 具有最小成本的边
mincost←COST(k,l)
(T(1,1),T(1,2)) ←(k,l)
for i←1 to n do // 将 NEAR置初值 //
if COST(i,l) ＜ COST(i,k) then NEAR(i)←l
else NEAR(i) ←k
endif
repeat
2009-7-27
NEAR(k)←NEAR(l)←0
for i←2 to n -1 do //找 T的其余 n-2条边 //
设 j是 NEAR(j)≠0 且 COST(j,NEAR(j))最小的下标
(T(i,1),T(i,2))←(j,NEAR(j))
mincost←mincost+COST(j,NEAR(j))
NEAR(j)←0
for k←1 to n do // 修改 NEAR//
if NEAR(k)≠0 and COST(k,NEAR(k))＞ COST(k,j)
then NEAR(k)←j
endif
repeat
repeat
if mincost＞ ∞ then print(‘no spanning tree’) endif
end PRIM
2009-7-27
计算复杂性：
第 3行花费 Θ (e)(e=|E|)时间，第 4行花费 Θ (1)时间；
第 6－ 9行的循环花费 Θ (n)时间；第 12行和第 16－ 20
行的循环要求 Θ (n)时间，因此第 11－ 21行循环要花费 Θ (n)时间。
所以 PRIM算法具有 的时间复杂度
)( 2n?
2009-7-27
最小生成树中包含了与每个结点 v相关的一条最小成本边证明略
方法：从一棵包含任何一个随意指定的结点而没有边的树开始这一算法，
然后再逐条增加边。
2009-7-27
4,Kruskal算法
（连通）图的边按成本的非降次序排列，下一条计入生成树 T
中的边是还没有计入的边中具有最小成本、且和 T中现有的边不会构成环路的边。
1
4
6
2
5
3
10
30
20
45
25 55
40
50
15
35
1 2
1
6
2
1
6
2 3
1
6
2 3
4
边
(1,2)
(3,6)
(4,6)
(2,6)
成本
10
15
20
25
1
6
2
3 4 5
63 4 5
3 4 5
4
5
5
2009-7-27
1
4
6
2
5
3
10
20
25
15
35边
(1,4)
(3,5)
成本
30 舍弃
35
V(TK) = {1,2,3,4,5,6}
E(TK) = { (1,2),(2,6),(3,5),(4,6),(3,6) }
2009-7-27
如何判断加入的边不构成环
把 T的同一连通分图中所有结点放到一个集合中。
T中的两个结点是连通的，当且仅当它们在同一个集合中。
如：考虑边 (2,6)时，这些集合是 {1,2},{3,4,6}和 {5}。
结点 2和 6在不同的集合中，因此这些集合可以合并为 {1,2,3,4,6}和 {5}。下一条边是 (1,4),1和 4在同一个集合中，因此舍弃。
2009-7-27
算法 3.9 Kruskal算法
procedure KRUSKAL(E,COST,N,T,mincost)
//G有 n个结点,E是 G的边集。 COST(u,v)是边 (u,v)的成本。 T是最小成本生成树的边集,mincost是它的成本 //
real mincost,COST(1:n,1:n); integer PARENT(1:n),T(1:n-1,2),n
以边成本为元素构造一个 min堆
PARENT← － 1//每个结点都在不同的集合中 //
i←mincost←0
while i＜ n-1 and 堆非空 do
从堆中删去最小成本边 (u,v)并重新构造堆
j←FIND(u); k←FIND(v)
if(j≠k) then i←i+1
T(i,1) ←u; T(i,2) ←v
mincost←mincost + COST(u,v)
call UNION(j,k)
endif
repeat
if i≠n-1 then print(‘no spanning tree’) endif
return
end KRUSKAL
2009-7-27
注：
● 边集以 min-堆的形式保存，一条当前最小成本边可以在 О(loge)的时间内找到；
● 当 i=n-1；此时算法具有最坏的执行时间；
● 算法的计算时间是 О(eloge)
2009-7-27
定理 3.5 Kruskal算法对于每一个无向连通图 G产生一棵最小成本生成树。
证明,设 G是任一无向连通图,T是用 Kruskal算法产生的 G的生成树,T’是 G的最小成本生成树。现要证明 T和 T’具有相同的成本。
设 E(T)和 E(T’)分别是 T和 T’中的边集。若 n是 G中的结点数，则 T
和 T’都有 n-1条边。
若 E(T)＝ E(T’)，则 T就是最小成本生成树
否则，设 e是一条使得 e∈ E(T)和 e E(T’)的最小成本生成边。
显然，这样的 e必定存在。由引理 3.1，把 e加入到 T’就产生一个唯一的环。假设 e,e1,e2,…,ek 是这个唯一的环。这些边 ei,至少有一条不在 E(T)中，如不然，则 T也将包含这个环。设 ej是这环中使得 ej E(T)中的一条边。若 ej比 e有更小的成本，则
Kruskal算法就会在 e之前考虑 ej,并把 ej计入 T。因此,c(ej)
≥ c(e)
现在，在具有边集 E(T’) ∪ {e}的图。去掉环 e,e1,e2,…,ek 上的任意一条边则留下一棵树 T’’。特别是，如果删去边 ej,T’’的成本将不比 T’的成本大。 T’’也是一棵最小成本树。
通过反复上述转换，树 T’可以转换成 T而成本没有增加。故 T是一棵最小成本生成树。
2009-7-27
3.6 单源最短路径
1,问题描述
最短路径问题：
● 每对结点之间的路径问题
● 特定线路下的最短路径问题
● 单源最短路径问题等
单源最短路径问题已知一个 n结点有向图 G=(V,E)和边的权函数
c(e)，求由 G中某指定结点 v0到其它各结点的最短路径。
假定边的权值为正。
2009-7-27
例 3.10 如图所示。设 v0是起始点，求 v0到其它各结点的最短路径。
路径 长度
(1) v0v2 10
(2) v0v2v3 25
(3) v0v2v3v1 45
(4) v0v4 45
注：路径按照长度的 非降次序 给出
v0
v1
v4
v5v3v2
45
45 10
15
20 10
15 3
3520 30
2009-7-27
2,贪心策略求解
1) 度量标准量度的选择：迄今已生成的 所有路径长度之和 ——
为使之达到最小，其中任意一条路径都应具有最小长度：
假定已经构造了 i条最短路径，则下一条要构造的路径应是下一条最短的路径。
处理规则：按照 路径长度 的 非降次序 依次生成从结点 v0到其它各结点的最短路径。
例：
v0→v 2
v0→v 2→v 3
v0→v 2→v 3→v 1
v0→v 4
2009-7-27
需要做什么?
确定与 v0生成最短路径的下一个结点
确定 v0与该结点的最短路径
如何确定？
2009-7-27
2) 贪心算法
设 S是已经对其生成了最短路径的 结点集合 （包括 v0)。
对于当前不在 S中的结点 w，记 DIST(w)是从 v0开始,只经过 S中的结点而在 w结束的那条最短路径的长度。
则有，
SW
2009-7-27
① 如果下一条最短路径是到结点 u，则这条路径是从结点 v0出发在 u处终止，且 只经过 那些在 S中的结点,即由 v0
至 u的这条最短路径上的所有 中间结点 都是 S中的结点,
设 w是这条路径上的任意中间结点，则从 v0到 u的路径也包含了一条从 v0到 w的路径，且其长度小于从 v0到 u
的路径长度。
v0,s1,s2,?,w,?,s m-1,u
均在 S中根据 生成规则,最短路径是按照路径长度的非降次序生成的，因此从 v0到 w的最短路径应该已经生成。从而 w也应该在 S中。
故,不存在 不在 S中的中间结点。
2009-7-27
② 所生成的下一条路径的终点 u必定是所有不在 S内的结点中且具有最小距离 DIST(u)
的结点。
2009-7-27
③ 如果选出了这样结点 u并生成了从 v0到 u的最短路径之后，结点 u将成为 S中的一个成员。此时，那些从 v0出发，
只经过 S中的结点并且在 S外的结点 w处结束的最短路径可能会 减少 —— DIST(w)的值变小：
如果这样的路径的长度发生了改变，则这些路径必定是一条从 v0开始，经过 u然后到 w的 更短 的路所致。
S W
uv
0
2009-7-27
根据 DIST(w)的定义，它所表示的 v0至 w的最短路径上的所有中间结点都在 S中；
只考虑 <u,w>∈E 和 的情况
u是从 v0至 w的最短路径上所经过的结点。
则有,DIST(w) = DIST(u) + c(u,w)
Ewu,
2009-7-27
算法 3.10 生成最短路径的贪心算法
procedure SHORTEST-PATHS(v,COST,DIST,n)
//G是一个 n结点有向图，它由其成本邻接矩阵 COST(n,n)表示 DIST(j)被置以结点 v到结点 j的最短路径长度，这里 1≤j≤n。 DIST(v)被置成零 //
boolean S(1:n);real COST(1:n,1:n),DIST(1:n)
integer u,v,n,num,I,w
for i←1 to n do // 将集合 S初始化为空 //
S(i) ←0;DIST(i) ←COST(v,i)
repeat
S(v) ←1;DIST(v) ←0 // 结点 v计入 S//
for num←2 to n -1 do //确定由结点 v出发的 n-1条路 //
选取结点 u,它使得 DIST(u)=
S(u) ←1 // 结点 u计入 S//
for 所有 S(w)＝ 0的结点 w do //修改 DIST(w)//
DIST(w) = min(DIST(w),DIST(u) + COST(u,w))
repeat
repeat
end SHORTEST-PATHS
)}({m in 0)( wD ISTwS?
2009-7-27
3) 计算时间
⑴ 算法 3.10的计算时间是,О(n2)
⑴ for i←1 to n do
S(i) ←0;DIST(i) ←COST(v,i)
repeat
⑵ for num←2 to n -1 do
选取结点 u,它使得 DIST(u)=
S(u) ←1
for 所有 S(w)＝ 0的结点 w do
DIST(w) = min(DIST(w),DIST(u) + COST(u,w))
repeat
repeat
⑵ 最短路径算法的时间复杂度由于任何一条边 都有可能 是最短路径中的边，所以求任何最短路径的算法都必须至少检查图中的每条边一次，所以这样的算法的最小时间是 О(e)。
邻接矩阵表示的图,О(n2)
)}({m in 0)( wD ISTwS?
)(n?
)2( －n?
)(n?
)(n?
2009-7-27
例 3.11 求下图中从 v1出发到其余各结点的最短路径
v1
v2
v4
v3
v5
v6 v7
20
50
25 70
50
70
10
50
55
40
30 25
图的成本邻接矩阵：
0 20 50 30 +∞ +∞
+∞
+∞ 0 25 +∞ +∞ 70
+∞
+∞ +∞ 0 40 25 50
+∞
+∞ +∞ +∞ 0 55 +∞
+∞
+∞ +∞ +∞ +∞ 0 10
70
2009-7-27
算法的执行轨迹描述迭代 选取的结点
S DIST
(1) (2) (3) (4) (5) (6) (7)
置初值
1
2
3
4
5
－
2
4
3
5
6
1
1,2
1,2,4
1,2,4,3
1,2,4,3,5
1,2,4,3,5,6
0 20 50 30 +∞ +∞ +∞
0 20 45 30 +∞ 90 +∞
0 20 45 30 85 90 +∞
0 20 45 30 70 90 +∞
0 20 45 30 70 90 140
0 20 45 30 70 90 130
算法的执行在有 n-1个结点加入到 S中后终止
2009-7-27
3,最短路径生成树对于无向连通图 G，由结点 v到其余各结点的最短路径的边构成 G的一棵 生成树,称为 最短路径生成树 。
注：不同起点 v的生成树可能不同。
2
1
3
5
6
7
4 8
55
5
25
40
35
15
10
5020
45
30
2
1
3
5
6
7
4 8
5
25
40
15
10
20
30
2
1
3
5
6
7
4 8
55
5
25
15
10
45
30
原始图 由结点 1出发的最短路径生成树 最小成本生成树
