贪心算法

1. 贪心算法 (Greedy Algorithm)

  • 基本思想：在每一步中选择“当前最优解”，即局部最优解，期望通过一系列局部最优选择达到全局最优。
  • 局部最优与全局最优的关系：
    • 贪心算法仅在某些特定问题中有效，即局部最优选择能导出全局最优解。
    • 贪心算法通常简单且高效，但并不总是正确。
  • 优点：算法简单、执行效率高。
  • 缺点：可能产生错误结果或次优解。

1.1案例：区间调度问题 (Interval Scheduling)

  • 问题描述：
    • 给定 $n$ 个任务，每个任务有一个开始时间 $s_j$ 和结束时间 $f_j$。
    • 两个任务相容当且仅当它们不重叠。
    • 目标：选择最多数量的相容任务。
  • 贪心策略：
    • 按任务的结束时间 $f_j$ 升序排序。
    • 每次选择当前最早结束且与已选任务不冲突的任务。
  • 时间复杂度：
    • 排序：$O(n \log n)$。
    • 遍历：$O(n)$。
    • 总时间复杂度：$O(n \log n)$。

以下是区间调度问题 (Interval Scheduling) 的贪心算法伪代码：

区间调度问题的伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Algorithm Interval_Scheduling
Input: 一个任务集合 S = {(s_1, f_1), (s_2, f_2), ..., (s_n, f_n)}，
       每个任务 i 有开始时间 s_i 和结束时间 f_i
Output: 最多的相容任务集合 A

1. 将任务按照结束时间 f_i 升序排序
2. 初始化相容任务集合 A = {}
3. 初始化上一个任务的结束时间 last_finish_time = 0
4. for each task (s, f) in S do
5.     if s >= last_finish_time then
6.         将任务 (s, f) 添加到集合 A 中
7.         更新 last_finish_time = f
8.     end if
9. end for
10. return A

时间复杂度分析

  1. 排序：将任务按照结束时间排序需要 $O(n \log n)$ 时间。
  2. 遍历：检查所有任务需要 $O(n)$ 时间。
  3. 总复杂度：$O(n \log n)$。

定理：贪心算法是最优的**

证明方法：反证法 (Proof by Contradiction)

  1. 假设贪心算法不是最优的：
    • 设 $i_1, i_2, \dots, i_k$ 是贪心算法选择的任务集合。
    • 设 $j_1, j_2, \dots, j_m$ 是最优解选择的任务集合，且 $m > k$。
    • 假设两个集合的前 $r$ 个任务是相同的，即 $i1 = j_1, i_2 = j_2, \dots, i_r = j_r$，但 $i{r+1} \neq j_{r+1}$。
  2. 分析任务 $i{r+1}$ 和 $j{r+1}$ 的关系：
    • 根据贪心算法的选择策略，任务 $i{r+1}$ 的结束时间比 $j{r+1}$ 的结束时间早，即 $f{i{r+1}} \leq f{j{r+1}}$。
    • 因为贪心算法优先选择结束时间最早的任务，所以任务 $i_{r+1}$ 不与前 $r$ 个任务冲突。
  3. 替换分析：
    • 由于任务 $i{r+1}$ 比 $j{r+1}$ 更早结束，且它与前 $r$ 个任务相容，可以用 $i{r+1}$ 替换 $j{r+1}$。
    • 替换后，新的任务集合仍然是合法的解，且任务数量不变，但结束时间更早。
  4. 矛盾：
    • 根据上述替换操作，可以构造一个比最优解更优的解（即任务数量相同但结束时间更早），这与最优解的定义矛盾。
    • 因此，假设贪心算法不是最优的成立不了。

关键结论

  • 贪心选择性质：每一步选择结束时间最早的任务不会影响全局最优解。
  • 最优子结构：贪心算法的解是最优解的一部分，且每一步选择后剩余问题仍然是原问题的子问题。

1.2 区间分配问题 (Interval Partitioning)

image-20241123165945029

问题描述

  • 给定多个讲座，每个讲座的开始时间和结束时间分别为s_j和f_j。
  • 目标：用最少数量的教室安排所有讲座，使得同一教室内没有重叠的讲座。

贪心算法方法

  1. 按照讲座的开始时间s_j递增排序。
  2. 遍历排序后的讲座列表：
    • 检查当前讲座是否可以分配到现有教室中（该教室中最后一个讲座的结束时间早于当前讲座的开始时间）。
    • 如果可以，则分配到该教室。
    • 如果不可以，则分配一个新教室。
  3. 返回分配的教室总数。

伪代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
IntervalPartitioning(lectures):
    sort lectures by start time s_j (ascending)
    d ← 0  // 教室总数
    initialize a priority queue classrooms to store end times of lectures in each classroom

    for each lecture j in lectures:
        if lecture j is compatible with any classroom k:
            // Compatible: the last lecture in classroom k ends before lecture j starts
            assign lecture j to classroom k
            update the end time of classroom k in classrooms
        else:
            d ← d + 1  // Allocate a new classroom
            assign lecture j to the new classroom d
            insert end time f_j of lecture j into classrooms

    return d

实现细节：

  • 使用优先队列存储每个教室的结束时间，始终优先分配结束时间最早的教室。
  • 排序的时间复杂度为O(nlog⁡n)，遍历讲座列表的时间复杂度为O(nlog⁡d)O（d是教室数量）。

贪心最优性证明

引理：贪心算法分配的教室数量d恰好等于区间深度（最大重叠数）。

核心观察

  • 贪心算法永远不会在同一个教室中安排两个互相不兼容的讲座，因为它在每一步都选择与现有教室安排兼容的讲座。

证明

  1. 设定：
    • $d$：贪心算法分配的教室总数。
  2. 贪心分配新教室的原因：
    • 当分配到第 $d$ 个教室时，说明有一个讲座 $j$ 无法与前 $d-1$ 个教室中的任何安排兼容。
    • 换句话说，$j$ 与所有前 $d-1$ 个教室中正在进行的讲座重叠。
  3. 关于这些讲座的性质：
    • 这些不兼容的讲座（包括 $j$ 在内）总共有 $d$ 个。
    • 它们的结束时间都晚于 $j$ 的开始时间 $s_j$。
  4. 按开始时间排序的作用：
    • 因为所有不兼容都发生在 $s_j$ 或更早时间开始的讲座之间。
    • 因此，这些讲座重叠的时间段是 $s_j + \epsilon$（$\epsilon$ 是一个非常小的正数）。
  5. 关键观察：
    • 在时间 $s_j + \epsilon$，有 $d$ 个讲座同时进行，导致需要至少 $d$ 个教室。
  6. 结论：
    • 任何调度方案都需要至少 $d$ 个教室。
    • 贪心算法正好使用了 $d$ 个教室，因此它是最优的。

1.3 加油站问题（Selecting Breakpoints）

问题描述

  • 场景：从 Princeton 到 Palo Alto 的固定路线中，有若干加油站，车的燃油容量为 $C$。
  • 目标：在尽可能少的加油次数下完成旅程。

贪心算法思路

  • 核心原则：在当前油量范围内，选择能到达的最远加油站。
  • 贪心选择的理由：最远加油站可以为下一段行程提供最长的可行范围，确保加油次数最少。

伪代码

image-20241123173007212

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
SelectBreakpoints(L, C):
    # 输入：加油站的位置列表 L，燃油容量 C
    # 输出：加油的站点序列

    sort L in ascending order  # 按加油站位置升序排列
    x ← 0  # 当前车辆所在位置
    S ← ∅  # 加油站点集合
    n ← length of L
    i ← 0  # 当前加油站索引

    while x < L[n-1]:  # 未到达终点
        p ← -1  # 记录当前最优选择
        while i < n and L[i] <= x + C:  # 找到当前油量范围内的所有可选站点
            p ← i  # 更新最优选择
            i ← i + 1
        if p == -1:  # 如果没有可以到达的站点
            return "No solution"
        S.append(L[p])  # 在 p 点加油
        x ← L[p]  # 更新当前位置
    return S

时间复杂度

  • 排序的时间复杂度：$O(n \log n)$。
  • 遍历加油站的时间复杂度：$O(n)$。
  • 总体时间复杂度：$O(n \log n)$。

正确性证明

  1. 假设：
    • 贪心算法选择的加油站序列为 $g_1, g_2, \dots, g_k$。
    • 最优解为 $f_1, f_2, \dots, f_m$，其中 $m < k$。
  2. 比较前若干站点：
    • 假设两者在前 $r$ 个站点一致，即 $g1 = f_1, g_2 = f_2, \dots, g_r = f_r$，且 $g{r+1} \neq f_{r+1}$。
    • 贪心算法选择的 $g{r+1}$ 是当前能到达的最远站点，而最优解选择了 $f{r+1}$。
    • 如果 $f{r+1}$ 比 $g{r+1}$ 更近，则 $f_{r+1}$ 无法保证后续行程的最少加油次数，导致矛盾。
  3. 结论：
    • 贪心算法的选择确保了最远的行驶范围，因此保证了全局最优性。