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

1第7章 贪心算法算法概述 2最佳邮局设置问题 3一个简单的最佳活动安排问题 7其它最佳活动安排问题 12?两个大礼堂的最佳活动安排问题 13?等长时间的活动的最佳安排问题 21哈夫曼编码问题 29最佳加油计划问题 44

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

3问题定义设东西方向的街上有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米处，那么必有xH[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)个邮局 fori?2ton //贪心法逐个察看住户位置 ifH[i]P[m]+100 //它不在第m个邮局服务区间内 then m?m+1 //必须再建一个新邮局 P[m]?H[i]+100 endifendforifP[m]H[n] thenP[m]?H[n] //使最后一个邮局不超过H[n]endifreturnP,mEnd显然这个算法复杂度为O(n)。

73.一个简单的最佳活动安排问题问题定义n个活动a1,a2,…,an申请使用大礼堂。ai(1?i?n)有固定的开始时间si和完成时间fi(0?sifi?)。一旦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个活动。0239a1a61a4a10147a7一个非最优解一个最优解

9解题思路如何选取第一个活动？选开始时间最早的活动？这个设想可立即被反例否定。选完成时间最早的活动？完全正确！定理7.1