贪心算法逐步作出局部最优的选择,并且从不修改已作的选择。许多看似合理的贪心规则其实是错的,所以真正有用的能力不是设计规则,而是证明规则。标准的证明技巧是交换论证:取任意一个最优解,说明它可以一步步改造成与贪心选择一致的解,而且不会变差。最小生成树一节中的割性质就是一个例子;本节把这个方法单独抽出来,应用于另外两个问题。贪心算法与动态规划都依赖最优子结构,但贪心算法只承诺于单一个子问题,而不是比较多个子问题,交换论证正是用来证明这个承诺是合理的。
1. 证明模式
定义 19.1.1
(贪心选择性质与最优子结构)
设问题要求在可行解中使目标函数最小或最大。贪心算法依固定规则挑选元素。要证明它正确,需证明两个性质。
- 贪心选择性质。 对每个实例,都存在一个包含贪心选择的最优解。
- 最优子结构。 固定贪心选择之后,包含它的最优解的其余部分,是同类型的较小实例的最优解。
然后对实例大小作归纳,即可证明贪心算法最优:它作出与某个最优解一致的选择,由归纳假设最优地解决较小的实例,两部分合起来是最优的。工作的核心是性质 1,并以交换来证明:设 是不含贪心选择 的最优解,构造包含 且不比 差的 。只证明算法的输出可行,或在若干例子上最优,都不算证明。
第二种形式是针对排序问题的相邻交换论证:说明在任何次序中,交换违反贪心规则的两个相邻条目不会令目标变差,而当违反是严格的时,目标严格改善。
2. 区间调度
定义 19.1.2
(相容请求与区间调度)
问题。 给定 个请求,请求 占用半开区间 ,。选出最大的两两相容的请求集合,相容指区间互不相交。使用半开区间意味着 与 相容。
贪心规则(最早结束时间)。 在与已选请求相容的请求中,反复选取结束时间最小的一个。
sort requests by f (ties broken arbitrarily)
last = -infinity; chosen = []
for each request i in this order:
if s_i >= last:
append i to chosen
last = f_i
return chosen
由于请求按结束时间递增处理,当前请求 与所有已选请求相容,当且仅当 最近选取的请求的结束时间(它也是迄今最大的结束时间)。
定理 19.1.3
(最早结束时间的最优性)
该算法返回一个大小最大的相容请求集合。
证明
(交换第一个请求)
对请求数作归纳。没有请求时显然成立。令 为第一个被选取的请求,它的结束时间在所有请求中最小(若有并列,任取一个)。
贪心选择性质。 设 为最优集合,其区间按开始时间(由于互不相交,等同于按结束时间)排序为 。因为 的结束时间全局最小,。若 无需改动。否则令 。 的结束不迟于 ,而 的结束不迟于 的开始,所以 与 相容。因此 相容且 ,故它也是最优的,并包含 。
子结构。 令 为满足 的请求集合,即恰好与 相容的请求。任何包含 的相容集合,都是 加上 的一个相容子集。若 不是 的最大相容子集,把它换成更大的,就得到包含 的更大相容集合,与 的最优性矛盾。所以 是 的最优解。
选取 之后,算法恰好等于在 上运行同一算法,因为它会跳过开始于 之前的请求,而其余请求仍按结束时间排列。由归纳假设,它返回 的最优集合,加上 即得 ,也就是最优值。
证明透视
结束时间规则在交换中的位置
这个证明只有一步不是例行的:把 换成 。这一步所需的每个事实都在确定的位置使用。第一, 成立,仅仅因为 的结束时间在所有请求中最小;贪心规则只在这里用到。第二,最优解的区间两两不相交,所以 ;把两个不等式连起来得 ,而 的开始时间都不早于 ,所以同一个界对它们也成立。第三,子结构一步把交换后的最优解 变成较小实例 的最优解。
去掉第一个事实,交换就失败。对“最早开始”的选择 与 ,,所以 与 相撞。论证之所以能收尾,是因为 不含 (),所以 的请求比原实例少,归纳假设可以使用。
复杂度。 排序主导:,扫描为 。
反例模式
最早开始与最短请求都不是最优
声称:每次选开始最早的请求,或选最短的请求,总能得出最大的相容集合。两个说法都是错的。对 、、,“最早开始”规则选 ,它与其余两个都重叠,所以只得 1 个请求,而 相容,有 2 个。对 、、,长度为 ,“最短请求”规则选 ;它与 在 重叠,与 在 重叠,结果只有 1 个请求,而 与 相容,因为 与 不相交。修正方法是结束时间规则:在第一个实例中,它选 再选 ;在第二个实例中,它选 (结束于 5),跳过 (开始 ),再选 (开始 )。
3. 例题:区间调度
例题 19.1.4
(八个请求的最早结束时间调度)
请求(半开区间):A 、B 、C 、D 、E 、F 、G 、H 。按结束时间排序:A(4)、B(5)、C(6)、D(7)、E(9)、F(9)、G(10)、H(11)。
- A:,选取;last 。
- B:开始 ,跳过。C:开始 ,跳过。
- D:开始 ,选取;last 。
- E:开始 ,跳过。F:开始 ,跳过。G:开始 ,跳过。
- H:开始 ,选取;last 。
结果为 ,大小为 3。由定理,不存在含四个请求的相容集合。作为对比,“最早开始”规则先选 C(开始于 0),然后选第一个开始于 6 或之后的请求,即 G,其后没有开始于 10 或之后的请求(H 开始于 8):只得两个请求,严格较差。
例题 19.1.5
(首尾相接的区间与并列的结束时间)
取 、、、。结束时间为 ,所以 与 并列。按次序 :选 (last );跳过 (开始 );选 (开始 ,因为 与 不相交);跳过 (开始 )。结果为 。按次序 ,同样的步骤得 。两个输出是大小同为 的不同集合,这与定理并不矛盾:定理确定的是答案的大小,而不是集合本身。并列时的选择不影响后续步骤,因为 与 的结束时间同为 。
4. 最小化加权完成时间
定义 19.1.6
(完成时间与加权完成时间)
问题。 项工作在单一机器上逐项运行,无空隙,从时间 0 开始。工作 的处理时间为 ,权重为 。在某个次序中,工作 的完成时间 是直至并包括它在内的所有工作的处理时间之和。要最小化 。
贪心规则(Smith 规则)。 按比值 不递减的次序处理工作。
引理 19.1.7
(相邻交换)
设工作 与 在某个调度中相邻, 紧接在 之前,这一对从时间 开始。交换两者使目标函数(交换前减交换后)恰好改变 ,其他工作的完成时间不变。
证明
(只有被交换的一对改变)
两项工作无论次序如何,都占用同一个区间 ,所以其他工作的完成时间不变。交换前,这一对的贡献为 ;交换后为 。相减时,、 与 互相抵消,剩下 。
由于 , 当且仅当 。
定理 19.1.8
(Smith 规则最优)
任何按 不递减排列的次序都使 最小,而且所有这类次序的成本相同。
证明
(消除相邻逆序)
令 为最优次序(排列只有有限个,最优次序必存在)。若它含有相邻一对 满足 (严格逆序),交换它们由引理使成本严格下降,与最优性矛盾。所以 没有相邻的严格逆序,即相邻比值不递减,由传递性整个次序按比值不递减。任何两个按比值不递减的次序,只相差于比值相等的工作之间的排列;交换比值相等的相邻工作,由引理使成本改变 ,而比值相等的各块的任何排列都是一连串这样的交换。所以所有不递减次序的成本都等于 的成本,即最优值。
证明透视
为什么局部交换能得出整体最优
引理纯属局部:它只计算一次相邻交换的得失。使它变成整体结论的一步,是把 取为最优次序;由于排列只有有限个,最优次序必存在。矛盾出现在“严格”二字:严格逆序 给出严格为正的节省量 ,所以 还能改进。 用来把 的正负化为比值的比较;若有权重为零,比值就不能反映正负。没有相邻的严格逆序,就表示比值序列不递减;此时只有比值相等的各块可以自由排列,而每次交换的节省量恰为 ,所以所有这类次序的成本相同。
5. 例题:Smith 规则
例题 19.1.9
(三项工作的 Smith 规则)
工作: 的 ,比值 ; 为 ,比值 ; 为 ,比值 。Smith 次序为 ,完成时间为 ,成本 。
逐一检查全部六个次序可确认它最优。:完成时间 ,成本 。:,成本 。: 于 1, 于 4, 于 6:。:14。: 于 2, 于 5, 于 6:。: 于 2, 于 3, 于 6:。最小值为 14。
6. 常见错误
反例模式
权重最大优先并不最优
声称:按权重不递增处理工作,可使 最小。取工作 与 。先做 :、,成本 。先做 :、,成本 。所以按权重优先的次序并不最优。两者的比值为 与 ,Smith 规则先做 ,与成本比较的结果一致。修正方法是使用比值 ,而不是只看权重。
常见错误
(可行或在例子上最优都不是证明)
贪心规则必须对每个实例证明最优。只证明输出可行,或只在少数实例上最优,既不能确立贪心选择性质,也不能确立最优子结构。上面的“最早开始”与“最短优先”规则的输出必然可行,也看似自然,却都会失败。
常见错误
(交换后离开了可行解的范围)
交换必须从任意一个最优解 出发,而不是从贪心解出发,并且必须验证改造后的解可行。在区间调度中,把 换成 之所以可行,是因为 ,而其余区间都开始于 之后。结果不可行的交换什么也证明不了。
常见错误
(Smith 规则的比值方向与并列情况)
Smith 规则按 不递减排序,等价于按 不递增;方向相反会把又长又轻的工作排在前面。比值相等的工作在这里可以任意排列,因为交换它们使成本改变 。在其他贪心问题中,并列可能有影响,所以要说明对并列情况声称了什么。
练习
快速检查
(对 、、、、、 应用最早结束时间调度。)
先按结束时间排序。
解答 · 答案
按结束时间排序:(2)、(3)、(5)、(7)、(9)、(10)。选 ;last 。 开始于 ,跳过。 开始于 ,选取;last 。 开始于 ,跳过。 开始于 ,选取;last 。 开始于 ,跳过。所选集合为 ,共 3 个请求。
快速检查
(给出一个三请求的实例,使“最早开始优先”不是最优。)
让其中一个请求很长。
解答 · 答案
取 、、。最早开始选 ,它与另外两个都重叠,得 1 个请求。集合 相容,有 2 个请求。
练习 19.1.10
(按 Smith 规则排列工作 :、、、,并计算成本。说明两种合法的并列次序成本相同。)
核心
解答(3)
- 1
计算比值并排序
比值 为 、、、。不递减次序为:先是比值 1 的 ,然后是比值 2 的 与 (任一次序),最后是 。
- 2
第一种并列次序的成本
次序 的完成时间为 ,所以
依据: 完成时间是处理时间的累计和。
- 3
另一种并列次序的成本与比较
次序 的完成时间为 ,成本为 。两种并列次序的成本都是 46。
快速检查
(利用 Smith 规则说明:要使处理时间为 的工作的完成时间总和最小,应先做最短的工作,并计算最小值。)
所有权重均为 1。
解答 · 答案
所有权重为 1 时,比值 ,所以 Smith 规则按处理时间不递减排序:。完成时间为 ,总和为 。作为对比,次序 的完成时间为 ,总和 。