计算机算法基础 第2版 课件 第7章 贪心算法

1第7

章

贪心算法算法概述

2最佳邮局设置问题

3一个简单的最佳活动安排问题

7其它最佳活动安排问题

12

两个大礼堂的最佳活动安排问题

13

等长时间的活动的最佳安排问题

21哈夫曼编码问题

29最佳加油计划问题

441.算法概述

是又一个从解决小规模问题开始，逐步解决大规模问题的方法。贪心算法通常只发展一个解，而不是一组解。初始解也许是一个小规模问题的最优解，也可能是一个大规模问题的最原始的、粗略的、不完整的、非最优的解。贪心算法每前进一步，就把当前的解变为一个稍大规模问题的最优解，或把解变为一个更好、更完整、更优的解。算法结束时，得到一个最初大规模问题的一个最优解，或者一个相当好的近似解。这一章所讨论的例子都产生最优的结果。23问题定义设东西方向的街上有n

户人家，它们与街西头的距离是：

H[1]<H[2]<H[3]<…<H[n]街上无邮局。现在，要建一些邮局使得任一户人家到最近一个邮局的距离不超过100米。请设计一个O(n)的算法以确定最少需要建多少邮局，和每个邮局到街西头的距离。解：这个题用分治法和动态规划都不太方便。如果我们把序列H[1..n]分为两段，那么，合并时，两个子问题的解是不能改动的。分治法和动态规划都不允许改动子问题的解。但是，不改动子问题的解，很难保证合并后的解是最佳的。这使得递归地分割和归纳地定义子问题都产生困难。(接下页)2.最佳邮局设置问题4最佳邮局设置问题(继续1)贪心法的思路：先确定如何走第一步，即确定第一个邮局的位置P[1]。直观上看，为了使邮局数最小，应尽量使P[1]距街西头远一些。但是，因为要使得第一户人家到它的距离不超过100米，因此，P[1]

H[1]+100。那么P[1]=H[1]+100是不是正确的决定呢？贪心法通常需要证明第一步正确，然后用归纳法证明每一步都正确，而证明中往往使用反证法。让我们用反证法证明，有最优解把第一个邮局设在P[1]

=H[1]+100。如果没有，取一个最优解。它不把第一个邮局设在P[1]，而是设在距街西头x米处，那么必有x

<H[1]+100。让我们来比较一下。(接下页)5P[1]=H[1]+100H[1]

xx+100P[1]+100设在x的邮局的复盖范围设在P[1]的邮局的复盖范围最佳邮局设置问题(继续2)由下图可见，所有能在x处得到服务的住户都可以在P[1]=H[1]+100处的邮局得到服务。因此把第一个邮局建在P[1]处总是正确的。这就证明了第一步是正确的。在P[1]确定后，确定P[2]的位置。这时，被P[1]复盖的住户可以不考虑。如果在P[1]+100米外还有人家，则可重复这一过程确定P[2]、P[3]、…。算法伪码见下页6Post-office(P,H,m,n) //m是邮局个数P[1]

H[1]+100 m

1 //目前为止，建了第m(=1)个邮局

for

i

2ton //贪心法逐个察看住户位置

if

H[i]>P[m]+100 //它不在第m个邮局服务区间内

then

m

m+1 //必须再建一个新邮局 P[m]

H[i]+100

endifendforif

P[m]>H[n]

thenP[m]

H[n]

//使最后一个邮局不超过H[n]endifreturnP,m

End显然这个算法复杂度为

O(n)。73.一个简单的最佳活动安排问题问题定义n

个活动a1,a2,…,an

申请使用大礼堂。ai

(1

i

n)有固定的开始时间si和完成时间fi

(0

si<fi<

)。一旦ai被选中，ai在时间区间[si,fi)里独占大礼堂。礼堂从t

=0开始可安排活动，但任何时候允许最多一个话动。

ai

和aj

称为兼容，如果[si,fi)和[sj,fj)不相交，即要么fi

sj，要么fj

si。最佳活动安排问题：从这n

个活动中选出一个两两兼容的最大子集，使得尽可能多的活动在大礼堂进行。8例7.1 假定我们有以下10个活动申请使用大礼堂。i12345678910si01031376910fi24578910111314如果选出{a1,a6,a9}，它们是兼容的，但不是最优的。最优解可以安排4个活动。0239a1a6a91302310a1a4a10147a7一个非最优解一个最优解9解题思路如何选取第一个活动？选开始时间最早的活动？这个设想可立即被反例否定。选完成时间最早的活动？完全正确！定理7.1

给定n

个活动a1,a2,…,an，完成时间最早的活动一定包含在某个最优解中。证明：设am的时间fm最早。取最优解S。假设S含有am，证明完成。否则，设S中完成时间最早的活动为ak

am。我们有fm

≤fk。因为S中其他活动与ak兼容，他们的开始时间大于等于fk，因而也大于等于fm。所以S中其他活动与am也兼容。因此，集合S’=S

{am}–{ak}也是一个最优解且包含am。

10算法伪码：先按完成时间排序为F[1]

F[2]…

F[n](F[i]=fi，S[i]=si)。选a1后，与a1不兼容的不取，用同法在所余活动中选取。Greedy-Activity-Selection(S[1..n],F[1..n]，A)A

{a1} //a1是第一个中选的活动i

1

//

ai是当前为止，最后选中的一个活动for

k

2to

n

if

S[k]

F[i]

//若S[k]<

F[i]，则ak与ai不兼容

then

A

A

{ak}

i

k

//ak成为当前最后选中的活动

endifendforreturnAEnd 算法复杂度是O(n)，加上排序是O(nlgn)。11例7.1的解(图7-4)124.其它最佳活动安排问题实践中还有很多其它最佳活动安排问题。很多处理器的调度问题和活动安排有相同的本质。这一节再讨论两个活动安排问题。两个大礼堂的最佳活动安排问题等长时间的活动的最佳安排问题它们在证明技巧上用了相同的方法，希望读者能欣赏和掌握这个方法。13两个大礼堂的最佳活动安排问题：假设有n

个活动

a1，a2，…,an申请使用大礼堂。ai(1

i

n)有一个固定的开始时间

si和固定的完成时间

fi

(0

si<fi<

)。我们有两个礼堂，H-1和H-2，都从t=0开始可供使用。安排在同一礼堂的活动必须两两兼容。请设计一个O(nlgn)的贪心算法，找出最佳的活动选择计划使得被安排的活动数最多。(类似地，可定义

k个礼堂问题。)贪心法思路：与一个礼堂的问题相同。先把n个活动按完成时间排序，使

f1

f2

…

fn。然后从第一个活动开始，逐个检查，并作出决定是否选取。如果选取，安排在哪个礼堂？(接下页)14两个大礼堂的最佳活动安排问题

(继续)具体做法：用变量Available-Time-1记录礼堂H-1目前的可用时刻。用变量Available-Time-2记录礼堂H-2目前的可用时刻。开始时，Available-Time-1=Available-Time-2=0。对每个活动ai(1

i

n)，逐个作出决定的规则如下：(假设Available-Time-1

Available-Time-2，否则对称处理。)如果Available-Time-1

si，那么把ai安排在H-1，并更新Available-Time-1为

fi。如果Available-Time-2

si<Available-Time-1，那么把ai安排在H-2，并更新Available-Time-2为

fi。如果si<Available-Time-2，则丢弃不安排。(伪码见下页)15Two-hall-schedule(S[1..n],F[1..n],A1,A2)

//A1和A2是安排在H-1和H-2中活动的集合

Available-Time-1

Available-Time-2

0A1

A2

Sortai(1

i

n)suchthatF[1]

F[2]

…

F[n] for

i

1to

n

ifAvailable-Time-1

Available-Time-2

thenif

Available-Time-1

S[i]

then

A1

A1

{ai}

Available-Time-1

F[i]

else

if

Available-Time-2

S[i]

then

A2

A2

{ai}

Available-Time-2

F[i]

endif

endif(接下页)

16Two-hall-schedule(继续) elseif

Available-Time-2

S[i]

//Available-Time-1<Available-Time-2

then

A2

A2

{ai}

Available-Time-2

F[i]

else

if

Available-Time-1

S[i]

then

A1

A1

{ai}

Available-Time-1

F[i]

endif

endifendifendforEnd排序需要O(nlgn)时间。后面逐个处理活动时，每次只需O(1)时间，所以算法复杂度是O(nlgn)。下面证明它得到的解最优。17定理7.2

对任何一个序号

i(i=1,2,…,n)，总存在一个最优解，它对前面i个活动的处理和算法对这

i个活动的处理完全一样。因此，存在一个和算法得到的解完全相同的最优解。证明：我们对序号i(i=1,2,…,n)进行归纳证明。归纳基础：当

i

=1时，算法必定把a1安排在H-1中。我们分析两种情况：如果a1不被某最优解M选中，假设ak

(k>1)是解M中在H-1有最小完成时间的活动。我们可用a1换走ak，解仍然最优。如果最优解M选中了a1但安排在H-2中，我们可以把H-1中的所有活动与H-2中的所有活动交换，解仍然最优且a1在H-1中。因此，当

i

=1时，定理7.2正确。

归纳步骤：(接下页)18定理7.2证明(继续1)假设到第i步为止，有一最优解M，它对a1到ai的处理与算法完全一样。下面证明，存在一个最优解，它对a1到ai+1

的处理与算法完全一样。我们分析三种情况。(1)S[i+1]<min{Available-Time-1，Available-Time-2}这种情况，M不可能选ai+1，它必与算法一样，拒绝ai+1。(2) Available-Time-2

S[i+1]<Available-Time-1

(对称情况为Available-Time-1

S[i+1]<Available-Time-2)这时，解M不可能安排ai+1到H-1。如果M拒绝ai+1，而在H-2中下一个结束最早的活动是ak，k>i+1，那么，我们在M的基础上用ai+1换走ak。因为F[i+1]

F[k]，这个交换可行。得的解含有与M一样多的活动。所以，存在一个最优解，它对a1到ai+1

的处理与算法完全一样。（H-2中必有下一个活动，否则更可以安排ai+1。）(接下页)19定理7.2证明(继续2)(3) S[i+1]

Available-Time-1

Available-Time-2

(对称情况为S[i+1]

Available-Time-2

Available-Time-1)这时，如解M根本不取ai+1，而在H-1中下一个结束最早的活动是ak，那么，我们用ai+1换走ak所得的解仍然最优。如果解M取ai+1，但安排在H-2，那么如图，解M在每个礼堂中活动可以用Available-Time-1为界分为不相交的两个集合。所以，我们可以把Available-Time-1之后在两个礼堂安排的所有活动互相交換。得到的解仍然最优且ai+1在H-1中。所以，在这种情况下，也有一个最优解，它对a1到ai+1的处理与算法完全一样。对称情况同理可证。归纳成功，定理7.2得证。

(图在下页)20结论：算法Two-hall-schedule正确解决两个礼堂的最佳活动安排问题21等长时间的活动的最佳安排问题：有n

个活动a1，a2，…,an申请使用同一个大礼堂。时间划分为等长的间隔

t，称为时隙，假设

t=1小时。

slot(t)，t

=1,2,3,…表示时隙序列。每个小时只能安排一个活动或不安排活动。每个活动

ai

(1

i

n)都是申请用礼堂一个小时。每个ai有区间[si,fi]，si和fi

是正整数(si

fi)，称为开始时隙和终止时隙。

活动ai可安排在区间中任一时隙slot(t)，t

[si,fi]。礼堂从t=1可以使用。问题：设计一个O(n2)贪心算法以安排最多的活动。

为简单起见，假定这n个活动已按终止时隙排序，

F[1]≤F[2]≤…≤F[n]。22贪心法思路：因为F[1]≤F[2]≤…≤F[n]，序列中后面的活动有较大的终止时隙，所以当我们顺序安排a1，a2，…，

an

时，尽量把活动往前面的时隙安排。具体做法是，在我们安排ai(1

i

n)时，从si

到fi，顺序检查每个时隙，一旦发现有某个时隙还没有人用，则马上把

ai安排到这个小时。我们可以证明这个思路是正确的。这里，有个复杂度的问题。如果(fi

-si)>>n，那么为ai搜索的时间是否会大于n？不会，这是因为，前面一共处理了(i-1)个活动，它们最多占用(i-1)个小时，所以我们最多需要检查n个时隙就一定可以成功地为ai申请到一个时隙。这就保证了算法复杂度为O(n2)。(伪码见下页)23Max-Activities-Fixed-Length(S[1..n],F[1..n],A,T[1..n],k) //H是选中的活动集合，A是为活动安排的时隙，k=|A|A

fori

1to

n

T[i]

nil //初始化，无时隙分配给ai，记为nil fort

S[i]to(S[i]+n)

//避免F[i]过大

slot[t]

nil //所有可能被查的时隙t都初始化为空endfork

0for

i

1to

n

//顺序处理活动ai t

S[i] //从S[i]开始检查 whileslot[t]≠niland

t≤F[i] //不需担心F[i]过大

t

t+1

endwhile(接下页)24Max-Activities-Fixed-Length

(继续)

if

t≤F[i] //t是第一个空闲的时隙

then

A

A

{ai} //ai

被选中 slot[t]

i //时隙t被ai占了

T[i]

t

//把时隙t分配给ai k

k+1 //选中的活动数加1

endifendforreturnA,T,kEnd

算法复杂度显然是O(n2)定理7.3

对任一序号i(i=1,2,…,n)，存在一个最优解，它对前面i个活动的处理和我们的算法完全一样。因此，存在一个最优解和我们的算法得到的解完全相同。(证明见下页)25定理7.3

证明：我们对序号i(i=1,2,…,n)进行归纳证明。归纳基础：i

=1时，算法把

a1

安排在t=S[1]。取一最优解M。如果M也把a1

安排在

S[1]，定理得证。否则，分析以下4种情况：解M拒绝a1，并且没有活动被安排在S[1]。对这种情况，我们在解M的基础上，把a1安排在S[1]。这样会得到一个更优的结果，与解M最优矛盾。(B) 解M拒绝a1，并把ak（k>1）安排在S[1]。对这种情况，我们把ak

换成a1。这样得到的解也是一个最优解，而且把a1安排在S[1]，与算法一致，定理得证。(接下页)26定理7.3

证明(继续1)(C) 解M安排a1在

u>S[1]。并且，无活动安排在S[1]。对这种情况，我们把a1重新安排到t=S[1]。得到的解也是最优解，而且把a1安排在S[1]，与我们的算法一致，定理得证。(D) 解M安排a1在u

>S[1]。并且安排ak（k>1）在S[1]。对这种情况，必有u

F[1]，和S[k]

S[1]。我们可把a1和ak对调。因为S[k]

S[1]<u

F[1]

F[k]，对调是合理的。我们得到一个最优解把a1安排在S[1]，与我们的算法一致。所以i

=1时，定理正确。归纳步骤：假设

i=1,2,3,…,k(k

1)时，存在最优解，它对前面i个活动的处理和算法完全一样。现在证明，当i=k+1时，定理也正确。设M是在i=k时与我们算法一致的最优解。(接下页)27定理7.3

证明(继续2)如果从t=S[i+1]到t=F[i+1]的每一个时隙都已被前面的活动占用，那么，最优解M和我们的算法都必须拒绝ak+1，定理得证。所以假设w是从S[i+1]到t=F[i+1]之间第一个空闲的时隙。我们的算法把ak+1安排在

w。如果解M也把ak+1安排在

w，证明就完成了。所以，假定M没有把ak+1安排在t=w。我们分析以下4种情况。(A)解M拒绝ak+1，并且没有活动被安排在t=w。对这种情况，我们在M的基础上，把ak+1安排在w。这样会得到一个更优的结果，与解M最优矛盾。(B) 解M拒绝ak+1，并把活动ap（p>k+1）安排在t=w。对这种情况，在M的基础上，把ap

换成ak+1。这样得到的解也是一个最优解，而且把ak+1安排在

w，与我们的算法一致。(接下页)28定理7.3

证明(继续3)(C）解M接收ak+1，但安排在

u>w，并且，无活动安排在

w。对这种情况，在M的基础上，我们把ak+1重新安排到t=w。这样得到的解与M有完全相同的活动集合，而且把ak+1安排在

w，与我们的算法一致，命题得证。(D) 解M接收ak+1但安排在u>w，并安排ap（p>k+1）在w。对这种情况，必有u

F[k+1]和S[p]

w。我们可在M的基础上，把ak+1和ap对调。因为S[p]

w<u

F[k+1]

F[p]，所以对调是合理的。对调使我们得到另一个最优解，它与最优解M选取完全相同的活动集合。而且，这个最优解把ak+1安排在w，与我们的算法一致。归纳成功。定理7.3得证。

结论：算法正确解决了等长时间的活动的最佳安排问题。29前缀码介绍不同符号在报文中出现的频率不一样，如字母e出现频率很高而z则很少出现。所以考虑用变长码。用较短的码字为频率高的符号编码，用较长的码字为不常出现的符号编码，会使整个文件所用比特数减少。为使接收方能正确解码，必须是前缀码，即任一个码字不能是另一个码字的前缀。反例：如字母A、B、C编为A=0，B

=1，C

=01，那么序列0101应解码为ABAB?，ABC?，CAB?

还是CC?为了避免二义性，必须使用前缀码。5.哈夫曼编码问题30前缀码与完全二叉树的关系从一棵有

n个树叶的完全二叉树可构造一个n个字符的前缀码。让每个叶子对应一个字符。每个内结点到左右儿子的边分别标以0和1。根到每个叶子的路径上，每条边上的0和1形成的序列就是该叶子对应的字符的前缀码。这棵树称为前缀码树。这是因为，每条路径都不是另一条的一部分。31反之，从n个字符的前缀码，可找出对应的前缀码树。例：A

=01，B=001，C=000，D=110，E=10，F=111。如下找出对应的前缀码树。32

33引理7.4

假设a和b是所有字符中频率最小的二个字符，那么存在一个最佳前缀码树使得它们对应的叶结点在最底层，并有共同的父结点。证明：设T是最佳前缀码树，高度为h，而

a对应的叶结点在第k层，k<h。如下图所示，因为T是完全二又树，必定有字符x,x

b，对应于一个最底层的叶子。我们有d(x)=h。如果我们把a和x在T中交換一下，会得到一个新的前缀码树，T’。(接下页)34引理7.4证明(继续)我们有以下计算：B(T’)=B(T)-(kf(a)+hf(x))+(kf(x)+hf(a))=B(T)–h(f(x)-

f(a))+k(f(x)-

f(a))=B(T)-(h-k)(f(x)-

f(a))因为k<h，

f(a)≤f(x)，所以B(T’)≤B(T)。如果B(T’)<B(T)，则产生矛盾，所以有B(T’)=B(T)，说明T’也是最佳前缀码树，且a在底层。同理可证b也在底层。现在，假设与a共一父结点的字符是y。如果b=y，那么引理得证。否则把b和x交换以使a和b共一父结点。因为a，b，y都在底层，交换不改变B(T)值，定理得证。

35哈夫曼编码简介贪心法的第一步：如下图所示，贪心法的第一步是构造只有两个叶子的树，并让这两个叶子对应两个权值(频率)最小的字符a和b。由引理7.2知，这是正确的。ab贪心法如何继续？研究一下a和b与他们父结点p的关系。假设T是含上面这棵小树的字符集S的最优前缀码树，由(7.1)式，我们有：(接下页)p36

37哈夫曼编码简介(继续2)由上面讨论知，在贪心法走了第一步之后，下面应当构造集合S’的最佳前缀码。然后把a和b接到它们的父亲p即可。实际做法是，把a和b先接到p。把p为根的整个树对应到一个字符p。当需要把结点p与其它结点相联时，则把整棵树随着p与其它结点相联即可。所以，贪心法每一步选两棵权值最小的树A和树B相联。它们的父亲P是一个新的结点，以P为根的树的权值是树A和树B的权值之和。它对应一个新符号P，其权值(频率)是树A和树B的权值之和，或等价地说，是它们对应的符号A和符号B的权值(频率)之和。一开始，n个字符对应n棵初始树，每棵初始树只有一个结点，没有儿子，定义为树叶，它的权值就是对应字符的权值(频率)。38算法伪码Huffman(S,f) //输入是字符集S以及字符的频率n

|S|Q

S

//优先队列Q中每个元素指向一棵初始树。Q可用最小堆fori

1to

n-1

a

Extract-Min(Q) //取出有最小权值(频率)的树a

b

Extract-Min(Q) //取出第2小频率的树b Constructrootp //先构造含一个内结点的树

left

(p)

treea //树a成为p的左儿子

righ(p)

treeb //树b成为p的右儿子

f(p)

f(a)+f(b)

//以p为根的树的权值是树a和树b的权值之和

insert(Q,p) //以f(p)为关键字，把指向p为根的树的指针加到Q中endforT

Extract-Min(Q) //Q中只含一棵树End

//算法复杂度显然是O(nlgn)。39定理7.6

哈夫曼算法Huffman(S,f)产生一个关於集合S的最佳前缀码树。证明：

其实，前面已讨论了。我们用归纳法再正式证明一下。归纳基础：当S只有二个字符a和b时，该算法显然正确。归纳步骤：假设当S有n-1个字符时(n

3)，该算法正确。我们证明，当S有n个字符时，算法仍然正确。初始化后，算法其实只做一件事，就是执行第5行起的for循环。该循环的第一轮产生一个以p为根、以树a和树b为子树的二叉树。这里，树a和树b对应频率最小的两个字符。在循环的第二轮开始时，我们观察到以下两点：优先队列Q刪去了指向树a和树b的指针。增加了指向p为根的树，其权值为f(p)=f(a)+f(b)。我们可认为p为根的树对应一个字符p，其频率是f(p)。(接下页)40定理7.6

证明继续所以，for循环第二轮开始时，优先队列Q指向n-1个树。这些树对应的符号正好是集合S’=S

{p}–{a,b}中n-1个字符。而且，这n-1个树的权值也正好是它们对应的S’中字符的权值(频率)。由归纳假设，从循环的第2轮开始到循环完成，算法将产生一个关于S’的最佳前缀码树T’。由引理7.5，如果在第2轮前把结点a和b从点p切下，循环完成后再把结点a和b连接到点p就可以得到关于字符集S的最佳前缀码树T。显然，我们不需要把a和b与点p切断。哈夫曼算法确定了字符a和b之后，把整个p为根的树对应到一个字符p，效果一样。这就省去了切断和再连接的操作。引入切断和再连接的操作是为了方便证明引理7.5而已。所以，算法结束时，优先队列Q中只含一棵关於集合S的前缀码树T。由引理7.5，这个前缀码树T必定最佳。归纳成功，定理正确。

41例7.3 假设S={A，B，C，D

，E，F}。S中字符使用的频率为f(A)=5，f(B)=8，f(C)=2，f(D)=4，f(E)=9，f(F)=12。找出它们的一组哈夫曼码。解：424344开车从城市A到B，经过加油站，1，2，…，n。开始油箱为空，在城市A的油站(标为0号)加油后出发。城市B的加油站标为n+1号。从站(i-1)到站i距离已知为D[i]公里(1≤i

≤n+1)。定义D[0]=0。站i的油价已知为P[i]，这里的价格已转换为元/公里。在油站n+1加的油不计入本问题，为方便，定义P[n+1]=0。汽车装满油可跑L公里，大于任两相邻加油站距离。问题：设计一个算法确定，从0号油站开始，应该在那些油站加油和加多少油使得汽车到达城市B时总共用的油钱最少。6.最佳加油计划问题45解的基本思路从0号加油站开始，在每一个停靠站，须要回答两个问题：下一站应该停在几号加油站？在当前停下的加油站应加多少钱的油？两个符号：(1) R[i]表示到达i号油站时(0≤i≤n