为什么要近似
前面几节说明,许多优化问题是 NP 困难的,目前没有已知的多项式时间算法能对所有输入求出最优解。除非这些问题都能在多项式时间内精确求解,否则必须有所取舍。近似算法放弃的是最优性,而不是可证明性:它在每个输入上都以多项式时间运行,并附带一个已证明的界,说明答案与最优值最多相差多少。本节介绍两种基本的证明技巧。第一种把算法的输出与一个容易计算的最优值下界(极大匹配)作比较;第二种把总成本分摊到被覆盖的元素上,再与最优值比较(贪心集合覆盖)。本节假定读者已掌握本章前几节关于图和 NP 困难的定义。
定义
定义 4.6.1
(近似比)
极小化型的优化问题为每个输入 指定一族可行解,每个可行解有非负成本; 表示可行解的最小成本。算法 称为 -近似算法( 为常数),是指在每个输入 上,它以输入大小的多项式时间运行,输出一个可行解,并且输出的成本 满足
比值 也可以依赖输入规模,本节后半部分便是如此。近似比是对所有输入成立的陈述,所以算法在某些输入上碰巧得到最优解并不能证明什么;而它在某个输入上表现欠佳,只能给出其真实近似比的下界。
定义 4.6.2
(顶点覆盖、匹配与极大匹配)
设 为有限无向图。顶点覆盖是集合 ,使每条边至少有一个端点在 中。最小顶点覆盖问题要求大小最小的顶点覆盖。匹配是边集 ,其中任意两条边没有公共端点;若无法从 中再加入任何一条边而保持匹配性质,则称 极大。极大比最大要弱:极大匹配不能再扩充,但别处仍可能存在更大的匹配。
定义 4.6.3
(集合覆盖与调和数)
在最小集合覆盖问题中,给定有限全集 ()及集合 ,它们的并集为 。覆盖是一组下标 使 ,其成本为 。第 个调和数为 ;因为对 有 ,所以 。
以极大匹配求顶点覆盖
算法反复取一条未被覆盖的边,把它的两个端点都放入覆盖。
APPROX-VERTEX-COVER(G):
C = empty set; M = empty set
while G still has an edge uv:
add u and v to C; add uv to M
delete u, v and every edge incident to u or v from G
return C
定理 4.6.4
(顶点覆盖的二近似)
对任意图 ,算法在 时间内终止,集合 是极大匹配,输出 是顶点覆盖且 ,并且
证明
(以极大匹配得到二近似)
每次迭代至少删去边 ,所以循环至多执行 次。使用邻接表并为每个顶点设一个标记,每次迭代的时间与被删去的边数成正比再加一个常数,因此得到上述总时间。
当 加入 时,所有与 或 相连的边都被删去,所以之后加入 的边不会再用到 或 。因此 中的边两两不相交,。只有图中不再有边时循环才结束; 的每条边要么被加入 ,要么因为含有已在 中的端点而被删去。所以每条边都有端点在 中, 是顶点覆盖。若结束时还有边可加入 ,这条边的两个端点都不在 中,与上面的结论矛盾;所以 是极大的。
关于最优性,设 为最小顶点覆盖。 的每条边都有端点在 中,而不同的边有不同的端点,所以 至少含有 个不同的顶点:。因此 。
这个证明体现了一个一般模式:把一个可在多项式时间内算出的最优值下界()与输出的成本作比较。算法本身无须知道 。
概念视角组合
顶点覆盖是特殊的集合覆盖
由 构造一个集合覆盖实例:全集为 ,每个顶点 对应集合 ,即与 相连的所有边。集合 是顶点覆盖,当且仅当 ,所以顶点覆盖正是这个实例的覆盖,代价也相同。每个元素(边)恰好属于两个集合。匹配是一族两两不属于同一集合的元素,所以任何覆盖都要为每个元素各用一个不同的集合;这正是 的另一种说法。取匹配边的两个端点,就是取所有含该元素的集合。
贪心集合覆盖
贪心规则是反复选取含有最多尚未覆盖元素的集合。
GREEDY-SET-COVER(U, S_1..S_m):
R = U; J = empty list
while R is not empty:
choose j maximizing |S_j intersect R| (break ties by smallest index)
append j to J; R = R minus S_j
return J
定理 4.6.5
(贪心集合覆盖的调和数保证)
设 为覆盖的最小大小。贪心算法返回的覆盖大小至多为 。
证明
(贪心集合覆盖的调和数界)
终止性:由于所有集合的并集为 ,只要 ,就有某个集合与 相交,所以每次迭代至少移走一个元素,循环至多 次后以 结束;因此 是覆盖。
关键引理。 若仍有 个元素未被覆盖,则某个集合至少含其中 个。事实上,由 个集合组成的最优覆盖覆盖全部 个剩余元素,所以这 个集合含有的剩余元素(按重数计)至少有 个,由鸽笼原理,其中一个至少含 个。贪心所选集合的新元素数不少于该集合的。
分摊。 每当贪心选取一个覆盖 个新元素的集合,就给这 个元素各标价格 。所有价格之和等于所选集合的个数。把元素按被覆盖的次序排成 (同一次迭代覆盖的元素任意排序)。在 被覆盖的那次迭代开始时, 都尚未被覆盖,所以 。由关键引理,贪心覆盖了 个新元素,于是
对 求和,得 。
证明透视
为什么价格能把计数变成求和
证明把所选集合的个数转成对元素求和:给每个新覆盖的元素定价 ,总价格就等于 ,于是可以逐个元素证明上界。不显而易见的一步是元素的排列顺序。无论同一次迭代内怎样排序, 仍有 ,因为这只用到“在该次迭代开始时 都尚未被覆盖”。
最优值 只在一处出现,就是关键引理的鸽笼步骤,而且只作为“覆盖剩余元素的最优覆盖最多需要几个集合”的上界;这正是贪心已经移走一些元素之后论证仍然成立的原因。界 相加得 ,证明就此完结。没有关键引理的话,每个元素的价格都可能高达 ,只能得到毫无用处的界 。
例题
例题 4.6.6
(六个顶点的路径上的顶点覆盖)
设 为路径 ,边为 。按所列次序取边运行算法。取 :把 放入 ,删去 。剩下的第一条边是 :把 放入 ,删去 。接着是 :把 放入 。此时 ,,故 。集合 覆盖 (靠 )、(靠 )和 (靠 ),所以 ;又 ,故 ,这个次序下的比值恰为 。
结果取决于选边次序。若第一条边取 (删去 ),再取 (删去 ),则 ,,。两种输出都符合定理。
例题 4.6.7
(贪心集合覆盖未必最优)
设 ,,,。贪心首先选 (四个新元素,其余集合各三个)。此时 ; 覆盖 , 覆盖 ,各有一个新元素;平手时取 。然后 ,选 。贪心返回三个集合。而仅 已覆盖 ,所以 ,输出是最优值的 倍。定理只保证 ,即 ,与 一致。
例题 4.6.8
(此算法的因子 2 不能改进)
设 为完全二分图,两侧 各有 个顶点。 的每个极大匹配都是完美匹配:若 和 中各有一个未匹配的顶点,它们之间的边就可以加入。所以算法总是输出全部 个顶点。单是 已是顶点覆盖(每条边都有端点在 中),所以 。由定理 ,故 ,输出恰为最优值的两倍,对每个 都如此。因此这个算法的分析是紧的。
常见错误与细节
常见错误
(把近似比当成结构上的相似)
-近似是对成本的最坏情况保证,并不保证输出与最优解相似:六个顶点路径的例题中,两个输出所用的顶点不同,两者都不必与最优覆盖相似。
反例模式
每条匹配边只取一个端点
一个诱人的捷径是每条匹配边只取一个端点,这样覆盖的大小会减半。在路径 上, 是极大匹配:唯一的另一条边 与这两条边都有公共端点。若选 和 ,边 就没有被覆盖,所以这个捷径不成立。必须取两个端点:极大性只说明 以外的每条边都接触某个已匹配的顶点,而要覆盖那条边,无论它接触的是哪一个端点,这个已匹配的顶点都必须在 中。
常见错误
(极大匹配与最大匹配)
匹配必须是极大的,覆盖才有效,但不必是最大的。不等式 对每个匹配 都成立,所以证明对算法碰巧构造出的极大匹配同样适用。
常见错误
(剩余元素的最优值)
在集合覆盖的分析中, 是原输入的最优值。选了一些集合之后,对尚未覆盖的元素而言,剩余的最优值至多为 ,但可能更小;关键引理只需要上界 ,而这个方向是成立的。
调和数的界依赖 ,所以不是常数因子保证;本节也没有说明它是否是最好的可能值。
练习
快速检查
(在顶点为 、边为 的五边形上,按此顺序取边运行顶点覆盖算法。列出 和 ,并求 。)
圈上每个顶点至多覆盖两条边。
解答 · 答案
取 :把 放入 ,删去 。剩下 。取 :放入 ,删去 。再没有边。所以 ,,大小为 。顶点覆盖至少需要 个顶点,因为每个顶点至多覆盖五条边中的两条;而 覆盖 (靠 )、(靠 )和 (靠 )。所以 ,比值为 。
练习 4.6.9
(设 为图 的任意匹配。证明 的每个顶点覆盖至少有 个顶点,并说明为什么单靠这个不等式不能推出顶点覆盖算法的输出至多有 个顶点。)
核心
解答(3)
- 1
为每条匹配边选出一个在覆盖中的端点
设 为顶点覆盖。对 的每条边,选一个属于 的端点。
依据: 顶点覆盖在每条边上都有端点,当然也在 的每条边上有。
- 2
证明所选的端点互不相同
关键一步
中两条不同的边没有公共端点,所以它们给出不同的顶点。因此 至少含有 个顶点。
依据: 匹配中的边没有公共端点。
- 3
与算法的输出比较
这个不等式只给出 的下界 。算法的输出有 个顶点,大于 ,并且可以大于 :在六个顶点的路径例题中, 而 。
练习 4.6.10
(设 ,,,,,。运行贪心集合覆盖(平手时取下标最小者),并证明其输出是最优的。)
核心
解答(3)
- 1
运行贪心算法
是最大的集合,故取 ;此时 。新元素: 给出 (3 个), 给出 (2 个), 给出 (2 个), 给出 (2 个)。取 ;此时 ,第一个含 的集合是 。输出为 ,共三个集合。
- 2
证明没有两个集合能覆盖
关键一步
各集合的大小为 。两个集合要覆盖 ,大小之和至少为 。不含 时,最大的和是 。含 时,另一个集合的大小必须为 ,即 或 ;但 ,,所以这些配对至多覆盖 个元素。
依据: 下界 与贪心的输出相等。
- 3
得出最优性
因此 ,而贪心只用了 个集合,所以 ,贪心在这里是最优的。
快速检查
(在贪心集合覆盖未必最优的例题中(,,,),按元素被覆盖的顺序写出每个元素的价格,验证价格之和等于所选集合的个数,并对每个 验证 。)
贪心依次选 、、,而 。
解答 · 答案
贪心选 ,以价格 覆盖 ;然后用 以价格 覆盖 ,用 以价格 覆盖 。总和为 ,等于所选集合的个数。当 , 时, 的界 依次为 。价格 分别不超过 ,所以六个不等式都成立;例如 时 , 时 。
快速检查
(设一个有 个顶点的图,其边恰好构成 条边的完美匹配(没有其他边)。证明顶点覆盖算法输出的覆盖恰有 个顶点,并求 。)
利用下界 。
解答 · 答案
图的每条边都与其他边不相交,所以取一条边只删去这一条边,算法取遍全部 条边:。每个顶点覆盖都需要在这 条不相交的边中各取一个顶点,所以 ;每条边取一个端点即得大小为 的覆盖。故 ,,达到定理所允许的最坏情况。