数据集
交互工具采用的六个任务数据与贪心选择与动态规划一节的三个区间不同。任务按结束时间排序,占用半开区间:前一个任务恰好在下一个开始时结束,两者仍可兼容。调整任务 E 的报酬并观察表格,不要把前例的数值套进来。
前驱索引与递推式
定义 2.5.1
(前驱索引与前缀最优值)
把任务 按结束时间非递减排列:。任务 占用半开区间 ,其中 ,报酬为 。两个任务的区间不相交时兼容,所以一个任务恰好在另一个开始时结束,两者仍然兼容。前驱索引 是满足 的最大 ;若没有这样的 ,则 。令 为任务 的相容子集所能得到的最大总报酬,并规定 。
对任务 , 是一个索引:它标示一段可用的前缀,不是报酬,也不意味着必须选取该最后任务。E 在时刻 5 开始,C 在 5 结束,因此 。截至 C 的前缀子问题考虑 A、B、C 中的相容子集,并选取报酬最大的子集。
定理 2.5.2
(加权区间递推式)
对 ,
此外,在任务 之中,与任务 兼容的恰是任务 。
证明
(包含或不包含最后一个任务)
对 ,任务 与 的区间不相交,当且仅当 :另一种可能 会给出 ,不可能成立。若 ,则 ;若 ,则由 的选取知 。因此在 之中与 兼容的恰是 。
再取 的一个最优相容子集 。若 ,则 是 的相容子集,报酬至多为 ,而 的一个最优子集达到这个值。若 ,则 是 的相容子集,所以 的报酬至多为 ;反过来, 的一个最优子集加上 仍相容,并达到这个值。每个相容子集都属于两种情形之一,两个值也都能达到,所以 是两者的最大值。以 为基础,对 归纳即覆盖所有行。
证明透视
为什么一个索引可以代表一整组任务
唯一不显然的一点,是较早的兼容任务构成一段前缀,所以“包含”分支只涉及一个较小的子问题 。这正是用到按结束时间排序之处:它使条件 随 单调。区间长度为正,即 ,用来排除 的情形。按 与否分类是穷尽的,没有损失,所以不需要交换论证。归纳得以完结,是因为两个分支都只涉及更短的前缀,并以 为基础。两个分支并列并不影响数值,只影响回溯返回哪一个调度。
因此,排序是方法的一部分,而不是为方便而做的步骤。
反例模式
按开始时间排序会破坏前缀性质
断言:不论任务以什么顺序列出,较早的任务中与任务 兼容的总是一段前缀 。按开始时间列出 (报酬 )、(报酬 )和 (报酬 )。满足 的最大 是 ,所以公式会采用前缀 ,其最大报酬为 (取 )。于是公式报告 ,对应同时含 与 的调度,但两者重叠,真正的最优值是 。修正方法是按结束时间排序,使 随 单调,兼容的任务才构成前缀。
阅读轨迹
例题 2.5.3
(默认报酬:选取 E)
取 。A 至 F 的前驱索引依次为 :例如 D 在 开始,恰是 B 结束之时,这是允许的;F 在 开始,恰是 D 结束之时。表格为 。第 3 行比较 与 ;第 4 行比较 与 ;第 5 行比较 与 ;第 6 行比较 与 。回溯时,第 6 行因 而跳过;第 5 行选取 E 并跳至 ;第 3 行跳过;第 2 行选取 B 并跳至 。调度 的报酬为 。对 E 的比较是在相应前缀的完整调度之间进行,而不是只拿 E 与相邻任务比较。
例题 2.5.4
(报酬为 4:不决定调度的并列)
设 。第 5 行比较 与 :两个选项都等于 ,轨迹在相等时跳过 E。第 6 行比较 与 ,故选取 F,表格为 。回溯时选取 F 并跳至 ;第 4 行因 选取 D 并跳至 ;再选取 B。调度 的报酬为 。在第 5 行选取 E 对该前缀同样最优,即 ,报酬 ,但 F 与 E 重叠,这个前缀调度无法扩充为整体最优解。中间一行的平局本身不是最终调度。
例题 2.5.5
(没有前驱与报酬为零)
第 2 行的 ,因为没有较早的任务在时刻 之前结束。“包含”分支为 ,胜过“不含”分支 ;基础值 使这种情形不需要特殊处理。现在设 。第 5 行比较 与 ,跳过 E;其余各行与报酬为 时相同,得到 ,报酬 。报酬为零的任务永不被选取:它的“包含”值 不可能超过 ,因为 非递减,而轨迹只在包含严格更好时才选取。
回溯时,选取任务就跳至其前驱,跳过则退回上一行;两种情况都保持剩余前缀的最优值。
常见错误
常见错误
(把前驱索引当作已选取的任务)
索引 标示的是一段可用的前缀,并不表示任务 被选取。对 E, 使 A、B、C 都可用,但该前缀内最好的调度报酬为 ,只含 B,并不含 C。
常见错误
(使用错误的端点比较)
数据是半开区间,所以前驱检验是 。若共用端点算作冲突,检验就要改为 ,表格也会随之改变。D 在 开始,恰是 B 结束之时。按半开规则,,(任务 B 与 D);按严格规则,则 ,因为只有 A 在时刻 之前结束,而 。
练习
快速检查
(E 的报酬为 9 时,回溯选取哪些任务?总报酬是多少?)
从第 6 行开始,只在包含严格更好时才选取任务。
解答 · 答案
第 6 行比较 与 ,跳过 F。第 5 行比较 与 ,选取 E 并跳至第 3 行。第 3 行比较 与 ,跳过 C。第 2 行比较 与 ,选取 B 并跳至第 0 行。选取的任务为 B 与 E,总报酬为 。
快速检查
( 是多少?为什么是 而不是 ?)
把 F 的开始时间与 D、E 的结束时间比较。
解答 · 答案
F 在 开始。任务 D 占用 ,在 结束,按半开区间约定两者兼容,所以 。任务 E 占用 ,在 结束,与 F 重叠,不可用。因此 。
快速检查
(E 的报酬至少为多少(取整数),回溯才会选取 E?)
把第 5 行与第 6 行的“包含”值、“不含”值写成 的函数来比较。
解答 · 答案
第 5 行给出 。在第 6 行,当 时选取 F,此时 E 不会被选取,因为 F 与 E 重叠。 时 ,故选取 F。 时 ,第 6 行平局,跳过 F;第 5 行因 而选取 E。报酬更大时情况相同。所以最小的报酬是 。