动机
多个请求希望独占同一间房,我们希望接受尽可能多的请求。先接受输入中的第一个请求没有依据;先接受最短的请求似乎节省时间;先接受最早结束的请求则似乎为后续留下空间。本节证明的是最后一种规则。
贪心算法作出选择后不再反悔。因此必须说明某个最优解可以保留这个选择。交换证明通过修改一个最优答案、又不使它变差,提供这样的依据。随后还必须准确描述剩余问题,才能重复论证。
本例说明这两项证明任务,并不声称每个优化问题都有贪心规则。我们会区分“接受数量最多”与“已经无法再加入请求”,也区分请求数量与请求总价值。
定义
定义 8.1.1
(正长度半开区间请求)
输入是 个请求组成的有限列表,各有不同身份。请求 占用 ,端点为有限实数,且 ;端点可以为负。两个请求兼容,是指占用集合不相交,等价于 或 。因此一个请求可以恰在另一个结束时开始。
可行调度是两两兼容的请求子集,按时间先后排列;相邻请求满足前者结束不晚于后者开始。其大小是接受的请求身份数量。区间完全相同而身份不同的两个正长度请求仍冲突。
最大调度的数量最多;极大调度则只是无法在保持可行的前提下再插入一个请求。若剩余问题至少有一个最大调度可以从某个选择开始,就称这个贪心选择安全。不要求每个最优解都包含它。
已有结束阈值 时,剩余列表由开始时间至少为 的请求组成。最初尚未选择请求,没有阈值;实现时以独立标志记录。把阈值初始化为零,会错误排除在零以前结束的请求。
定理/命题
引理 8.1.2
(最早结束可以交换为第一个选择)
对任意非空剩余列表,取结束时间最小的请求 ,平局任意处理。该列表存在一个最大调度,以 为第一项。若此前已有固定可行前缀,只要所有剩余请求都不早于前缀末尾结束时间开始,这个结论仍成立。
定理 8.1.3
(按结束时间扫描使接受数量最大)
按结束时间非递减排序,任意处理平局,然后扫描一次。接受首项;此后恰在请求开始不早于上一已接受请求的结束时间时接受它。空输入返回空调度。
所得调度数量最大。比较排序加扫描需要 次精确比较及索引操作;归并排序实现连同工作空间和输出需要 个存储字。
定理 8.1.4
(贪心调度始终不落后)
设贪心调度为 ,任意按时间排列的可行调度为 。对每个 ,贪心调度都存在第 项 ,且 。因此 。比较的是结束时间,不是请求身份或占用时间总长。
证明思路或证明
交换第一项,同时避免重复身份
证明
(替换最优解的第一项)
从非空剩余列表中取任意最大调度 。单个请求总可行,所以 至少为一。按 的定义,
若 已在该调度中,它只能位于第一项;否则位于它前面的首项会满足
矛盾。若 不在其中,把 替换为 。 时,下一请求的开始不早于旧首项结束,因而也不早于 。其余兼容关系不变; 时没有后缀需要检查。新调度的身份仍互异,数量仍为最大值。
若此前有固定前缀, 属于剩余列表,故它也不早于前缀最后结束时间开始。交换因此保留整个前缀。结论是存在一个遵从下一选择的最优解,而不是原最优解唯一。
证明透视
交换究竟保留了哪些条件?
证明完成三项独立任务,各自依赖不同假设。最早结束给出的不等式保留被替换首项之后的全部请求;与固定前缀的兼容性来自剩余列表的成员资格,而非最小性;排除 在后面出现的不等式链,其严格一步用到正长度。没有正长度, 可能位于最优解较后位置,替换后同一身份会被计算两次。只说 留下更多时间,只检查了三项中的第一项。
选定之后,准确识别更小的问题
证明
(剩余问题的对应与归纳)
接受 后,剩余问题恰由开始时间至少为 的请求组成。 后的每个可行后缀都在这个列表中;反过来,该列表的每个可行调度都可以接在 后。以 表示最大数量, 表示当前剩余列表,交换引理及这个对应给出
正长度保证更小的列表不含 自己,请求数量严格减少。对剩余请求数归纳,便证明反复选择最早结束者最优。空列表的最优值为零,提供基础情形。
这说明证明的结构:先证安全选择,再证精确的剩余问题对应。只知道最优解具有最优后缀并不够;很多问题有这个性质,某个贪心首步却仍然错误。后面的最短时长反例正是首步失败的情形。
旁注
先尝试推翻贪心规则
证明贪心规则之前,先用两三个区间尝试推翻它;下面每个反例最多只需五个区间。能通过小例子的规则,只是交换证明的候选,还不是定理。
为什么排序后一次扫描就执行了这个递归
证明
(扫描恰好作出剩余选择)
被接受请求的结束时间严格增加:下一项开始至少等于当前结束,而它自己的结束又严格晚于开始。因此,因开始过早而被拒的请求,以后也不会重新符合条件,可以永久丢弃。
任何能接在上一已选请求后的候选,其结束都严格晚于当前阈值,也不可能已经被选。扫描排序后的余项时,遇到的第一个符合条件的请求,就是所有符合条件者中结束最早的;此前被拒者不会重新符合条件。因此扫描准确执行已分析的剩余选择。同结束时间的任意顺序由交换引理保证安全。
另一种证明:与每个可行调度逐项比较
证明
(对竞争调度归纳证明始终不落后)
若比较调度非空, 存在且 ,因为 在整个输入中最早结束。假设 存在且 ;如果 存在,可行性给出
故 能接在 后。正长度使其结束严格晚于 ,因此它不可能是此前已选的贪心请求。仍有符合条件且未选的请求,算法不能停止;下一个最早结束选择 的结束不晚于 。每一步既证明下一项存在,也证明所需不等式。
归纳遍历比较调度的 项,得 。空比较调度无须归纳,数量界自动成立。
始终不落后的结论给出另一种有用不变量。它避免了一个不完整证明:只在两边都有项时比较结束时间,随后未经证明便假设贪心不会先结束。
概念视角算法
安全选择比看似合理的局部评分更强
最早结束有用,是因为交换后保留了整个最优后缀。最短时长或最早开始本身没有这样的保证。贪心正确性取决于目标、兼容规则与交换性质的结合;直觉上有吸引力的评分不能代替它们。
在明确输入约定下计算工作量
证明
(排序与扫描的成本)
比较归并排序反复拆分列表,再在线性工作量内归并两段有序列表;层数为对数量级。扫描时每个请求做一次兼容测试,输出至多 个身份。因此得到上述时间和存储界,也包含空输入的常数工作。若输入已按结束时间排序,只需线性扫描。
有限实端点采用精确比较。若端点为绝对值至多 的整数,在将寻址作为基本操作的索引数组模型中,每次端点比较及身份、索引算术可按 位计费。操作次数乘此位长给出算术及索引位成本。这里没有引入容差:把准确端点比较换成近似测试,会改变兼容性问题。
例题详解
例题 8.1.5
(端点相接、负时间与结束平局)
取 、、、、、、、。结束顺序为 ,其中 平局可倒转。
依次接受 、拒绝 、接受 、拒绝 、接受 、拒绝 、接受 、接受 ,得到五项 。若平局中 在 前,则得到同样五项的 。相邻结束和开始时间相等可以兼容。定理保证两者都最大;错误地从阈值零开始,就已经会漏掉 。
例题 8.1.6
(最早开始与最短时长都会失败)
对最早开始规则,取 ,另有四项 、、、。 严格最早开始,却挡住另外四项。只含 的单项调度是极大的,因为无法再加入任何请求,但数量一小于最大值四。
对最短时长规则,取 、、。 时长二,严格最短,却与另外两项都冲突。先选它再删除冲突者,只得一项;先 后 可得两项。局部节省最多时长,并不能保留最优后缀。
例题 8.1.7
(计请求数与最大总价值不同)
、 的价值各为一, 价值十。最早结束规则接受 ,数量二最大,却只获价值二;单项 价值十。把 换成 的交换在该步保留数量一,却降低价值,所以不是保值证明。
这也不意味着应始终选择价值最高者:令长区间 价值十,三个连续的长度二区间各值四。先选最重者只有十,三项短请求则共十二。本节证明的是单位计数目标;加权优化需要自己的论证。
常见错误
反例模式
去掉正长度会改变模型
若允许零长半开区间作为空占用集合, 与 不相交,两者在集合不相交的规则下可以同时接受。最早结束先选 ,阈值变为 1,而 的开始 0 较小,于是被拒,只得一项而非两项。正长度用于给不相交请求排序,也用于从剩余列表中排除已选请求;本定理明确要求它。
以下错误保留模型不变,却误读了定理的内容。
常见错误
(闭区间沿用半开区间的比较)
闭区间的端点规则不同: 与 相交。在该模型中,兼容测试必须是严格的 或 。换成闭区间却仍用非严格比较 ,会接受互相冲突的请求。
常见错误
(极大不是最大,最大也不唯一)
无法再加入请求的调度仍可能远非最优:第二个例题中的单项调度 是极大的,大小为一,而最大值为四。反过来,最优数量也不决定输出;第一个例题的结束平局已经给出两个不同的最优调度。
总结
最早结束选择安全,因为用它替换最优首项仍保留整个后缀及固定前缀。准确的剩余对应使归纳成立,排序扫描高效执行这些选择。始终不落后的另一证明同时保证贪心不会早于任意竞争调度耗尽候选。目标和端点假设都是关键。
练习
快速检查
(给 、、、,分别列出 两种结束平局顺序的贪心输出。解释数量为何相同,以及任一输出是否为唯一最优解。)
利用 与 重叠,为所有可行调度给出上界。
解答 · 答案
先选 ,即使它的时间为负。若 在 前,选 、拒绝 、选 ,得到 ;反之得到 。 在 上重叠,任意可行调度至多取其中一项,再加 ,数量至多三。两种输出都达界且不同,因此不唯一。半开约定下,端点相接不冲突。
快速检查
(有人说:任取请求、删除所有冲突者,再重复,最后得到极大调度,因此必最优。用例题给出反例,并说明需要证明怎样的交换结论才能修补这种推理。)
比较极大调度的大小与最大值。
解答 · 答案
先选 ,会删除其中四项相互兼容的短请求,返回极大单项调度;最优调度却包含全部四项。要证明贪心选择正确,必须说明某个最大剩余调度能在所需的首位包含该选择,同时保持此前前缀可行。本例中不存在这样的交换,因为每个含 的调度只有一项。最终无法再添加,不代表比替换选择后得到的答案更好。
快速检查
(某个可行竞争调度有七项,贪心已选四项,且 。证明 存在且 ,并解释正长度的作用。)
先证明 能接在 后。
解答 · 答案
竞争者第五项满足 ,所以 仍符合条件。正长度给出 ,而此前各贪心项的结束至多为 ,因此 尚未被选。剩余列表非空,第五个贪心请求存在;最早结束规则给出 。反复使用此论证,而不是预先假定两边项数相同,才证明一般的始终不落后结论。