动机
贪心算法作出选择后不再回头;动态规划保留可能有用的替代方案,求解一族相关子问题。两者都可能有效,但不能靠口号证明。贪心法须证明指定选择可以出现在某个最优解;动态规划则须证明状态记录了足够信息,描述一切相关的后续选择。
本篇把这些责任明确化。先在区间调度证明局部选择安全,再改变目标,展示原证明为何失效。加权调度与背包说明如何用递推式补回失去的信息。以下输入均有限,并允许空的可行选取。
定义
定义 2.3.1
(可行性、最优性与交换论证)
最优化问题指定可行解集合及须最大化或最小化的目标。贪心选择按局部规则挑选下一部分。交换论证证明,可把某个最优解修改成包含贪心选择,同时保持可行且目标不变差;还须说明选择后的剩余问题如何表示。
定义 2.3.2
(动态规划状态)
状态指定一个子问题及其值。递推式用较小状态及基本情形表示该值。最优子结构表示可由递推式所指定子问题的最优解组合出最优解。重叠子问题表示不同递归分支需要同一状态。记忆化按需要计算一次;制表法则按依赖次序计算各状态。
最优子结构不允许任意丢弃背景。例如禁止重复顶点的路径问题中,只有当前端点未必足以描述合法后续,因为已用顶点可能影响可行性。状态须保留影响未来可行性或成本的信息;但记录完整历史又可能产生指数个状态。设计时须兼顾充分性与状态数目。
定理 / 命题
定理 2.3.3
(最早结束规则解决无权区间调度)
给定 的区间 ,每次选取剩余相容区间中最早结束者,可得到数目最多的两两不重叠区间。端点可相接:在 结束者与在 开始者相容。按结束时间排序后扫描,时间为 。
定理 2.3.4
(加权区间调度递推式)
按结束时间非递减排序,区间权重 非负。令 为小于 且结束时间不晚于 的最大索引;若不存在则为零。若 是前 个区间可达的最大总权重,则
以二分搜索计算前驱索引后,在精确权重运算为常数时间的模型下,排序及制表总时间为 ,辅助空间为 。
证明思路或证明
证明
(最早结束:交换与剩余问题)
对贪心定理,令 是剩余区间中最早结束者, 是某最优调度按时间排列的第一个区间。以 取代 。由 ,该调度所有后续区间均不早于 开始,故也不早于 。替换仍可行,区间数不变,所以存在包含 的最优解。
选 后,只有开始时间不早于 的区间符合条件。若包含 的最优解之剩余部分不是此子问题的最优解,就能把较好剩余解接到 后面,矛盾。对符合条件区间数归纳,空集合显然,交换及剩余论证完成每步。实现只须排序一次,按结束次序扫描,当区间开始不早于上个已选区间的结束便接受。相同结束时间可任意打破平局,因为证明只用非严格不等式。
证明透视
交换保持的是什么
用较早结束的区间取代最优调度第一区间,保持与后面所有区间的相容性,也保持选取数目。贪心证明依靠这两点。加权目标失去第二点,替代区间可能轻很多。动态规划通过比较包含与排除两类,修补这个精确缺口,而非直接承诺交换。
证明
(加权递推式:排除或包含最后一个区间)
对加权式,依是否包含区间 ,把前 个区间的可行解分两类。不含者至多为 ,而此值可达。若含 ,其他已选区间必于 或之前结束:其结束时间不晚于 ,而正长度区间不可能放在 后方又在它之前结束。这些符合条件的较早区间恰为截至 的前缀,最佳值为 ,接上 可达 。两类涵盖全部可能,取最大即证式子。
引用索引都小于 ,所以按递增索引制表合法。朴素递归可能反复求同一索引,存储每个值可避免重复。前驱已知后,每个状态只作常数工作,最多 个状态;排序及二分搜索给总时间。若权重是长整数,应加入位运算成本,不能默认常数。
重建一个解,而非只求值
表格记录最优值,但用户可能需要实际区间。从 开始,比较 与 。选前者便略过 ,移到 ;选后者便输出 ,移到 。平局可用一致规则任选。每次索引下降,最多 步终止。递推式证明保证选中分支可最优完成;倒转输出列表即得时间次序。
只有值表未必错,但只解决求值版本,规格须区分所需输出。反之,若每个状态只存一个任意贪心部分调度,就会失去动态规划用来保证正确的方案比较。
概念视角结构
把加权调度看成最长路径
取顶点 与两类边:长度为零的 ,以及长度为 的 。从 到 的路径恰好为所选的区间使用第二类边进入 ,而且要先经过结束时间不晚于 的区间,才会再到达 。因此路径长度就是一组相容区间的总权重,每组相容区间都对应一条路径, 就是到 的最长路径长度。重建的回溯就是把这条路径倒过来读。
零一背包与数值状态参数
命题 2.3.5
(零一背包递推式)
设物品 的正整数大小为 ,非负价值为 ,容量 为非负整数,每件最多取一次。令 为只用前 件且总大小不超过 的最佳值。基本值 ;由大小为正,。若 ,则 ;否则
证明
(零一背包:排除或包含最后一件物品)
仍把可行解分为不含及包含最后物品。包含时移除它,留下只用较早物品、容量为 的可行解;较差剩余解可换成最优者。因此每分支可达,也上界所有解。引用第 行至关重要,它防止重复取第 件。
表有 个状态,需 次算术运算及空间; 时惯写为 。只求值可用 空间:每件物品按容量递减更新。处理 时,较小容量仍存前一行值,故包含分支不能重用当前物品。递增更新会解另一个允许重用的式子。若要重建全部物品,须保留决策或另证重建方法;一行压缩值不自动包含那些决策。
由二进制 只有对数个比特, 是伪多项式,不是对编码长度的一般多项式界。若 对该长度为指数,表格也为指数。动态规划是设计方法,并非多项式时间保证。
另一个问题:恰好装满
上面的状态允许留下空位。如果要求总大小恰好为 ,空选就不是每个容量的可行答案。令 为只用前 件、总大小恰为 的子集的最大价值;若不存在这样的子集,记为 。因此 ,但对每个 都有 。仍假设大小为正整数,按是否选第 件穷尽分类,得到
证明
(恰好装满的递推式)
每个子集恰属于选或不选一类;从恰好装满 的选取中移去第 件,前一行就恰好装满 。反过来,每个可达前驱都能构造相应方案;有限价值加上 仍表示不可达。对 归纳,既得到表中数值,也得到不可达状态。因为不超过 的方案按确切大小分组,。
编程时应先检查前一状态能否到达,再做加法;不要直接给有限哨兵加值,以免溢出或误胜过真实解。
例题 2.3.6
(剩余容量与无法恰好装满)
物品为 与 时,可能的子集大小只有 ,所以恰好大小 不可达;但容量最多为 的最优值是 ,取第一件后还余两个单位。恰好大小 可取两件,得 。价值为零也不能混同于不可达:若只有物品 ,恰好大小 可达且价值为 ,恰好大小 却不可达。把两者都初始化为零,就丢失了这个区别。
压缩成一行时,仍可按容量递减更新,但不可达项必须先置为 ,加法前也要检查前驱是否可达。结果给出最优值或不可达,不会自动给出所选子集。保留每件物品、每个容量的决策(包括可达性和一致的平局规则)才可据此重建;把数值哨兵当作真实选择可能凭空造出子集。状态数与对数值 的伪多项式依赖不变。
阅读依赖图
可把每个状态视为顶点,向它依赖的状态连边。合法计算次序先放依赖项:加权调度只依赖较小索引,背包只依赖前一行。这种无环结构提供归纳,证明每个表值等于其定义的值。若式子引用自身却没有较小状态,就需要额外推理,不能直接写循环求值。
设计新动态规划时,先用一句话精确定义一个状态、指定参数范围,再从可行解推导各类。接着检查基本情形、计算次序、状态数、每状态工作及重建。这些检查处理不同错误:正确式子可能以错误次序实现;正确表格也可能被错估状态数。前驱计算等前处理亦可能主导总成本,须一并计入。
例题详解
反例模式
加入权重后,最早结束法会失效
断言:最早结束法同样使总权重最大。取 权重一与 权重一百。最早结束法选择先结束的 ,并因两者重叠而阻挡 ,总权重为一;只选 则得一百。无权的交换是把某区间换成较早结束的区间:它保持相容性与区间数目,却不保持权重。修正方法是加权递推式,它比较包含与排除两种情形。此反例指出失效的证明步骤,并非说所有贪心算法在所有加权问题都失败。
例题 2.3.7
(有实际取舍的加权表)
按结束次序取 权重三、 权重六、 权重四,前驱为 。表为 。重建选第三及第一区间,相接端点相容。只选个别最重者会得到六,而非七。
例题 2.3.8
(压缩背包的更新方向)
只有一件大小二、价值三的物品,容量四,零一最优值为三。若从全零行递增更新,先把容量二设为三,再于容量四使用这个新值,便得六,错误重用同一物品。递减更新先处理容量四,读到容量二的旧零值,正确保留三。
反例模式
按单位大小价值贪心对零一背包失效
一个诱人的规则是按价值与大小之比从大到小取物,只要放得下就取。容量为 ,物品 ,比值依次为 。此规则先取 ,剩下四个单位已放不下任何一件,价值为 ;两件大小为五的物品却能一起放入,价值为 。此规则只在物品可以分割时才最优;递推式处理的是整件取或不取的选择。
常见错误
常见错误
(忽略目标的交换论证)
交换论证须保持可行性与目标,并解释剩余问题;只说所选区间短或早并不足够。反例也须符合所有假设,包括正长度及端点约定。
常见错误
(把按数值容量建的表当作多项式时间)
按数值容量建表可能隐藏对位长度的指数依赖。当 时,背包表有 个状态,而 的二进制编码只有 位。界 是伪多项式的。
常见错误
(压缩行时没有追踪读取的是哪一行)
空间优化须保持每个读取值所属的逻辑行。对只有一件大小二、价值三的物品且容量为四,递增的原地更新会得到 ,等于把该物品用了两次;正确值是 。
动态规划式须有涵盖所有可行解的上界论证,也须构造能达到每个候选值的解。只数状态会漏掉转移工作:代价是状态数乘以每个状态的工作量。
总结
贪心调度有效,是因为交换可把最早结束选择放进最优解而不减少数目。权重破坏此交换,递推式便保留包含与排除两种方案。加权调度及零一背包展示状态意义、依赖、重建,以及多项式与伪多项式的区分。
练习
快速检查
(用严格正长度区间,反驳无权调度“先选最短区间”。)
解答 · 答案
取 。最后一个唯一最短,选它会阻挡另两个,只得一而非二。半开约定允许前两区间端点相接。
练习 2.3.9
(区间 的权重依次为 。计算前驱索引、值表与一个最优调度。)
核心
解答(3)
- 1
计算前驱索引
依据: 区间已按结束时间 排序, 是结束时间不晚于 的最大较小索引。
- 2
填写值表
关键一步
- 3
回溯得到最优调度
在状态四,包含给出 ,所以选区间四并移到 。在状态二,包含给出 ,所以选区间二并移到 。状态一则选区间一。这三个互相相容的区间权重为 ,超过单独一个权重为七的区间。
快速检查
(若允许负价值但仍可空选,解释零一背包式为何仍正确。)
解答 · 答案
包含与排除仍分割全部可行解,每个分支仍可达,所以不论价值的正负,递推式都算出真正的最大值。空选值为零,因此最大化时不必选负价值物品。大小为正只用于基本值 ,以及使 成为严格较小的容量,递减的原地更新尚未覆盖它。
练习 2.3.10
(面额为一、三、四。说明反复取最大可用硬币来凑六并不最优,并为一般的非负目标推出最少硬币数的递推式。)
综合
解答(4)
- 1
否定最大硬币规则在目标六时的最优性
贪心取四、一、一,用三枚硬币;三加三只用两枚。
- 2
定义状态
令 为凑成总额 所需的最少硬币数,。因为有面额为一的硬币,每个目标 都可行。
- 3
按最后一枚硬币分类
关键一步
把剩余部分换成 的最优解不会增加枚数,而在这样的最优解后加上该硬币就达到候选值。因此对 ,
依据: 每个方案的最后一枚硬币都是某个允许面额 ,剩下目标 。
- 4
按目标递增的次序计算
每个值只用较小的值,所以算到所需目标只需对该数值目标做线性次数的算术运算;对二进制编码的目标,这是伪多项式界。