第4章_贪心算法_作业

课后练习：算法分析题 算法分析题4-6(教材第128页):字符a~h出现 的频率恰好是前8个Fibonacci数，它们的哈夫曼 编码是什么？ 解答： Fibonacci数列1 n 0 F n 1 n 1 F n 1 F n 2 n 1

前8个Fibonacci数为： 1, 1, 2, 3, 5, 8, 13, 21, ……

则a, b, c, d, e, f, g, h这 8个字符出现的次数依 次为：1, 1, 2, 3, 5, 8, 13, 21次。

0 33 0

54

121

200 8 0 5 0 3 1 12

1

13

以此构造一颗 Huffman树(不唯一) 如右： 对应的Huffman编码 为： a: 0011100 b:0011101 c: 001111 d: 00110

1 7 1 4 0 2 0 1 1 1 1 2

e: 0010g: 01

f: 000h: 1

课后练习 练习2:假设有25分、10分、5分和1分四种硬币， 需要找给顾客2元5角钱，请问用贪心算法可以求 出何种找零方案？该方案是最优的么？为什么？ 解答： – 2元5角 = 250分，按照贪心算法(尽量用面值大 的硬币找零),则需要25分硬币10个即可。 – 该算法是最优的，因为五种硬币的面值中5分是 25分和10分的约数(因数)。

课后练习 练习3:活动安排问题。假设有9个活动申请使用1 个会议室，每个活动的开始时间和终止时间如下。 用贪心算法设计一个活动安排表，要求要尽可能 的多安排活动。会议室不允许被多个活动同时占 用。活动序号 起始时间 结束时间 1 2 5 2 1 5 3 2 8 4 5 10 5 7 11 6 4 13 7 6 15 8 8 22 9 15 24

活动序号起始时间 结束时间

12 5

21 5

32 8

45 10

57 11

64 13

76 15

88 22

915 24

根据贪心算法，第1个被安排的活动为1号活动，因为它的 结束时间(时刻5)最早。(贪心选择性质) 然后每次都选取起始时间最接近于上一次活动的结束时间 的活动，所以分别依次选择4号活动(时刻10结束)、9号 活动(时刻24结束),则最优解为：( 1, 4, 9 )。 显然，最优解不唯一，比如： ( 2, 4, 9 )。但显然，用贪心 策略求出的可行解是最优的。

课后练习练习4:单源最短路径问题。求下面连通图中从源 顶点v0到其它各顶点的最短路径。 ① 列出源顶点到其它顶点的最短路径长度和路径中 顶点序列。 ② 证明该算法的正确性。

迭代

S

u

dist[1]

dist[2]

dist[3]

dist[4]

初始1

{0}{0,1}

1

1010

maxint60

3030

100100

23

{0,1,3}{0,1,3,2}

32

1010

5050

3030

9060

4

{0,1,3,2,4}

4

10

50

30

60

算法正确性证明：教材114页-115页

课后练习练习5:最小生成树问题。

① 用Prim或者Kruskal算法求出下图中的最小生成树。② 证明该算法的正确性。(教材116页) 6 V1 1 V3 5

V23

5

54

V42

6V5 3

V6

课后练习 Kruskal算法： V1 V2 1 V3 V4 V2

65 6 V5

V1

5 5 V4

1V3

3

43 V1 1 1 V3 3 V6 5 5 4 3 V6

2

3V5

43 V6

2V2 V 2

65 6 V5

V V44

3 Prim算法：

2

练习6:一队徒步旅行者要从A地到B地，两地间距离为L公 里。他们每天最多可以走d公里(与地形、天气条件等无 关),中间需要就地宿营。 假定这些潜在的宿营地点位于起点A地的距离为x1, x2, ……, xn的地方，显然它们之间的距离小于等于d,称这些地点(停 止点)是有效的。 于是，一组停止点是有效的，如果人们只能在这些地方宿营 并且仍旧能顺利完成旅行。则必须假设n个停止点所组成的 集合都是有效的；否则就没法走完整个路程。 问题1:假设两地距离为100公里，潜在的宿营地点为{ 6, 14, 30, 37, 48, 65, 73, 76, 88, 90,94 }。旅行者每天最多走18公里。 给出最优(最少)的有效宿营地组合(最少几天能走完)。 问题2:证明该算法的正确性(解的最优)。

课后练习 问题1:假设两地距离为100公里，潜在的宿营地 点为{ 6, 14, 30, 37, 48, 65, 73, 76, 88, 90,94 }。旅行 者每天最多走18公里。给出最优(最少)的有效 宿营地组合(最少几天能走完)。 解答：根据贪心算法，潜在的宿营地点的选取应 该遵循每天尽量多走(但不多于18公里)的原则， 以期用最短的时间走完100公里的行程。源点 14 30 48 65 76 94

目的点B地

A地

需要7天才能走完，这与[100/18]+1 = 6结果符合！

课后练习 问题2:证明该算法的正确性(解的最优)。 解答：这个策略有可能是无效的么？ 一个想法：该算法能否保证某一天提早停止就使 后面一些天的宿营地点同步提前。有没有可能真 存在一个解，它故意落在贪心解的后面，然后突 然加速并且越过贪心解？在给出贪心解每天旅行 尽可能远的条件下，它怎样越过贪心解？

课后练习 设R = { xp , …, xp }表示由贪心算法选择的停止点的集合， 1 k 根据反证法，假设存在一个更小的停止点的有效集合： 把这个较小的集合称为S = { xq , …, xq },显然此时m< 1 m k。 证明I:贪心算法在每一天到达的停止点j比在其它解下 到达的停止点更远，即： 对每个j = 1, 2, …, m,有xp ≥xqj j

证明I:贪心算法在每一天到达的停止点j比在其它解下到 达的停止点更远，即： 对每个j = 1, 2, …, m,有xp ≥xqj j

证：j = 1的情况直接从贪心算法的定义得出：旅行者第1天 在停止之前走得尽可能远。 现在令j > 1并且假设这个断言对所有的i < j为真，那么 xq – xq ≤ d 因为S是停止点的有效集合，且根据归纳假设，由xp ≥xq j-1 j-1 有： x –x ≤x –xq j p j-1 q j q j-1 j j-1

由此可以推得： xq – xp ≤ d,即旅行者能够选择在1天之 j j-1 内走完从xp 到xq 的所有路程；因此他们最后停留的宿营地 j-1 j xp 只能比xq 更远。命题得证!j j

设R = { xp , …, xp }表示由贪心算法选择的停止点的集合， 1 k 根据反证法，假设存在一个更小的停止点的有效集合：把 这个较小的集合称为S = { xq , …, xq },显然此时m<k。1 m

对每个j = 1, 2, …, m,有xp ≥xqj m m

j

由上述命题(已证明),推出xp ≥ xq 式①。 现在m < k,那么一定有： xp < L – d 式② ,否则旅行者不 m 必停在xp 。m+1

把两式组合可得： xq < L – d ;但这与假设S是一个有效的 m 停止点集合相矛盾。

从而，不可能有m < k,即存在一个更小的停止点的有效集 合(较小的集合)S = { xq , …, xq }的假设是不成立的！1 m

所以贪心算法产生一个最小的有效停止点集合得证！

End