从动态规划出发设计贪心算法

DONG Yuxuan @ Feb 19, 2017 Asia/Shanghai

先设计一个动态规划算法,再优化成贪心算法。这样可以降低设计贪心算法过程中对技巧性和直觉的依赖。

前言

一个问题如果能够找到一个贪心算法来求解,那么这解法通常是最优且最容易编程的解法,然而贪心算法的设计并不容易,需要对问题的特殊性拥有深入的理解和直觉,其正确性的严格证明也因此而困难。另一方面,动态规划解法则比较容易想到,对技巧性的要求不高,但性能通常不够好。

本文介绍了一种设计贪心算法的方法,它从简单的动态规划解出发,通过对状态转移方程的观察推导出可能的贪心算法,对技巧和直觉的依赖程度相对较小,且算法的设计过程本身便能构成正确性的一个证明。

我们将以两个经典问题(英文排版问题,活动安排问题)为例来阐明这种方法,并在最后做出简要的总结。

英文排版问题

对于一段英文文本,我们要将它打印到一个列宽最大为 $W$ 个字符的屏幕上,在单词不被断行的情况下,我们希望每行末尾的空格数之和最小,问这最小的空格之数和是多少。

如果将单词后的标点符号也算作单词的一部分,那么英文文本可以被看作是由空格分隔的 $n$ 个单词,每个单词长度为 $w_1,w_2,\ldots,w_n, (w_i \leq W)$ 。

众所周知,此问题可以用 $O(n)$ 时间复杂度的贪心算法解决:只要一行还装得下,我们就尽可能地不换行。但是要证明这个算法的正确性却不容易,为此我们可以从动态规划出发,推导出这个贪心算法。

我们很容易得出这个问题的动态规划解:

设 $f(i)$ 表示从 $i$ 个单词到第 $n$ 个单词构成的子文本所能得到的最小空格数之和,由于我们第一步只需要决定与第 $i$ 个单词在同一行的最后一个单词是谁,所以显然我们有

\[f(i)=\min\{f(j+1) + W-\sum_{k=i}^{j}{w_k}+i-j\}, (i \leq j \leq n, j-i+\sum_{k=i}^{j}{w_k} \leq W)\]

边界条件 $f(n+1)=0$ 。

用动态规划求解这个方程我们需要 $O(n^2)$ 的时间,接下来我们通过对方程的观察来得到一个 $O(n)$ 的贪心算法。

注意到方程的物理意义,对于每一个子问题 $f(i)$,我们都需要找出与它在同一行的最后一个单词 $j$,动态规划的方法无非是通过暴力穷举来找出这个最优决策。我们考虑两个可能的决策 $j,j+1$,我们研究在什么情况下,决策 $j$ 比决策 $j+1$ 更优。

\[f(j+1)+W-\sum_{k=i}^{j}{w_k}+i-j < f(j+2)+W-\sum_{k=i}^{j}{w_k}-w_{j+1}+i-j-1\]

可得

\[f(j+2)-f(j+1) > 1+w_{j+1}\]

由于 $f(j+1)$ 与 $f(j+2)$ 相比,顶多能多消除 $w_{j+1}+1$ 个空格,所以 $f(j+2)-f(j+1) \leq 1+w_{j+1}$,也就是说 $j$ 绝不会比 $j+1$ 更优。

至此,我们便得到上述的贪心算法(并且已经证明了它的正确性):

只要一行还装得下,我们就尽可能地不换行。

活动安排问题

有$n$个活动,它们的开始时间分别为 $s_1,s_2,\ldots,s_n$,结束时间分别为 $e_1,e_2,\ldots,e_n$,现在问最多能安排多少个活动,使得各活动的时间没有重叠。

此问题的贪心算法解是大家都知道的:按照结束时间从小到大对活动排序,然后从前往后选取活动,遇到和已选活动有冲突的活动则跳过。由于需要 $O(n\log n)$ 时间的排序过程,所以时间复杂度为 $O(n\log n) + O(n) = O(n\log n)$。

现在用我们的方法来求解这个问题,首先是朴素的动态规划解:

假设活动已按照结束时间升序排序,且为方便起见,规定 $e_0=-\infty$,令 $f(i)$ 表示只考虑前 $i$ 个活动所能安排的最大活动数,规定 $f(0)=0$。对于 $i>0$ 的情况,通过考虑选或者不选最后一个活动来转移状态

\[\begin{equation} f(i)= \max \begin{cases} 1+f(k), (k=\max\{j,(0\leq j<i,e_j<s_i)\}) \\ f(i-1) \end{cases} \end{equation}\]

用动态规划直接求解的时间复杂度为 $O(n^2)$,这里可以有一个优化,由于 $e_i$ 是有序的,所以在查找 $k$ 时可以使用二分搜索,将复杂度降低到 $O(n\log n)$,这已经与经典的贪心算法拥有相同的性能了,但我们会继续优化,直到推导出上述的贪心算法。

我们研究在什么情况下选择活动 $i$ 比不选择更优,既 $1+f(k)>f(i-1)$。当 $k = i - 1$ 时,既活动 $i-1,i$ 不冲突时,必然应该选择活动 $i$。

当 $k < i -1$ 时,由于子问题 $f(i-1)$ 包含子问题 $f(k)$,所以 $f(k)\leq f(i-1)$。于是我们知道 $1+f(k)>f(i-1)$ 当且仅当 $f(k)=f(i-1)$,也就是说子问题 $f(i-1)$ 存在一个最优解( $f(k)$ ),它的最后一个活动( $k$ )与活动 $i$ 不冲突。

综上所述,我们便得到了最开始的贪心算法(并且已经证明它的正确性):

按照结束时间从小到大对活动排序,然后从前往后选取活动,遇到和已选活动有冲突的活动则跳过。

总结

通过以上两个例子,我们可以总结如下的设计贪心算法的一般方法:

这个方法除了能够更加形式化地分析问题,减少对直觉的依赖以外,还有如下优点: