第3章 贪心算法

贪心算法的直观含义 1. 例1.找硬币方法就是一种贪心算法. 2.顾名思义，贪心算法总是作出在当前看来是最好的选择。也就是说贪心算法不从整体最优上加以考虑，它所作出的选择只是在某种意义上的局部最优选择。 当然，我们希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不是对所有问题都能得到整体最优解，但对范围相当广的许多问题它都能产生最优解。如单源最短路径问题，最小生成树问题等。 而且，在一些情况下，即使贪心算法不能得到整体最优解，但其最终结果却是最优解的很好的近似解！

3.1一般方法 贪心方法适合的问题：它有n个输入，而它的解就由这n个输入满足某些事先给定的约束条件的某个子集组成，而把满足约束条件的子集称为该问题的可行解。显然，可行解一般来说是不唯一的。那些使目标函数取极值(极大或极小)的可行解，称为最优解。 贪心方法是求解这一类需求取最优解的问题的一种直接 有效的方法。贪心方法是一种分级处理方法，它首先根据题 意，选取一种量度标准。然后按这种量度标准对这n个输入 排序，并按序一次输入一个量。如果这个输入量的加入，不 满足约束条件，则不把此输入加到这部分解中。

贪心方法的抽象化控制 算法3.1 procedure GREEDY(A，n) //A(1：n)包含n个输入// solutions←φ //将解向量solution初始化为空／ for i←1 to n do x←SELECT(A) if FEASIBLE(solution，x) then solutions←UNION(solution，x) endif repeat return(solution) end GREEDY 从算法3.1可看出，一旦能选择出某个问题的最优量度标准，那么用贪心方法求解这个问题则特别简单有效。

…… n个输入按某种量度标准排序 按序一次选择一个输入量。 满足约束条件，加入解 解 ….. 不满足约束条件，扬弃 对于一个给定的问题，往往可能有好几种量度标准。用其中的大多数量度标准作贪心处理所得到该量度意义下的最优解并不是问题的最优解，而是次优。 选择能产生问题最优解的最优量度标准是使用贪心法设计求解的核心问题。

3.2 背包问题 问题：已知有n种物品和一个可容纳M重量的背包，每种物品i的重量为wi。假定将物品i的一部分xi放入背包就会得到pixi的效益，这里，0≤xi≤1，pi>0。如果这些 物品重量的和大于M，要求所有选中要装入背包的物品总重 量不得超过M，而装入背包物品获得的总效益最大。即 0≤xi≤l，pi>0，wi>0，1≤i≤n 满足约束条件的任一集合(x1，…，xn)是一个可行解(即能装下)，使目标函数取最大值的可行解是最优解。

例3.1 n＝3，M=20，P＝(25，24，15)， (x1，x2，x3) ∑wixi ∑pixi ①(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 在这四个可行解中，第④个解的效益值最大。这个解是背 包问题在这一情况下的最优解。

例，n＝3，M=25，P＝(25，24，15)， W (18，15，10)。 X=(1) ∑p=25, CU=M-W(1)=7 不能放下任何物品，显然X=(1)不是最优解。 最优解是(2,3)，利润为39。

贪心策略与最优量度表 目标函数作为量度标准 这是最容易想到的，即每装入一件物品就使背包获得最大可能的效益值增量。在这种量度标准下的贪心方法就是按效益值的非增次序将物品一件件放到背包中去。如果正在考虑中的物品放不进去，则可只取其一部分来装满背包。第②个解就是这种量度标准下的贪心方法所产生的解，显然它不是最优的。原因在于背包可用容量消耗过快。 容量作为量度 让背包容量尽可能慢地被消耗。这就要求按物品重量的非降次序来把 物品放人背包。例3.1的解③就是使用这种贪心策略得到的，它仍不是最 优解。其原因在于容量虽然慢慢地被消耗，但效益值没能迅速地增加。 利润/重量为量度 即每一次装入的物品应使它占用的每一单位容量获得当前最大的单 位效益。这就需使物品的装人次序按pi/wi比值的非增次序来考虑。解④ 就是使用这种贪心策略得到的，它是最优解。

procedure KNAPSACK(P，W，M，X，n) //P(1：n)和W(1；n)分别含有按 算法3.2 背包问题的贪心算法 procedure 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

定理3.1 如果 p1/w1≥p2／w2≥…≥pn／wn，则算法 KNAPSACK对于给定的背包问题实例生 成一个最优解。 证明 设X=(x1，…，xn)是 KNAPSACK所生成的解。设j是使x(i)<>1的最小下标。由算 法可知，有：(1,….,1,0,…,0) j 如果X不是一个最优解，则必定存在一个可行解Y=(y1，…，yn)，使得∑piyi>∑pixi。不失一般性，可以假定∑wiyi=M。设k是使得yk<>xk的最小下标。可以推得yk<xk。这可从三种可能发生的情况，即k<j，k＝j或k>j分别得证明： ①若k<j， (1,1,1,….,1,0,…,0) 因为 yk<>xk ，从而yk<xk。 K j ②若k＝j， (1,1,1,….,1,0,…,0) 若yk>xk，显然有∑wiyi>M，从而yk<xk。 K=j ③若k>j， (1,1,1,….,1,0,…,0) 若yk>xk ，有∑wiyi>M，是不可能的。 j K

现在，假定把yk增加到xk，那末必须从(yk+1，…，yn)中减去同样多的量，使得所用的总容量仍是M。这导致一个新的解Z=( z1，…，zn)，其中， zi=xi，1≤i≤k，并且 变换 Z不比Y差，重复上面的讨论，把Y转换成X，从而证明了X也是最优解。证毕。

3.3 带有限期的作业排序 贪心设计策略来解决操作系统中单机、无资源约束且每个作业可在等量ti的时间内完成的作业调度问题。即，假定只能在一台机器上处理n个作业，每个作业均可在单位时间内完成，假定作业i有一个截止期限di>0(它是整数)，当且仅当作业i在它的期限截止以前被完成时，则获得pi>0的效益。这个问题的一个可行解是这n个作业的一个子集合J，J中的每个作业都能在各自的截止期限之前完成。可行解的效益值是J中这些作业的效益之和，即 。具有最大效益值的可行解就是最优解。 例3.2 n=4，(p1，p2，p3，p4)＝(100，10，15，20)和 (d1，d2，d3，d4)=(2，1，2，1)

解⑦是最优的，所允许的处理次序是：先处理作业4，再处 理作业1。 例3.2的可行解和它们的效益值如下： 可行解 处理顺序 效益值 ① (1) 1 100 ② (2) 1 10 ③ (3) 1 15 (4) 1 20 (1，2) 2，1 110 (1，3) 1，3或3，1 115 (1，4) 4，1 120 (2，3) 2，3 25 解⑦是最优的，所允许的处理次序是：先处理作业4，再处 理作业1。 4 1

选择下一个作业的量度标准 得到最大增加的作业。这就要求按pi 的非增次序来考虑这些作业。利用例3.2中的数据来应用这一准则: 把目标函数 作为量度。使用这一量度，下一个要计入的作业将是使得在满足所产生的J是一个可行解的限制条件下让 得到最大增加的作业。这就要求按pi 的非增次序来考虑这些作业。利用例3.2中的数据来应用这一准则: 开始时 J＝φ， ， J＝{1}， p1=100 作业1有最大效益 J＝{1，4} p1+p4=120 作业4有第二大效益 作业3，2都被舍弃 。

算法3.3 作业排序算法的概略描述 procedure GREEDY-JOB(D，J，n) //作业按p1≥p2≥…≥pn的次序输入，它们的期限值D(i)≥1，1≤i≤n，n≥1。J是在它们的截止期限前完成的作业的集合// 1 J←{1} 2 for I←2 to n do 3 if J∪{i}的所有作业都能在它们的截止期限前完成 then J←J∪{i} 4 endif 5 repeat end GREEDY-JOB

定理3.2 算法3.3所描述的贪心方法对于作业排序问题总是得到一个最优解。 定理3.2 算法3.3所描述的贪心方法对于作业排序问题总是得到一个最优解。 证明 设(pi，di)，1≤i≤n，是作业排序问题的任一实例；J是由贪心方法所选择的作业的集合；I是一个最优解的作 业集合。可证明J和I具有相同的效益值，从而J也是最优的。 假定 I≠J，因此，至少存在着这样的两个作业a和b，使得 且 ，b∈I且 。由贪心方法可以得出，对于在I中 又不在J中的所有作业b，都有pa≥pb。这是因为若pb >pa，则 贪心方法会先于作业a考虑作业b并且把b计人到J中去。 ……… ……… a t pa≥pb ……… ……… b

现在，设SJ和SI分别是J和I的可行调度表。设i是既属于J又属于I的一个作业；又设i在SJ中在t到t+1时刻被调度，而在SI中则在t’到t’+1时刻被调度。可以调换SJ 或SI中的作业，使i在SJ和SI中都在同一时刻被安排。如果t<t’，交换SJ中的i与j; ……… i ……… j t t ……… ……… i b t’ 如果t>t’，交换SI中的i与j;重复使用，可使SJ和SI中都有的作业在相同的时刻被安排。 ……… ……… j t t ……… ……… j i j t’

下面考虑SJ与SI中的不同作业a,b，设a在[ta，ta+1]时刻被安排，设作业b在SI中的这一时刻被调度。根据对a的选择，pa≥pb。在SI去掉作业b而去调度作业a，这就给出了一张关于作业集合I’=I一{b}∪{a}可行的调度表。显然I’的效益值不小于I的效益值，并且I’比I少一个与J不同的作业。重复使用上述的转换，将使I能在不减效益值的情况下转换成J，因此J也必定是最优解。证毕。 用J中的作业a替换I中的作业b,得到新的作业集I’。 ……… ……… a t pa≥pb ……… ……… b

if J∪{i}的所有作业都能在它们的截止 期限前完成 then J←J∪{i} 下面对算法3.3的第3条语句进一步细化。 if J∪{i}的所有作业都能在它们的截止 期限前完成 then J←J∪{i} 实现语句3，一个明显的方法是检验J中作业的所有可能的排列，假定J中有k个作业，这就需要检查k!个 排列。事实上，对于J的可行性可以通过只检验J中作业的一 种特殊的排列来确定，这个排列是按期限的非降次序来完成 的。即将J中的K个作业按di1≤di2≤…≤dik 排列，作业i能 否加入J的充要条件是，作业i能否加入这个序列。 i ……… ……… k

作业已计人J(1)，J(2)，…，J(k)之中， 且有D(J(1))≤D(J(2))≤…≤D(J(k))，现在 假设已处理了I-1个作业，其中有k个 作业已计人J(1)，J(2)，…，J(k)之中， 且有D(J(1))≤D(J(2))≤…≤D(J(k))，现在 处理作业i。为了判断JU{i}是否可行，只需 看能否找出按期限的非降次序插入作业i的 适当位置r，使得作业i在此处插入后有 D(J(r))≥r，1≤r≤k+1。 D(J(r))≤D(i)，作业i应该放在r+1处 D(i)〉r，作业i可以放在r+1处， 从r+1到k的作业应向后移动。 i ……… ……… r k

找作业i可能的插入位置可如下进行：将 D(J(k))，D(J(k一1))，…，D(J(1))逐个与D(i)比较，直到找到位置r，它使得D(J(r))≤D(i)，只要D(i) >r，就可将作业I 在位置r+1处插入，从而得到一个按期限的非降次序排列的含有k+1个作业的可行解。以上过程可反复进行到对第n个作业处理完毕，所得到的贪心解是一个最优解。这一处理过程可用算法3.3来描述。算法中引进了一个虚构的作业0，它放在J(0)，且D(J(0))＝0。引入这一虚构作业是为了便于将作业插入位置1。

算法3.4 带有限期和效益的单位时间的作业排序贪心算法 算法3.4 带有限期和效益的单位时间的作业排序贪心算法 procedure JS(D，J，n，k) //D(1)，…，D(n)是期限值。n≥1。作业已按 p1≥p2≥…pa被排序。J(ri)是最优解中的第r个作业，1≤r≤k。终止时，D(J(r)≤D(J(r+1))，1≤r<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 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 l←k to r+1 by-l do J(I+1) ←J(l) repeat J(r+1)←i；k←k+1 endif repeat end JS

例n=4，P＝(1 00，20， 15， 10，)和 D=(2，1，2，1) J(1)=1,k=1 1 2. i=2, r=1 , 因为 D(J(r))=2>D(i) 所 以 r=r-1=1 D(J(r))=1〉D(i) 且， D(J(r))≠r 可以后移。 又因为，D(i) 〉r i可以插入 J(1)=1,k=1 J={1, 2} 1 2 3. I =3,r=k=2, D(J(r))=2=D(i) 且 D(J(r))=r 不可以后移 又因为，D(i) =r i不可以插入。 4. I =4, r=k=2, D(J(r))=2<D(i) 不可以后移 又因为，D(i)<r i不可以插入。

复杂度分析 对于JS，其复杂度参数有两个：即作业数n和包含在解中的作业数s. 6-8行：循环至多迭代k次，每次的时间为O（1）。因此O（k) 10-13: 若第9行的条件为真，则执行，时间O（k-r)去插入作业I 4-15：每次迭代的总时间为O（k),若s是 k的终值，即s是最后所得解的作业数。则JS所需的总时间是O（sn)。由于s<=n，因此最坏时间是O（n2) (当 p1=d1=n-i+1 时出现），所以最坏时间是：

一种更快的作业排序算法 通过使用不相交集合的UNION和FIND(即集合合并和查找树),可以将JS的计算时间由O(n2)降低到数量级相当接近于O(n) 主要思想:如果J是作业的可行子集,那末以可以按如下规则来确定这些作业中的每一个作业的处理时间:若还没给作业I分配处理时间,则分配给它时间片[a-1,a],其中a应尽量取大且时间片[a-1,a]是空的（如果没有这样的时间片[a-1,a]可分配，则作业不不能计入J）。此规则就是尽可能推迟对作业的的处理。于是，在将作业一个一个地装配互J中时，就不必为接纳新作业而去移动J中那些已分配了时间片的作业。

由于只有n个作业且每个作业花费一个单位时间,因此只需考虑这样一些时间片[i-1,i], ) 例3.3 设n=5, (p1,p2,…,p5)=(20,15,10,5,1)和（d1,d2,…,d5)=(2,2,1,3,3) 使用上述可行性规则，得： J 已分配的时间 正被考虑的作业 动作 无 1 分配[1,2] {1} [1,2] 2 分配[0,1] {1,2} [0,1],[1,2] 3 舍弃 {1,2} [0,1],[1,2] 4 分配[2,3] {1,2,4} [0,1],[1,2] ,[2,3] 5 舍弃 所以,最优解是J={1,2,4}.. 由于只有n个作业且每个作业花费一个单位时间,因此只需考虑这样一些时间片[i-1,i], )

3.4最优归并模式 前面已介绍将两分别有n个记录和m个记录的已分类文件可以在O(n+m)时间内归并成一个已分类文件。但现在假定X1，X2，X3，X4，X5是需要归并，从而得到想要的归并文件。-如何归并？（注意：归并需要移动记录—归并的代价， 移动记录总量最少的归并方法为最优归并—代价最小 5个文件（F1，F2，…,F5) 95 35 5 10 15 20 30 60 归并树 F4 F3 F1 F5 F2 di– 文件Fi到根的距离 qj– Fj的长度 记录移动总量:

生成二元归并对算法 P77 算法3.6 二元归并树生成算法 Procedure TREE(L,n) //L是n个单结点的二元树的表// 算法3.6 二元归并树生成算法 Procedure TREE(L,n) //L是n个单结点的二元树的表// 1 for i←1 to n-1 do 2 call getnode(T) //生成一个结点T，用于归并两棵树// 3 Lchild(T) ←LEAST(L) 4 Rchild(T) ←LEAST(L) 5 Weight(T) ←WEIGHT(Lchild(T))+WEIGHT(Rchild(T) ) 6 call INSERT(L,T) 7 repeat 8 return (LEAST(L)) 9 end TREE 图3.3 TREE 工作过程 P77

3.5 最小生成树 1. 网络的最小生成树在实际中有广泛应用.例如:在设计通信网络时,用图的顶点表示城市,用边的权表示建立城市之间的通信线路所需的费用,则最小生成树就给出了建立通信网络的最经济的方案。 2.最小生成树性质 设G=(V,E)是一个连通图,U是V的一个真子集.如果(u,v) ∈E,且u ∈U, v ∈V-U,且在所有的这些边中,(u,v)的权最小,那么一定存在G的一棵生成树,它以(u,v)为其中一条边。-----这个性质也称为MST性质。

Prim算法 获得最小（成本）生成树的贪心算法应该是一条边一条边地构造这棵树。根据某种最度标准来选择将要计入的下一条边。最简单的最度标准是：选择使得迄今为止所计入的那些边的权值的各有最小增量的那条边。 这一量度标准在两种解释：第一种方法使得迄今所选择的边的集合A构成一棵树，将要计入到A中的下一条边（u,v)是一条不在A中且使得A∪{（u,v)}也是一棵树的最小成本的边。其相应的算法称为PRIM算法。 算法主要思想：参看P79 图3.7 Prim 方法的运行实例图 。

算法说明 1。PRIM算法是在只计入了G中一条最小成本的边开始时的,然后一条边一条边地加进这棵树中.所要加入的下一条边(i,j)满足:i是已计入到这棵树的一个结点,j是还没有计入的一个结点,而(i,j)的成本是所有这样的边(k,l)的成本的最小值。K在这棵树中，l 不在这棵树中。 2。为了求出这条边（i,j), 把还没计入这棵树的每一个结点j和NEAR(j)联系起来。 NEAR(j) 是树中的结点，并且使得COST（j,NEAR(j))是对NEAR（j)所有选择中的最小值。 若j已在树中，则NEAR(j)=0,用NRAR（j) ≠0(即j还不在树中，且COST（j,NEAR(j))为最小值的结点来计入下一条边。

Procedure PRIM(E,COST,n,T,mincost) real COST(n,n),mincost; integer NEAR(n),n,I,j,k,l,T(1:n-1,2); (k,l) ←具有最小成本的边 O（e) mincost ←cost(k,l) (T(1,1),T(1,2)) ←(k,l) for i ←1 to n do // 将NEAR置初值// O(n) if COST(i,l)<COST(i,k) then NEAR(i) ←l else NEAR(i) ←k endif repeat NEAR(k) ←NEAR(l) ←0 For i ←2 to n-1 do //找T的其余n-2条边// O(n) 设j是NEAR(j) ≠0且COST(j,NEAR(j))最小的点 O(n) mincost ←mincost+COST(j,NEAR(j)) NEAR(j) ←0 for k ←1 to n do //修改NEAR// O(n) if NEAR(k) ≠0 and COST(k,NEAR(k))>COST(k,j) then NEAR(k) ←j endif Repeat If mincost≥∝ then print(‘no spanning tree’)endif End PRIM

PRIM算法复杂度分析 O(n2) Procedure PRIM(E,COST,n,T,mincost) real COST(n,n),mincost; integer NEAR(n),n,I,j,k,l,T(1:n-1,2); (k,l) ←具有最小成本的边 O（e) mincost ←cost(k,l) (T(1,1),T(1,2)) ←(k,l) for i ←1 to n do // 将NEAR置初值// O(n) if COST(i,l)<COST(i,k) then NEAR(i) ←l else NEAR(i) ←k endif repeat NEAR(k) ←NEAR(l) ←0 For i ←2 to n-1 do //找T的其余n-2条边// O(n) 设j是NEAR(j) ≠0且COST(j,NEAR(j))最小的点 O(n) mincost ←mincost+COST(j,NEAR(j)) NEAR(j) ←0 for k ←1 to n do //修改NEAR// O(n) if NEAR(k) ≠0 and COST(k,NEAR(k))>COST(k,j) then NEAR(k) ←j endif Repeat If mincost≥∝ then print(‘no spanning tree’)endif End PRIM O(n2)

Kruskal算法粗略描述 1。将图中所有的边按权值递的方式排序。{e1,e2,…..em} 2。T= 3。For i=1 to m do if T∪{ei} 不会产生圈 T= T∪{ei}

Kruskal算法详细描述 1。Sort the edges in increasing order: {e1,e2,…..em} 2. F={{v1},{v2},…,{vn}} 3. T= 4. For i=1 to m do ei={ui,vi} if ui and vi belongs to differrent pieces in F T= T= T∪{ei}

Kruskal算法进一步详细描述 1. For each vertex vi do make{vi} a piece 2. T= 3. Sort the edges in increasing order: {e1,e2,…..em} 4. For i=1 to m do ei=[ui,vi] if ui and vi belongs to differrent pieces in Su and Sv then T= T= T∪{ei} merge Su and Sv into a single piece. lecture3(KRUSKAL算法）.ppt

算法3.9 Kruskal算法—P83 procedure KRUSKAL(E,COST,n,T,mincost) Real mincost,COST(1:n,1:n) Integer PARENT(1:n),T(1:n-1,2),n 以边为成本构造一个min堆 PARENT←-1 I ←minost ←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’) Return End KRUSKAL 上机作业:给定一个图,求出其最小生成树)

贪心算法的基本要素 贪心算法通过一系列的选择来得到一个问题的解.它所作的每一步选择过日子是当前是状态下的某种意义地最好选择,即贪心选择.希望通过每次所作的贪心选择导致最终结果是问题的一个最优解.这种启发式的策略并不总能奏效，然而在许多情况下确实能达到预期的目的。 对于一个具体的问题，我们怎么知道是否可用贪心算法求解呢？--很难回答。但是，从许多可以用贪心算法求解的问题中可以看到它们一般具有两个重要的性质： 贪心选择性质和最优子结构性质。

贪心选择性质 所谓贪心选择性质是指所求问题的整体最优解可以通过局部最优的选择，即贪心选择达到。这是贪心算法可行的第一个基本要素。 贪心算法所作的选择可以依赖于以往作过的选择，但决不依赖于将来所作的选择，也不依赖于子问题的解。所以贪心算法以自项向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为一个规模更小的子问题。 对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的一个整体最优解。------如何证明？ 首先考察问题的一个整体最优解，并证明可修改这个最优解，使其贪心选择开始。而且作了贪心选择后，原问题简化为一个规模更小的类似子问题。然后，用数学归纳法证明，通过每一步作贪心选择，最终可得到问题的一个整体最优解。其中，证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。

最优子结构性质 当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构性质。这是问题能用贪心算法求解地一个关键特征。

贪心法总结 适合用贪心法的问题应具有最优子结构性质：原问题的最优解包含了其子问题的最优解。 例如背包问题，原问题的最优解是在背包的容积的限定下利润达到最大，实际上是一个单位容积利润最大的问题。它包含子问题的最优。 带限期的作业调度，是在限期的约束下，利润最大。子 问题得最优符合这一原则。 但不是所有的问题都能找到贪心算法。例如，0/1背包问 题，即在背包问题多了一个限制：xi{0,1}，物品i不能拆 开。