Greedy Algorithm

1. Greedy algorithm 简介
2. 实例：活动选择问题
- 2.1. 解法 1：动态规划
- 2.2. 解法 2：贪心算法
  - 2.2.1. 活动选择问题贪心算法实现
3. 实例：单源最短路径（Dijkstra 算法）
4. 实例：最小生成树
5. 实例：背包问题
- 5.1. 0-1 knapsack problem（不能用贪心算法）
- 5.2. fractional knapsack problem（贪心算法）

1. Greedy algorithm 简介

A greedy algorithm is an algorithm that follows the problem solving heuristic of making the locally optimal choice at each stage with the hope of finding a global optimum.

贪心算法并不一定得到整体最优解，有时得到的仅是一个局部最优解。所以我们需要证明贪心算法的正确性。

参考：
Introduction to Algorithms, 3rd Edition. Chapter 16 Greedy Algorithms
"Greedy Exchange": a technique used in proving the correctness of greedy algorithms
Guide to Greedy Algorithms

2. 实例：活动选择问题

问题描述：有很多活动需要以独占的方式使用某一公共资源（如教室），该资源一次只能被一个活动占用。怎样从活动集合中选择活动，使公共资源能服务的活动数量最多？

设活动组成的集合为 $S = {a_{1}, a_{2}, . . ., a_{n}}$ ，每个活动 $a_{i}$ 的开始时间为 $s_{i}$ ，结束时间为 $f_{i}$ ，即该活动占用的时间为 $[s_{i}, f_{i})$ 。 如果两个活动 $a_{i}$ 和 $a_{j}$ 满足 $[s_{i}, f_{i})$ 和 $[s_{j}, f_{j})$ 不重叠，则称它们是兼容的，活动选择问题是目标就是寻找最大的兼容活动集。

例如，考虑下面的活动集合：
$\begin{array}{cccccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ s_{i} & 1 & 3 & 0 & 5 & 3 & 5 & 6 & 8 & 8 & 2 & 12 \\ f_{i} & 4 & 5 & 6 & 7 & 9 & 9 & 10 & 11 & 12 & 14 & 16 \end{array}$

对于这个例子，子集 ${a_{1}, a_{4}, a_{8}, a_{11}}$ 是一个最大兼容活动集。这个问题还有其他的解，如： ${a_{2}, a_{4}, a_{8}, a_{11}}$

上面例子的结果已提前给出，但如何解决这个问题呢？请看下面内容。

参考：Introduction to Algorithms, 3rd Edition. Section 16.1 An activity-selection problem

2.1. 解法 1：动态规划

我们容易验证这个问题具有最优子结构性质。为了寻找最优子结构，定义如下的集合： $S_{i j} = {a_{k} \in S : f_{i} \leq s_{k} < f_{k} \leq s_{j}}$
显然， $S_{i j}$ 是 $S$ 中活动的子集，其中的每个活动都在活动 $a_{i}$ 结束之后开始，且在活动 $a_{j}$ 开始之前结束。

假设 $S_{i j}$ 的最优解 $A_{i j}$ 包含活动 $a_{k}$ ，则显然 $A_{i j}$ 也包含 $S_{i k}$ 的最优解 $A_{i k}$ 及 $S_{k j}$ 的最优解 $A_{k j}$ 。即有： $A_{i j} = A_{i k} \cup {a_{k}} \cup A_{k j}$ ，从而有： $| A_{i j} | = | A_{i k} | + | A_{k j} | + 1$
上面递归式假设 $k$ 值已知，然而我们并不知道。 $k$ 的取值可能是 $i + 1, . . ., j - 1$ ，共有 $j - i - 1$ 种可能。于是： $| A_{i j} | = {\begin{cases} 0 & if S_{i j} = \emptyset, \\ max_{a_{k} \in S_{i j}} {| A_{i k} | + | A_{k j} | + 1} & if S_{i j} \neq \emptyset . \end{cases}$

到此为止，已经得到一个递归解法，可根据这个递归式直接编程即可实现（运行效率低）。也可设计一个带备忘机制的递归算法，或者设计一个表格化的、自底向上基于前面递归式的动态规化算法。具体的编程实现略。

2.2. 解法 2：贪心算法

直观上，我们应该选择这样一个活动，选出它后剩下的资源应能被尽量多的其他活动所用。
现在考虑可选的活动，其中必然有一个最先结束。 所以我们应该每次选择 $S$ 中最早结束的活动，因为剩下的资源可供尽量多的活动使用。

采用上面的贪心选择算法，由于 $a_{1}$ 最先结束，所以选择活动 $a_{1}$ ，按同样的方法在剩下活动中依次选择 $a_{4}, a_{8}, a_{11}$ 。可以得到活动选择问题的一个解为： ${a_{1}, a_{4}, a_{8}, a_{11}}$

要证明它的正确性，只需要证明我们的第一个选择，即第一个最早结束的活动 $a_{1}$ 在某个最大的兼容活动集中。这个结论是“显而易见”的。形式化的严谨证明可参考“算法导论，第 3 版，定理 16.1”。

说明：不能采用这样的贪心策略：“每次选择 $S$ 中占用时间最少的活动”，因为它不一定得到正确解。比如下面例子中，如果“每次选择 $S$ 中占用时间最少的活动”，则应该选择下排的三个活动，但事实上我们可以找到更多的兼容活动（上排的四个活动）。

+-----+--------+--------+   +-------+
|     |        |        |   |       |
1--2--3--4--5--6--7--8--9--10--11--12
|  |        |     |             |   |
+--+        +-----+             +---+

2.2.1. 活动选择问题贪心算法实现

/* 贪心算法解决活动选择问题 */
#include<stdio.h>

void greedy_activity(int s[], int f[], int n) {
    int i = 1;                                       // 由于约定f按单调递增的顺序排列，所以可以总是选择a1。
    printf("The selected activities are: a%d ", i);
    int j;
    for (j=1; j<n; j++) {
        if (s[j] >= f[i]) {
            printf("a%d ", j+1);
            i = j;
        }
    }
    printf("\n");
}

int main() {
    int s[] =  {1, 3, 0, 5, 3, 5,  6,  8,  8,  2, 12};   // 活动开始时间
    int f[] =  {4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16};   // 活动结束时间
    int n = sizeof(s)/sizeof(s[0]);

    greedy_activity(s, f, n);

    return 0;
}

运行上面程序，会输出：“The selected activities are: a1 a4 a8 a11 ”

3. 实例：单源最短路径（Dijkstra 算法）

参考：http://aandds.com/blog/algorithm-graph.html

4. 实例：最小生成树

参考：http://aandds.com/blog/algorithm-graph.html

5. 实例：背包问题

背包问题（Knapsack problem）描述如下：假设我们有 $n$ 件物品，其编号分别为 $1, 2, \dots, n$ 。其中编号为 $i$ 的物品价值为 $v_{i}$ ，重量为 $w_{i}$ 。为了简化问题，假定价值和重量都是整数值。现在，假设我们有一个背包，它能够承载的重量是 $W$ 。现在，我们希望往包里装这些物品，使得包里装的物品价值最大化，那么我们该如何来选择装的东西呢？如图 1 所示。

Figure 1: 背包问题（摘自其 Wikipedia）

这个问题根据不同的情况可以归结为不同的解决方法。假定我们选取的物品每个都是独立的，不能选取部分。也就是说我们要么选取某个物品，要么不选取它，不能只选取一个物品的一部分，这种情况，我们称之为 0-1 背包问题（0-1 knapsack problem）。而如果我们可以选取部分物品的话，这个问题则成为部分背包问题（fractional knapsack problem）。

5.1. 0-1 knapsack problem（不能用贪心算法）

要使得背包里装的物品价值最大，那我们贪心地每次选取那些单位价值最高（即 $v_{i} / w_{i}$ 最高）的物品可以吗？通过下面的例子我们可以发现这种贪心策略不可取。假设背包最多可承重 10kg，现在有 2 种物品，重量和价值为 2kg，10kg 和 4，8。按照前面的贪心策略，我们会选取物品 1（因为它的单位价值最高），此时由于背包承重的限制我们无法再选择物品 2 了。而显然这个问题的解是选择物品 2（价值为 8）。

我们需要换一种思路。假设问题的解为物品 $a_{1}, a_{2}, \dots, a_{k}$ ，此时如果把最后一个物品 $a_{k}$ 拿掉，则对于剩下的 $k - 1$ 个物品 $a_{1}, a_{2}, \dots, a_{k - 1}$ 来说它的重量范围为 $0 \sim (W - w_{k})$ ，而且用反证法可以推导它是其子问题（即背包总承重为 $W - w_{k}$ 的背包问题）的最优解。

上面的推理表明“0-1 背包问题的最优解中包含其子问题的最优解”。具有这个特点的问题往往可以用“动态规划”来解决。

基于上面的推理，下面介绍使用“动态规划”解决 0-1 背包问题的过程。我们定义函数 $m [i, w]$ 表示到第 $i$ 个物品为止，在限制总重量为 $w$ 的情况下我们所能选择到的最优解对应的总价值。则 0-1 背包问题最优解对应的总价值就是 $m [n, W]$ 。

显然，有下面推导关系：
$m [i, w] = {\begin{cases} 0 & if i = 0 or w = 0 \\ m [i - 1, w] & if w_{i} > w \\ max (m [i - 1, w], m [i - 1, w - w_{i}] + v_{i}) & if w_{i} \leq w \end{cases}$

下面的伪代码可以解决 0-1 背包问题：

// pseudo code for 0-1 knapsack problem

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)

for j from 0 to W do:
    m[0, j] := 0

for i from 1 to n do:
    for j from 0 to W do:
        if w[i] > j then:
            m[i, j] := m[i-1, j]
        else:
            m[i, j] := max(m[i-1, j], m[i-1, j-w[i]] + v[i])

算法的时间复杂度为 $O (n W)$ 。

参考：https://en.wikipedia.org/wiki/Knapsack_problem#0/1_knapsack_problem

5.2. fractional knapsack problem（贪心算法）

可以用贪心算法解决“部分背包问题”。贪心策略是： 优先选取单位价值最高的物品，直到达到背包的重量限制。