带权区间调度:子问题必须排除冲突
在无权问题中,选择最早结束的活动可以使相容活动的数量最大,但不一定使总收益最大。一旦我们确定了选择某个活动之后剩下的更小问题,动态规划就能奏效。
1. 明确调度模型
共有 n 个活动。活动 i 占用半开区间 [s_i,f_i),其中 s_i<f_i,收益为 w_i。收益可加,什么都不选的收益为零。输入按结束时间排序,这样每个相容前缀都可以被识别出来。
定义 7.1.1
(带权区间调度与前驱下标)
若两个活动占用的区间不重叠,则称它们相容;一个活动恰好在另一个活动开始时结束是允许的。问题要求找出一组两两相容、总收益最大的活动,空集的收益为 。将活动按结束时间非降序排序,并以确定的规则处理并列情况,然后按此顺序编号为 。
- 前驱下标 是满足 的最大下标 ;若不存在这样的下标,则为 。
- 是只从前 个活动中选出相容集合所能获得的最大总收益,并令 。
定理 7.1.2
(前驱递推式)
设活动已按结束时间非降序编号,且 ,收益 为任意实数。则对 ,
证明
(排除活动 i 或包含活动 i)
令 为 的所有相容子集构成的族(包括空集),于是 就是 上总收益的最大值。按是否选取 把 分成两类。
不含 的集合恰好就是 的成员,因此它们的最佳收益为 。
现取 。由排序知 ,而 ,故 :活动 不可能在 或之后才开始。所以 与 相容,当且仅当 在 或之前结束,即 。集合 恰好是前缀 :若 ,则 ;若 ,则 ,因为 是具有该性质的最大下标。
因此,含 的集合相容,当且仅当它形如 ,其中 。其收益为 ,所以这类集合的最佳收益是 ,并且可以取到。 中的每个集合恰好属于两类之一,两个值都能取到,所以 是两者中较大的一个。收益为负也不构成问题:空集既属于 ,也属于 ,所以两个分支都不会被迫承受损失。
递推式只在位置 和 读取表格,因此可以按 的顺序填表。仅靠排序并不能解决问题;排序的作用是使相容的活动构成一个前缀。
证明透视
各项假设在递推式中的作用
这个论证只有一个结构性步骤:包含 的调度与前缀 的调度,可以通过加入或去掉 一一对应。三项假设使这个对应成立。
第一,按结束时间排序,使每个 都有 。第二,区间长度为正,即 。两者合起来排除了下标更小的活动从右侧与 相容的唯一方式,即在 或之后才开始,于是与 相容就化为单一检验 。第三,由于结束时间非降,这个检验把 以下的下标切成一个前缀,所以只用一个数 就能概括所有冲突。
论证随后便告完成:被去掉的 本身就是前缀内任意的相容集合,所以 正是所需的量;而两个互相穷尽的情形的最大值,就是两个情形的值中较大者。去掉排序这一假设,第一点和第三点就会失效;最后一节的反例表明递推式会给出错误的值。
概念视角结构
把递推式看成最长路径
取节点 ,并为每个节点 设两种入边:边 ,权重为 (跳过活动 );边 ,权重为 (选取它)。每条边都指向前方,所以图无环,节点可以按递增顺序处理。从节点 出发的最长路径距离 满足 及 ,这正是 的递推式。从 到 的一条路径对应于它所用选取边所属的活动集合:若路径选取了 ,之后又选取 ,则它必先到达节点 ,所以 ,两者相容。反过来,每个相容集合都给出这样一条路径。重构就是沿着每个最大值所取的边往回走。
2. 例题
例题 7.1.3
(含边界相等情形的五个活动)
下列活动已按结束时间排好序。计算每个前驱时,将之前活动的结束时间与当前活动的开始时间进行比较,相等的情况也要计入。
i | 区间 | 收益 | p(i) | OPT(i) |
|---|---|---|---|---|
| 1 | [1,3) | 5 | 0 | 5 |
| 2 | [2,5) | 6 | 0 | 6 |
| 3 | [4,6) | 5 | 1 | 10 |
| 4 | [6,7) | 4 | 3 | 14 |
| 5 | [5,8) | 11 | 2 | 17 |
例如,活动 4 可以接在活动 3 之后,因为 6 <= 6。在活动 5 处,不包含得到 14,而包含得到 11+OPT(2)=17,所以选择 5,并继续到下标 2。在 2 处,包含得到 6,不包含得到 5,所以选择 2。选中的区间 [2,5) 和 [5,8) 的总收益为 17。前驱是一个下标,而不是之前某个活动的总收益。
为了重构调度方案,从 i=n 开始。若 w_i+OPT(p(i)) > OPT(i-1),则选择 i 并令 i=p(i);否则令 i=i-1。出现相等时,这一策略会跳过 i,从而得到一个有效的最优解;在相等时选择 i 也是有效的,只要随后从 p(i) 继续重构即可。若需要按时间顺序排列,最后将所选下标反转即可。
例题 7.1.4
(负收益与空调度)
取已按结束时间排序的活动:[0,2) 收益 ,[1,3) 收益 ,[3,5) 收益 。前驱:活动 1 的 p(1)=0;活动 2 在 1 开始,但活动 1 在 2 才结束,所以 p(2)=0;活动 3 在 3 开始,而活动 2 在 3 结束,所以 p(3)=2。
各值:OPT(1)=max{0, -4+0}=0,OPT(2)=max{0, 2+0}=2,OPT(3)=max{2, -1+OPT(2)}=max{2,1}=2。重构:在 3 处,-1+2=1 不大于 OPT(2)=2,所以跳过并移到 2;在 2 处,2+0=2>OPT(1)=0,所以选择 2 并跳到 0。最优解是只选单个活动 [1,3),收益为 2。若所有收益都为负,每次包含检验都会失败,重构就会得到收益为 0 的空调度,这正是边界情形 OPT(0)=0 的作用。
例题 7.1.5
(用二分搜索计算 p(i))
沿用第一个例题的结束时间 3,5,6,7,8,计算 p(5),其中 s_5=5。我们要在 0..4 中找出满足 f_j <= 5 的最大 j,并规定 j=0 总是可接受。维护一个已知包含答案的区间 [lo,hi],初始为 lo=0、hi=4;当 lo<hi 时,探测 mid=ceil((lo+hi)/2),若 f_mid <= s_i 则令 lo=mid,否则令 hi=mid-1。
探测 mid=2:f_2=5<=5,所以 lo=2。探测 mid=3:f_3=6>5,所以 hi=2。区间为 [2,2],故 p(5)=2,与表格一致。两个极端情形几乎不需要探测:i=1 时区间为 [0,0],立刻得到 p(1)=0;i=2(s_2=2)时,探测 mid=1 得 f_1=3>2,所以 hi=0,p(2)=0。每个前驱大约需要 log2 i 次探测。
3. 复杂度与一个边界陷阱
排序的代价为 O(n log n)。由于结束时间已经有序,可以在前缀 1,...,i-1 中二分搜索结束时间不超过 s_i 的最右侧活动,每个前驱耗时 O(log n),总计 O(n log n)。填表和重构各需 O(n) 时间,表格、前驱数组和输出共占用 O(n) 空间。这些结论假设对给定数值的比较和算术运算都是常数时间的。对每个前驱向后逐一扫描也是正确的,但代价可能达到 Theta(n^2)。
如果规定当一个端点等于另一个端点时区间也视为冲突,那么相容性检验就变为 f_j < s_i;前驱数组和答案都可能改变。递推式必须与问题本身的规则相符,而不是依赖某种未明确说明的约定。
常见错误
(允许端点相接时却用了严格不等式)
若模型允许 [a,b) 与 [b,c) 同时被选,却写成 f_j < s_i,前缀就会变短。在第一个例题中,这会使 p(4)=2 而不是 3,因为 f_3=6 不再被接受;于是 OPT(4)=max{10, 4+6}=10 而不是 14,p(5) 变为 1,最终答案由 17 降到 16。检验必须依据所规定的相容规则来选择。
常见错误
(把 i-1 当作前驱)
排序使活动 i-1 不晚于 i 结束,但它仍可能与 i 重叠。在第一个例题中,[6,7)(活动 4)与 [5,8)(活动 5)重叠,所以 w_5+OPT(4)=25 不是任何调度的值。正确的前驱是 p(5)=2,它跳过了所有与活动 5 冲突的活动。
表格同样依赖输入的顺序,下面的例子说明这一点。
反例模式
递推式要求输入按结束时间排序
假设活动按如下顺序列出:活动 1 为 [2,4),收益 5;活动 2 为 [0,1),收益 3,因此结束时间 4 与 1 并非非降。沿用同一定义,p(2) 是满足 f_j<=0 的最大 j<2;由于 f_1=4,得 p(2)=0。于是 OPT(1)=5,OPT(2)=max{5, 3+OPT(0)}=5。但区间 [0,1) 与 [2,4) 不相交,所以真正的最优值是 5+3=8。活动 1 与活动 2 相容,但在时间上位于其后,而检验 f_j<=s_i 只能发现在活动 i 开始之前结束的活动。按结束时间排序后,[0,1) 在前、[2,4) 在后,于是 p(2)=1,递推式得到 max{3, 5+3}=8。
快速检查
(按结束时间排序的活动为 [0,4) 收益 2,[3,5) 收益 3,[4,7) 收益 1。计算 p(1),p(2),p(3) 与 OPT(1),OPT(2),OPT(3)。)
将每个结束时间与当前活动的开始时间比较,允许相等。
解答 · 答案
p(1)=0。活动 2(开始时间 3):f_1=4>3,所以 p(2)=0。活动 3(开始时间 4):f_2=5>4,但 f_1=4<=4,所以 p(3)=1。于是 OPT(1)=2,OPT(2)=max{2, 3+0}=3,OPT(3)=max{3, 1+OPT(1)}=max{3,3}=3。出现相等,说明有两个最优调度 {2} 与 {1,3},收益都是 3。
练习:重叠的活动
快速检查
(考虑以下活动:[1,3),收益为 4;[3,4),收益为 4;[2,5),收益为 9。求最大收益,并解释为什么在带权收益的情形下,反复选择最早结束的活动是不够的。)
比较总收益之前,先列出哪些活动对相容。
解答 · 答案
按结束时间排序后,前两个活动相容,总收益为 8。第三个活动与前两个都重叠,单独选它可得 9,因此最优值为 9。最早结束选择法会选中前两个活动,得到 8;这一贪心规则优化的是另一个目标,即活动的数量,而不一定是总收益。
练习:五项按结束时间排序的活动
快速检查
(按结束时间排序的活动为:[0,2) 收益 3,[1,3) 收益 5,[2,4) 收益 4,[3,5) 收益 4,[4,6) 收益 3。计算 p、动态规划的值以及一个最优调度。)
先计算 p,再从左到右填表。
解答 · 答案
前驱数组为 [0,0,1,2,3]。从 OPT(0)=0 开始,各值依次为 3,5,7,9,10:例如,第五个活动给出 3+OPT(3)=10,超过了 OPT(4)=9。选择 5,然后选择 3,因为 4+OPT(1)=7>OPT(2)=5,再选择 1。区间 [0,2)、[2,4)、[4,6) 仅在端点处相接,总收益为 3+4+3=10。这一重构过程所依据的,正是证明中使用的“包含/不包含”两种选择。