Lec 9: Greedy Algorithms⚓︎

Introduction⚓︎

实际上，贪心算法(greedy algorithms) 也已经在 FDS 中介绍过，比如求单源最短路的 Dijkstra 算法、求最小生成树的 Kruskal 算法等。本篇笔记将会更系统地讲解贪心算法的知识，以及补充更多相关的经典例子。先来了解一下基本概念：

• 优化问题(optimization problem)：给定一组限制条件(constraints) 和优化函数(optimization function)，称满足限制条件的解为可行解(feasible solutions)。如果一个可行解在优化函数中取得最佳值，则称该解为最优解(optimal solution)。

• 贪心法(greedy method)：

  • 根据预先设定的贪心标准，在每个阶段中作出最佳决策
  • 当前作出的决策不允许在后面改变，所以确保作出的每个决策都是可行的，否则就是“一步错，步步错”
  • 只有当“局部最优 = 全局最优”时，贪心算法才是可行的
  • 贪心算法不保证得到最优解，但它能够产生与最优解相当接近的解（所以贪心算法属于一种启发式算法(heuristics)），因此当找最优解耗时太长时，贪心算法可能更加适合。

贪心算法的范式：

• 优化问题 -> 先做出一个选择，剩下一个有待解决的子问题
• 需要证明对于原问题，贪心选择总能保证得到最优解
• 证明问题具备最优子结构(optimal substructure)——做出贪心选择后，剩余的子问题具备这样的性质：如果将子问题的最优解和做出的贪心选择相结合，便能得到原问题的最优解

在每个贪心算法下，总是有一个更笨拙的 DP 解。

贪心算法的正确性证明包括：

• 贪心选择性质：通过局部最优贪心选择来构造全局最优解。这样的话在做当前选择的时候就不必考虑子问题的解。
• 最优子结构：一个问题的最优解包含其子问题的最优解。

Activity Selection⚓︎

例子

下面以表格形式给出活动集 \(S\)，并且将每个活动的时间区间关系表示出来：

答案

最优解为最多安排 4 个活动，但有多个最优解，如下所示（用红色或绿色标出的区间）：

• 我们先尝试用上节课讲到过的 DP 来解

  • 规定：\(a_1\ a_2 \dots \underbrace{a_i \dots a_k \dots a_j}_{S_{ij}} \dots a_n\)，注意 \(a_i\) 和 \(a_j\) 不在 \(S_{ij}\) 内，即 \(S_{ij}\) 是一个开区间

  • 令 \(c_{ij}\) 为活动 \(a_i\) 和 \(a_j\) 之间最多的活动数，则得到状态转移方程

    \[ c_{ij} = \begin{cases}0 & \text{if}\ S_{ij} = \emptyset \\ \max\limits_{a_k \in S_{ij}} \{c_{ik} + c_{kj} + 1\} & \text{if}\ S_{ij} \ne \emptyset\end{cases} \]

    其中在 \(S_{ij} \ne \emptyset\) 的情况用到了分治算法的思想：根据中间的某个活动 \(a_k\)，将整个区间分为左右两半，分而治之，最后再算上 \(a_k\)（\(+1\)）

  • 由于 \(i, j, k\) 都是 \(O(n)\) 的，因此时间复杂度为 \(O(N^3)\)，所以整个算法感觉就像是在暴力搜索（我认为 PPT 的 \(O(N^2)\) 是错的，但是可以通过其他技巧优化到 \(O(N^2)\)）。但为了提升速度，我们可以算得更“贪心”一些

• 我们先尝试几个贪心策略（假设红色区间表示最优解）：

  • 策略 1：挑选最早开始的活动

    • 反例：

      

      如果采用这种策略，那么就要先挑选那个最早开始，也是时间最长的区间，这样的话剩余的三个区间就没得选了，因此这种方法肯定是不行的。

  • 策略 2：挑选时间最短的活动

    • 反例：

      

      如果采用这种策略，那就要先挑选那个最短的，且和剩余两个区间都冲突的区间，这样的话剩余的两个相互不冲突区间就没得选了，因此这种方法也是不行的。

  • 策略 3：挑选冲突最少的活动

    • 反例：

      

      可以看到冲突最少的区间是位于中间位置的黑色区间，如果选择它的话，与它冲突的两个区间就不能选了，这样的话最多只能选择 3 个区间，而不是最优解的 4 个区间，因此这种方法也行不通。

  • 策略 4：挑选最早结束的活动

    • 可以自行检验，这种策略可以解决上面给出的所有反例

    • 接下来需要验证这种策略的正确性：

      • 贪心选择性质：考虑任意非空子问题 \(S_k\)，令 \(a_m\) 为 \(S_k\) 中最早结束的活动，那么 \(a_m\) 一定被包含在 \(S_k\) 中的某些满足活动相互兼容的最大子集中
      证明

      • 令 \(A_k\) 为最优解集，\(a_{ef}\) 为 \(A_k\) 中最早结束的活动
      • 如果 \(a_m = a_{ef}\)，那么定理成立；否则的话需要用 \(a_m\) 替代 \(a_{ef}\)，得到 \(A_k'\)
      • 因为 \(f_m \le f_{ef}\)（由条件知），因此 \(A_k'\) 是另一个最优解，得证。

      这种证明方法称为交换参数法：假设存在一个最优选择，其中的某些元素不在贪心选择中，此时可以通过交换贪心选择和最优选择的元素来构造一个不可能变差的解。

      • 最优子结构：在活动选择问题中，用贪心策略选择 \(a_k\) 之后得到子问题 \(S_k\)，那么 \(a_k\) 和子问题 \(S_k\) 的最优解一定可以得到原问题的一个最优解

    • 实现步骤：

      • 选择首先结束的活动，递归解决剩余的活动子集
      • 由于这是一个尾递归，因此可以用迭代方法替代
      • 时间复杂度：\(O(N \log N)\)（目前不清楚为什么）
      • 对应地，也可以采取“选择最晚开始的活动”这一策略，具体原因这里就不分析了

• 得到正确的贪心算法后，我们回过头来修改 DP 的状态转移方程：

  \[ c_{1, j} = \begin{cases}1 & \text{if}\ j = 1 \\ \max \{c_{1, j - 1}, c_{1, k(j)} + 1\} & \text{if}\ j > 1\end{cases} \]

  其中 \(c_{1, j}\) 是 \(a_1\) 到 \(a_j\) 之间的最优解，\(a_{k(j)}\) 是离 \(a_j\) 最近的、兼容的、且先于 \(a_j\) 完成的活动

• 如果每个活动都有一个权重，那么状态转移方程为：

  \[ c_{1, j} = \begin{cases}w_j & \text{if}\ j = 1 \\ \max \{c_{1, j - 1}, c_{1, k(j)} + w_j\} & \text{if}\ j > 1\end{cases} \]
  • 此时 DP 算法依然可行，但是贪心算法就行不通了（我还没探究具体原因）

活动选择问题的变体：

• 加权活动选择问题：现在考虑的不是尽可能多的活动，而是权重尽可能大的活动，此时一般的贪心算法会失效，但可以用动态规划来解决本问题

• 区间调度问题：要求用尽可能少的教室举办所有的活动

  • 解决方案（比前面的活动选择问题还要简单）：
    • 首先设置初始教室数量为 1，将所有活动按照开始时间排序，然后从前往后遍历
    • 每次选择一个活动时，看当前有无空闲教室，如果有就直接放进对应的教室，否则的话则新开一个教室

  • 正确性证明：我们可以用一个时间轴（如下图的红色虚线）来扫一遍所有的活动。根据算法，只需要扫每个活动的开头即可，因为：

    • 活动一旦开始就不会被中断，因此后面的选择不会影响当下的选择（所以无需遍历每个时间点，可见贪心提高了效率）
    • 在这个时间点上，如果存在多个活动举行，那么就需要将该活动放在别的房间举行；如果没有多余的房间，就需要新增一个房间了。因此该算法能够正确得到所需最少的房间数
    

  • 如果继续采用活动选择问题中的算法（即先选出尽可能多的活动放入一个教室，然后在剩余活动中挑选尽可能多的活动放入第二个教室，以此类推直到所有活动都被放入教室里），则无法得到最优解，上面的图片便是反例，读者可自行检验。

Huffman Codes⚓︎

我们通常用一棵二叉树来表示这些字符编码（这种树称为字典树(trie)）

• 对于字符 \(C_i\)，它的深度和频率分别为 \(d_i\) 和 \(f_i\)，那么总的编码成本为 \(\sum d_i f_i\)

• 对于前一种原始的编码方式，得到的字典树如下所示：

  

  成本 = 2 * 4 + 2 * 1 + 2 * 2 + 2 * 1 = 16

• 而对于后一种优化的编码方式，得到的字典树如下所示：

  

  成本 = 1 * 4 + 3 * 1 + 2 * 2 + 3 * 1 = 14

不难发现，这些字典树均有这样一个特征：所有的字符位于叶子节点，而不会位于内部节点，因为这样可以实现“例子”中提到的注意点。像这样的树称为满树(full tree)，树上的 01 编码称为前缀码(prefix code)。

事实上，第二种编码方式便是经典的哈夫曼编码(Huffman Codes)，其算法的伪代码如下所示：

void Huffman(PriorityQueue heap[], int C) {
    consider the C characters as C single node binary trees,
    and initialize them into a min heap;

    for (i = 1; i < C; i++) {
        create a new node;
        // be greedy here
        delete root from min heap and attach it to left_child of node;
        delete root from min heap and attach it to right_child of node;            
        weight of node = sum of weights of its children;
        // weight of a tree = sum of the frequencies of its leaves
        insert node into min heap;
    }
}

时间复杂度：\(T = O(C \log C)\)

例子

题目答案

给定以下字符及其频率，请你得到对应的哈夫曼编码，并计算编码的总成本。

动画演示

我们还要证明这种贪心算法的正确性：

• 贪心选择：令 \(C\) 为一张字母表，其中字符 \(c \in C\) 的频率为 \(c.freq\)。令 \(x, y\) 为 \(C\) 内频率最小的两个字符，那么在 \(C\) 中存在一个最优的前缀码，\(x\) 和 \(y\) 的编码具有相同的长度且仅相差 1 位。

  

• 最优子结构：（与前一条引理一样的前提条件）令 \(C'\) 为加入新字符 \(z\) 并移除 \(x\) 和 \(y\) 后的字母表，满足 \(z.freq = x.freq + y.freq\)。令 \(T'\) 为表示字母表 \(C'\) 的最优前缀码的树，那么树 \(T\) 可以通过移除树 \(T'\) 的叶子节点 \(z\)，用 \(x, y\) 以及一个内部节点构成的子树替代得到，它能够表示字母表 \(C\) 的最优前缀码（可用归谬法证明）。

  

Other Examples⚓︎

下面给出了其他的贪心算法相关的问题：

• 田忌赛马
• 拟阵
• 聚类问题
• 匹配问题
  • 稳定匹配问题
• 分数背包问题
• 最大容量问题
• 最大切分乘积问题

评论区