算法设计技巧既是组织计算的方式,也是组织证明的方式。贪心算法需要一个理由,说明某个局部选择可以被永久确定下来。分治法需要相互独立的更小子问题,以及正确的合并步骤。动态规划需要子问题的值保留后续决策所需的全部信息。掌握这些证明义务,比死记一串算法名称更有用。
动机
假设一间会议室同一时间只能举办一项活动。每项活动都有开始时间和结束时间。如果所有活动价值相同,选择结束得早的活动看起来是明智的,因为这样为将来留下了更多可用时间。然而,如果活动的价值各不相同,一项短小而价值低的活动可能会挡住一项价值高得多的活动。输入对象几乎没有变化,但目标函数的改变足以使贪心证明失效。
带权调度将引出动态规划。按结束时间对活动排序后,会出现一个有用的边界:选定某项活动之后,所有与之相容的较早活动都位于排序列表的某个特定前缀之中。因此,一个子问题可以用一个前缀下标来概括。如果不能识别出这种充分的状态,“试试动态规划”就只是一句口号。
排序本身提供了分治法的例子。我们可以分别对两半独立排序,再合并两个已排序的输出。证明的核心并不在于每次递归调用的规模都更小,那只能说明算法会终止。正确性还需要一个合并不变式,说明每一个被选出的下一个元素确实是全序中的下一个元素。
定义
定义 3.1.1
(活动、相容与两种目标)
活动 占用一个左闭右开区间 ,其中 。一项活动恰好在另一项活动开始时结束是允许的。两项活动的区间不重叠时,称它们相容。无权调度问题要最大化所选活动的个数;带权版本则给每项活动指定非负整数权重 ,并最大化所选活动的权重之和。空选择总是可行的。
定义 3.1.2
(前驱下标与前缀最优值)
将活动排序,使 ,结束时间相同时按任意固定规则决定先后。对于带权调度,定义 为满足 的最大下标 ,若不存在这样的下标则取零。由于 ,每一项与 相容的较早活动都属于以 结尾的前缀。令 为仅使用活动 时所能得到的最大权重,并规定 。
定义 3.1.3
(最优子结构)
如果在固定了外围的选择之后,较大问题的最优解使用了相关较小问题的最优解,就称该问题具有最优子结构。这一性质需要证明:若较小问题的解不是最优的,将其替换后必须仍保持可行性,并使整体目标值得到改善。
定义 3.1.4
(比较排序与操作计数)
比较排序算法只通过比较输入的键来获知顺序。对于下面的下界,键两两不同,且所有排列都可能出现。对于所述的上界,一次比较或一次基本算术运算算作一次操作。当数值变大或输入坐标的编码很长时,位复杂度可能还需要额外的因子。
定理/命题
定理 3.1.5
(最早结束时间对无权调度是最优的)
在与已作选择相容的活动中,反复选取结束时间最早的活动。所得的相容集合具有最大基数。本定理针对无权目标,以及长度严格为正的左闭右开区间。
定理 3.1.6
(带权调度的递推式)
对 ,
在排序并求出所有前驱下标之后,该表可按下标递增的顺序计算,并且可以沿着取得最大值的选择重构出一个最优集合。
两者的区别在于承诺。贪心算法永久地选定第一项活动,因为交换论证证明了存在一个最优解包含这一选择。动态规划则同时保留“包含”与“不包含”两种可能,直到比较过它们各自可达到的最优值。它并不显式枚举每一种选择,因为许多选择所需要的是同一个更小前缀的最优值。
命题 3.1.7
(归并排序正确,且使用 次比较)
归并排序返回输入的一个有序重排,对 个键共进行 次比较。数组实现使用 的额外存储空间。
定理 3.1.8
(比较排序需要 次比较)
任何在 个互不相同的键的所有排列上都正确的确定性比较排序算法,在某个输入上至少作 次比较,而 。
证明思路或证明
证明
(交换最优解的第一项活动)
设 是全局结束时间最早的活动,并取一个按时间顺序排列的无权最优调度。若它非空,记其第一项活动为 ,并将 替换为 。由于 ,所有后续活动(其开始时间至少为 )仍与 相容。因为 是第一项,所以没有需要照顾的更早活动。该替换保持所选活动的个数不变。因此存在一个以 开头的最优解。其余活动必须在 或之后开始,对这个更小的问题可递归地应用同样的论证。每次选择至少移除一项活动,所以该过程终止并得到最优解。空实例是显然的。
证明透视
交换论证在哪里用到各项假设
关键一步是从任意一个最优解出发,只改动它的第一项活动。这样做是合法的,原因有三。由于 的结束时间不迟于任何活动,所以 ,最优解的每一项后续活动都在 或之后开始,因此也在 或之后开始。这里左闭右开区间很重要:一项活动恰好在另一项活动结束时开始,仍然相容。区间长度严格为正,使“按时间顺序的第一项”有明确含义。
目标函数只在一处出现:替换是一项换一项,所以个数不变。对带权问题,替换还需要 ,而没有任何条件保证这一点。论证对活动个数作归纳而完结:选定 之后,剩下的问题由在 或之后开始的活动组成,活动个数更少,在其中求得的最优解与 合并,就是整个实例的最优解。
证明
(包含或不包含最后一项活动)
对于带权调度,按是否包含 来划分前缀 中的可行调度。不包含 的调度,其最大值为 。包含 的调度只能含有在 之前结束的较早活动,这些活动都位于前缀 之中。它们其余的选择可以被替换为该前缀的一个最优解,而不会产生重叠。因此其最大值为 ,且两个候选值都是可行的。取二者的最大值即证明了等式。由于 ,按下标递增的顺序求值时只会用到已经算出的值。
证明
(重构沿着取得最大值的分支进行)
重构时,从 开始。若不包含分支取得 ,则移至 。否则包含 ,并移至 。出现平局时可以任选一边,只要所选分支取得最优值即可。下标严格递减,所以该过程终止。递推式保证累计所选的权重等于原问题的最优值,而且每次包含操作都移到一个相容的前缀。这就证明了输出的集合本身(而不仅仅是它的目标值)是正确的。
证明透视
为什么小的状态就足够
前缀下标之所以有效,是因为选择活动 只通过一个结束时间的边界来限制较早的选择。我们不需要记住被拒绝活动的整个历史。在另一个具有多个资源或额外依赖关系的调度问题中,前缀下标可能丢掉关键信息。只有在证明了状态描述了所有剩余约束之后,递推式才算得到论证。
证明
(合并保持有序前缀,逐层计算成本)
对于归并排序,把列表分成长度几乎相等的两部分,递归地对它们排序,然后合并。合并期间保持如下不变式:输出是有序的,并且由已从两个有序输入中取出的最小元素组成。当前较小的队首元素不大于任一输入中的任何剩余元素,把它追加到输出中即保持该不变式。一旦某个输入耗尽,另一个输入的其余部分可按原顺序直接追加。每个元素恰好被取出一次,因此合并的代价是线性的。对列表长度作归纳即证明排序的正确性,而递归输入逐步变小则证明终止性。
在递归的每一层,各子列表的长度之和至多为 ,而在到达单元素叶子之前,树的高度至多为 。每层的合并工作是线性的,因此对 共需 次操作。这种按层计算的论证无需假定输入长度恰好是 2 的幂。使用辅助数组的实现需要 的额外存储;而不必要地复制数据的朴素实现,其常数与存储行为可能有所不同。
证明
(计算判定树的叶子)
比较模型的下界解释了这一代价为何重要。互不相同的键共有 种可能的顺序。确定性的二叉比较判定树至少有 个叶子,所以某条路径的长度至少为 。对 ,阶乘中至少有 个因子不小于 ,从而当 增大时得到 的界。这是比较排序的最坏情形下界,并不适用于利用额外信息(例如位数有界的整数数位)的算法。
例题详解
例题 3.1.9
(同一输入,两种目标的计算)
取活动 、、、、,权重分别为 。按结束时间的顺序恰好就是上面列出的顺序,前驱下标为 。带权表为 ,随后依次是 。回溯选出 ,然后是 ,再是 ,总权重为十七。最早结束的贪心算法在这里也选出 ,但它们在这个例子上一致,并不能证明贪心算法能解决带权问题。
反例模式
权重不同时,最早结束的贪心会失败
人们可能预期,一条对活动个数已证明为最优的规则,对最大化权重也依然最优。取两项重叠的活动: 权重为一, 权重为一百。最早结束的贪心算法取 ,它与另一项冲突,所以其值为一;而单独一项 是可行的,其值为一百。表格的结果一致:前驱下标为 ,所以 ,。无权情形的交换证明在替换第一项活动时仍能保持个数,但无法保持总权重。证明责任的失败恰好指明了究竟是哪一条定理不再适用。修正的方法就是递推式,它比较两个分支,而不是提早承诺。
例题 3.1.10
(带有明确平局约定的合并)
合并有序列表 与 。每次取较小的队首元素,并在相等时选择左边的队首,得到 。如果键带有原始位置,则在键相等时选左半部分,可以保持它们跨越两半的原有顺序,因此归并排序可以是稳定的。稳定性是有序性之外的附加性质,应当从平局约定出发加以证明,而不能仅凭“合并”一词推断。
例题 3.1.11
(表中的平局与重构)
取 权重五, 权重五, 权重十。按结束时间排序, 与 的平局以把 排在前面来决定,活动依次为 。前驱下标为 ;,因为 ;,因为 。于是
在 时两个分支打成平局,重构时可以任选一边。取不包含分支,移至 ;那里不包含分支只得 ,所以包含 ,并移至 ,再包含 :所选集合是权重十的 。若在 取包含分支,则选出同样权重为十的 。两个输出都是最优的; 与 在边界点 相接而不重叠,这正是左闭右开约定的作用。
排序需要 次比较,而对已排序的结束时间进行二分查找,可在 次比较内求出所有 。随后动态规划表与重构共使用 次算术运算和 个存储项。若每个权重至多有 位,则每个表项的值至多是最大权重的 倍,至多需要 位。在位模型下,算术阶段并非常数代价。端点比较的代价同样取决于时间的表示方式;关于操作次数的陈述不应隐藏这一选择。
常见错误
常见错误
(最优子结构不等于贪心证明)
最优子结构本身并不能证明某个贪心规则有效。动态规划可以利用最优子结构,同时保留多个可能的第一选择。贪心算法对其特定的永久性决策,需要更强的交换论证或“保持领先”论证。
常见错误
(遗漏了约束的状态)
不要用遗漏了某项约束的状态来做记忆化。例如,如果递推式只按剩余活动的个数编号,就往往会因为忘记已经施加的结束时间边界而失败。活动个数相同的两个子问题,可行的调度可能不同。
常见错误
(递推式还不是高效的算法)
递推式的存在也不能保证实现是高效的。直接递归地计算带权调度,可能会多次重复访问同样的前缀。用表格则每个状态只计算一次。反过来,一个递推式未经证明的大表格,可能高效地算出错误的答案。
总结
交换论证为安全的贪心承诺提供依据。分治法把输入分成相互独立的更小部分,并证明合并步骤。动态规划确定充分的子问题状态,通过穷尽各种情形证明递推式,并避免重复计算。正确性、重构、终止性与代价模型,是算法说明中彼此区别的不同部分。
练习
练习 3.1.12
(证明:先选最短的区间,不一定能使相容活动的个数最大。)
基础
解答(3)
- 1
选取区间
取 、 和 ,长度分别为 、 和 。
- 2
执行最短优先规则
最短的区间是 。它与 相交于 ,与 相交于 ,所以选了它之后,没有其他活动相容。该规则只选出一项活动。
- 3
与最优解比较
区间 与 相容,因为前者恰好在后者开始时结束。可以选出两项活动,所以最短优先并非最优。持续时间短与结束时间早确实是不同的贪心规则;最早结束的规则会先选 ,再选 。
练习 3.1.13
(对区间 、、,权重为 ,计算带权表,并给出一个最优集合。)
核心
解答(3)
- 1
求前驱下标
结束时间已按 排好。。对 , 而 ,所以 。对 ,, 而 ,所以 。
- 2
按下标递增填表
关键一步
- 3
重构一个最优集合
在 时,不包含分支取得 ,所以移至 。那里不包含分支只得 ,所以包含 ,并移至 。最优集合是 ,权重为 。两侧的区间虽然相容,但总权重只有八,所以最大化个数解决的是另一个目标。
练习 3.1.14
(对于面额为一、三、四的硬币,证明在金额为六时,反复取尽可能大的硬币会失败。并给出求最少硬币数的正确递推式。)
核心
解答(4)
- 1
执行贪心规则
贪心先取 ,再取 ,再取 ,共三枚硬币。但 只用两枚,所以对金额六,贪心并非最优。
- 2
写出递推式
关键一步
依据: 每个非空的解都有最后一枚硬币,删去它就得到较小金额的一个解。
- 3
在较小的金额上检验递推式
,,,,,,与 相符。
- 4
论证正确性
删去最优解的最后一枚硬币 ,得到 的一个解,它本身必须是最优的,否则替换它就能改进整体。反过来,把 附加到 的最优解上是可行的。面额为正,使每次引用的金额都更小;面额一的存在则保证每个金额都能凑出。
快速检查
(解释为什么排序的下界与对 中整数的计数排序并不矛盾。)
想想计数排序除了比较之外还用了什么信息。
解答 · 答案
计数排序利用整数的取值去索引计数,并利用了有界的键域。它所用的信息并非仅仅通过输入键之间的二叉比较获得,因此比较判定树的假设并不适用。其成本包括键域的大小,通常为 ,当 很大时这个成本可能很大。