Greedy Algorithm

Table of Contents

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}{c|ccccccccccc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline 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_{ij} = \{a_{k} \in S: f_{i} \leq s_{k} < f_{k} \leq s_{j} \}\]
显然, \(S_{ij}\) 是 \(S\) 中活动的子集,其中的每个活动都在活动 \(a_{i}\) 结束之后开始,且在活动 \(a_{j}\) 开始之前结束。

假设 \(S_{ij}\) 的最优解 \(A_{ij}\) 包含活动 \(a_{k}\) ,则显然 \(A_{ij}\) 也包含 \(S_{ik}\) 的最优解 \(A_{ik}\) 及 \(S_{kj}\) 的最优解 \(A_{kj}\) 。即有:\(A_{ij} = A_{ik} \cup \{ a_{k} \} \cup A_{kj}\) ,从而有:\[|A_{ij}| = |A_{ik}| + |A_{kj}| + 1 \]
上面递归式假设 \(k\) 值已知,然而我们并不知道。 \(k\) 的取值可能是 \(i+1, ..., j-1\) ,共有 \(j-i-1\) 种可能。于是: \[|A_{ij}| = \begin{cases} 0 & \text{if} \; S_{ij} = \emptyset, \\ \max \limits_{a_{k} \in S_{ij}} \{ |A_{ik}| + |A_{kj}| + 1 \} & \text{if} \; S_{ij} \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算法)

4 实例:最小生成树

5 实例:背包问题

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

algorithm_knapsack_problem.png

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, \cdots, a_k\) ,此时如果把最后一个物品 \(a_k\) 拿掉,则对于剩下的 \(k-1\) 个物品 \(a_1, a_2, \cdots, 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 & \text{if} \; i=0 \; \text{or} \; w=0 \\ m[i-1, w] & \text{if} \; w_i > w \\ \max(m[i-1,w], m[i-1,w-w_i] + v_i) & \text{if} \; w_i \le 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(nW)\) 。

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

5.2 fractional knapsack problem(贪心算法)

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


Author: cig01

Created: <2011-09-03 Sat 00:00>

Last updated: <2017-12-16 Sat 17:37>

Creator: Emacs 25.3.1 (Org mode 9.1.4)