Greedy Algorithm 贪心算法

理解贪心算法的思想；
能判断一个算法是否贪心算法；
掌握工作安排Interval scheduling问题的贪心算法及其正确性证明；

★Greedy Algorithm 贪心算法

Basic Idea 基本思想

In each iteration, we choose the "best"solution at that moment. This "best" solution may notyield the BEST final solution. 在每次迭代中，我们都会选择当时的“最佳”解决方案。这种“最佳”解决方案可能不会产生最佳的最终解决方案。

Local optimal v.s. Global optimal 局部最优vs.全局最优

Greedy algorithm isto make the locally optimal choice at each moment. In SOME problems , such strategy can lead to a globaloptimal solution. 贪心算法是在每个时刻做出局部最优选择。在某些问题中，这种策略可以导致全局最优解。

Advantage 优点

Simple , efficient 简单、高效

Disadvantage 缺点

May be incorrect / may not be optimal 可能不正确 / 可能不是最佳

问题 > Coin changing 找硬币

问题描述

Goal. Given U. S. currency denominations, 给定美国货币面额 { 1, 5, 10, 25, 100 },
devise a method to pay amount to customer using fewest coins. 设计一种使用最少硬币向客户支付金额的方法

贪心算法：Cashier′s algorithm 收银员算法

At each iteration, add coin of the largest value that does not take us past the amount to be paid. 在每一次迭代中，添加价值最大的、不超过要支付的金额的硬币。

收银员的算法并不是对任何一组面额都是最优的

Is cashier’s algorithm optimal for any set of denominations? 收银员的算法对任何一组面额都是最优的吗？

No. 否 Consider U.S. postage 考虑美国邮费: 1, 10, 21, 34, 70, 100, 350, 1225, 1500.
・Cashier’s algorithm 收银员的算法: 140¢ = 100 + 34 + 1 + 1 + 1 + 1 + 1 + 1.
・Optimal 最优: 140¢ = 70 + 70.

★问题 > Interval scheduling 活动安排

问题描述

Job j starts at s_j and finishes at f_j. 活动j开始于s_j，结束于f_j

Two jobs compatible if they don’t overlap. 如果两个活动不重叠，则两个活动兼容

Goal: find maximum subset of mutually compatible jobs. 目标：找到相互兼容活动的最大子集

贪心算法：Earliest-finish-time-first algorithm 最早结束时间优先算法

将所有活动按照结束时间从早到晚排序；

遍历所有n个活动：每次选择相兼容的、最早结束时间的活动加入结果集；

返回结果集。

最早结束时间优先算法正确性证明

Theorem. The earliest-finish-time-first algorithm is optimal. 定理：最早结束时间优先算法是最优的。

Pf. [by contradiction] 证明[反证法]

・Assume greedy is not optimal, and let’s see what happens. 假设贪心算法不是最优的
・Let i₁, i₂, ... i_k denote set of jobs selected by greedy. 设i₁，i₂，…i_k表示贪心算法选择的一组活动
・Let j₁, j₂, ... j_m denote set of jobs in an optimal solution with i1 = j₁, i₂ = j₂, ..., i_r = j_r for the largest possible value of r. 设j₁，j₂，…j_m表示最优解中的活动集，其中i₁=j₁、i₂=j₂、…、i_r=j_r的最大可能值为r（前r组贪心算法和最优解相同，且第r+1组贪心算法和最优解不同）。

贪心算法选择了最早结束时间优先的i_r+1，最优解j_r+1的结束时间晚于贪心算法选择的。那为什么不用贪心算法中最早结束时间优先的活动i_r+1替换最优解中的活动j_r+1，替换后不影响最优解后续的活动，而且最优解中活动数量不变。

依次替换每组，直到最优解与贪心解相同。证得贪心解就是一个最优解。

问题 > Interval partitioning 活动划分

问题描述

Lecture j starts at s_j and finishes at f_j. 讲座j从s_j开始，到f_j结束

Goal: find minimum number of classrooms to schedule all lectures so that no two lectures occur at the same time in the same room. 目标：找到最少的教室来安排所有的讲座，不能在同一个房间里同时安排两场讲座。

贪心算法：Earliest-start-time-first algorithm 最早开始时间优先算法

将所有讲座按照开始时间从早到晚排序；

遍历所有n场讲座：
如果这场讲座时间内有空教室，安排这个教室个这个讲座；
如果这场讲座时间内没空教室，添加一个新教室，安排这个教室个这个讲座；

返回结果集。

最早开始时间优先算法可以在 O(n log n) 时间内完成

Lower bound on optimal solution 最优解的下界

最早开始时间优先算法正确性证明

Observation. The earliest-start-time first algorithm never schedules two incompatible lectures in the same classroom. 观察：最早的开始时间优先算法从不在同一个教室安排两次不兼容的讲座。

Theorem. Earliest-start-time-first algorithm is optimal. 定理：最早开始时间优先算法是最优的。

Pf. 证明：

・Let d = number of classrooms that the algorithm allocates. 设d为算法分配的教室数量。

・Classroom d is opened because we needed to schedule a lecture, say j, that is incompatible with a lecture in each of d – 1 other classrooms. 之所以使用第d个教室，是因为我们需要安排一个讲座j（开始于s_j），讲座j与其他d–1个教室的讲座都不兼容（其他d–1个教室的讲座在s_j之后结束）。

・Thus, these d lectures each end after s_j. 因此，这d个讲座每次在s_j之后结束。

・Since we sorted by start time, each of these incompatible lectures start no later than s_j. 由于我们按开始时间排序，所以这些不兼容的讲座中的每一场开始时间都早于s_j。

・Thus, we have d lectures overlapping at time s_j + ε. 因此，我们有d个讲座在时间s_j+ε重叠。

・Key observation ⇒ all schedules use ≥ d classrooms. 关键点：所有计划使用的教室 ≥ d个。

问题 > Scheduling to minimizing lateness 最小延迟调度

问题描述

Single resource processes one job at a time. 只有单个资源，一次只能处理一个活动。

Job j requires t_j units of processing time and is due at time d_j . 活动j需要t_j单位的处理时间，并在时间d_j截止

If j starts at time s_j , it finishes at time f_j = s_j + t_j . 如果j在时间s_j开始，则它在时间f_j=s_j+t_j结束。

Lateness: ℓ_j = max { 0, f_j – d_j }. 延迟：ℓ_j=最大{0，f_j–d_j}。

Goal: schedule all jobs to minimize maximum lateness L = maxj ℓ_j . 目标：安排所有活动，使所有活动的最大延迟L=maxj ℓ_j最小。

贪心算法：Earliest deadline first 最早截止日期优先

No idle time 没有空闲时间

Observation 1. There exists an optimal schedule with no idle time. 观察1：最优解中没有空闲时间

Observation 2. The earliest-deadline-first schedule has no idle time. 观察2：最早截止日期优先算法没有空闲时间

Inversions 逆序

Def. Given a schedule S, an inversion is a pair of jobs i and j such that: i < j but j is scheduled before i. 对于调度S，逆序是指一对作业i号和j号，编号i＜编号j，但作业j在作业i之前调度。

We assume the jobs are numbered so that d₁ ≤ d₂ ≤ … ≤ d_n. 作业按照截止排序编号。

Observation 3. The earliest-deadline-first schedule is the unique idle-free schedule with no inversions. 观察3：最早截止日期优先算法的调度是唯一的、无空闲的、没有逆序调度。

Observation 4. If an idle-free schedule has an inversion, then it has an adjacent inversion. 如果无空闲的调度具有逆序，则它具有相邻的逆序。

Key claim. Exchanging two adjacent, inverted jobs i and j reduces the number of inversions by 1 and does not increase the max lateness. 关键断言：交换两个相邻的逆序作业i和j可减少1个逆序次数，但不会增加最大延迟。

最早截止日期优先算法的正确性证明

Greedy analysis strategies 贪心算法分析策略

Greedy algorithm stays ahead. 贪心算法保持领先

Show that after each step of the greedy algorithm, its solution is at least as good as any other algorithm’s. 事实证明每一步都是贪心的算法，其解至少与任何其他算法的解一样好。

Structural. 结构

Discover a simple “structural” bound asserting that every possible solution must have a certain value. Then show that your algorithm always achieves this bound. 每个解都有一个简单的"结构"界限，找到这个界限。然后证明你的算法也能达到这个界限。

Exchange argument. 交换参数

Gradually transform any solution to the one found by the greedy algorithm without hurting its quality. 逐步将任何解转换为贪心算法找到的解，而不损害其质量。

Other greedy algorithms. 其他贪心算法

Kruskal, Prim, Dijkstra, Huffman, …