贪心算法(1)—算法导论(21)

1. 写在前面

之前的5篇博客介绍了动态规划算法。可以看到，在求解最优化问题的算法中，通常需要经过一系列的步骤，在每个步骤中都面临多种选择。对于许多最优化问题，使用动态规划算法来求解最优解有些杀鸡用牛了，可以使用更加简单的算法。贪心算法（greedy algorithm） 就是其中之一：它在每一步做出的选择都是当时看起来的最优选择。也即是说，它总是做出局部最优选择，以此希望这样的选择能够产生全局的最优解。

2. 选择活动问题

2.1. 提出问题

我们先来看看一个适应贪心算法求解的问题：选择活动问题。

假定有一个 $n$ 个活动的集合 $S = \{ a_1, a_2,...,a_n \}$ ，每个活动 $a_i$ 的举办时间为 $[s_i, f_i),0 \leqslant s_i < f_i$ ，并且假定集合 $S$ 中的活动都已按结束时间递增的顺序排列好。由于某些原因，这些活动在同一时刻只能有一个被举办，即对于任意两个活动 $a_i$ 与 $a_j(i \neq j)$ ，区间 $[s_i, f_i)$ 与区间 $[s_i, f_i)$ 不能重叠，此时我们称活动 $a_i$ 与 $a_j$ 兼容。在选择活动问题中，我们希望选择出一个最大兼容活动集。

例如，给出如下活动集合 $S$ ：

$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

子集 $\\{a_3,a_9,a_{11} \\}$ 是相互兼容的，但它不是一个最大集，因为子集 $a_i, a_4, a_8, a_{11}$ 更大。实际上， ${a_1, a_4, a_8, a_{11}}$ 是一个最大兼容活动集，另一个最大集是： $a_2, a_4, a_9, a_{11}$ 。

2.2. 分析问题

2.2.1. 动态规划算法

我们先尝试使用动态规划算法来解决该问题。首先验证该问题是否具有最优子结构性质。

令 $S_{ij}$ 表示在 $a_i$ 结束之后开始，且在 $a_j$ 开始之前结束的活动集合。我们的任务是求 $S_{ij}$ 的一个最大兼容的活动子集。假设 $A_{ij}$ 就是这样一个子集，其中包含 $a_k$ ，于是原问题就被分解为了两个子问题：求解 $S_{ik}$ 与 $S_{kj}$ 中的兼容活动。显然，这两个子问题的兼容活动子集的并是原问题的一个兼容活动子集。

现在问题的关键是两个子问题的最优兼容活动子集的并是否是原问题的最优解。或者反过来，原问题的一个最优解 $A_{ij}$ 是否包含两个子问题的最优解。答案是肯定的，同样可以用剪切-粘贴证明，这里不再赘述。

证明了该问题具有最优子结构性质，于是我们可以用一个递归式来描述原问题的最优解。设 $c[i, j]$ 表示集合 $S_{ij}$ 的最优解的大小，则有：

c[i, j] = \begin {cases} 0 & \text{若$S_{ij} = \varnothing$ }\\ \max \limits_{a_k \in S_{ij}}\{c[i, k] + c[k, j] + 1\}&\text{若$S_{ij} \neq \varnothing$} \end{cases}

于是接下来就可以设计一个自顶向上的动态规划算法。

2.2.2. 贪心选择

我们看到，在上述的动态规划算法中，由于我们不确定到底选择哪一个 $a_k$ ，会产生最优解，因此我们必须考察每一种 $a_k$ 的选取情况。自然地，我们便会想，对于每一次 $a_k$ 的选择，我们可不可以直接找出“最优的 $a_k$ ”的呢？如果能这样，那么算法的效率会大大地提升。

事实上，对于该问题，我们在面临选择时，还真的可以只考虑一种选择（贪心选择）。直观上我们可以想象，要想使活动更多的举办，我们在每次选择活动时，应尽量选择最早结束的活动，这样可以把更多的时间留给其他的活动。

更确切地说，对于活动集合 $S_{ij}$ ，由于活动都按照结束时间递增的顺序排列好，因此贪心选择是 $a_i$ 。如果贪心选择是正确的，按照该选择方法，我们便能将所有选择的结果组合成原问题的最优解。

现在问题的关键是，贪心选择选择出来的元素总是最优解的一部分吗？答案同样还是肯定的，下面的定理说明了这一点：

设 $S_k = \{a_i \in S:s_i \geq f_k\}$ 表示在活动 $a_k$ 结束后开始的活动集合。考虑任意非空子问题 $S_k$ ，令 $a_m$ 是 $S_k$ 中最早结束的活动，则 $a_m$ 在 $S_k$ 的某个最大兼容活动子集中。

我们可以如下证明该定理：设 $A_i$ 是 $S_i$ 的一个最大兼容活动子集，且 $a_j$ 是其中最早结束的活动。若 $a_m = a_j$ ，则自然满足上述结论；若 $a_m \neq a_j$ ，用 $a_m$ 替代 $A_i$ 中的 $a_j$ ，得到子集 $A'$ ，即 $A' = (A - a_j) \cup a_m$ ，则 $A'$ 也是 $S_i$ 的一个最大兼容活动子集。因为 $a_m$ 是 $S_k$ 中最早结束的活动，于是有 $f_m \leq f_j$ ，因此 $A'$ 仍然是兼容的。并且显然 $|A'| = |A|$ ，所以得出上面的结论，也就得出了定理中的结论。

2.3 解决问题

有了上述分析的基础，我们可以很容易设计出一个贪心算法来解决原问题。和动态规划算法相比，由于我们每次都是一次性的找出了当时的最优解，而不必像动态规划算法那样需要考虑每种可能的选择情况，因此贪心算法就不必考虑子问题是否重叠，也就不需要解决重叠问题的“备忘录”了。因此，与动态规划算法相反的是，贪心算法通常都是自顶向下进行设计的。

下面给出一种Python的实现：

def recursive_activity_selector(s, f, k, n, ls):
    m = k + 1
    while m <= n:
        if s[m] >= f[k]:
            ls.append(m)
            recursive_activity_selector(s, f, m, n, ls)
            return ls
        m += 1

对于文章开头给出的例子，做如下测试：

# 测试
if __name__ == '__main__':
    # 注意，这里添加了一个开始时间为0，结束时间也为0的活动。
    s = [0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12]
    f = [0, 4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16]
    k = 0
    n = 11
    ls = []
    recursive_activity_selector(s, f, k, n, ls)
    print(ls)

打印结果为：

[1, 4, 8, 11]

贪心算法(1)—算法导论(21) 2016年06月14日 16:49