CSCI3160 L19 集合覆盖、击中集与对数近似

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L19 集合覆盖、击中集与对数近似 · 原件 L19-Approximation-03-Set-Cover-Hitting-未核-隐藏.pdf（本地课件） p.1–20 定位：追踪尚未覆盖的元素数，证明贪心的几何下降。

p.1–3：集合覆盖选择的是集合【新】

p.1 为标题。p.2 全集 U 是输入集合族的并，选子族 C，使 U 的每个元素至少出现在一个被选集合中；目标最少集合数。

p.2 “every element of U appears in at least one set in C.”

p.3 的 U={1,…,12}，集合为 S1={1,2,3}、S2={4,5,6}、S3={2,3,4,5}、S4={7,8,9,10}、S5={10,11,12}、S6={8,9,10}。元素1、6、7、11分别强迫选S1、S2、S4、S5，这四个也足以覆盖，所以OPT=4。

p.4–6：收益只数新增覆盖

p.4 输入规模为各集合大小之和，不是仅集合个数。p.5 近似比要求输出集合数至多 $\rho OPT$。p.6 令 F 为尚未覆盖元素，每轮选与 F 交集最大的集合；已覆盖元素不再算收益。只按原始集合大小排序不是这个算法。

p.4 的规模明确为 $n=\sum_{S\in\mathcal S}|S|$；该优化问题 NP-hard，若 P≠NP 就不存在关于此规模的多项式精确算法。p.6 的完整循环为：

C = 空集合族；F = 全集 U
当 F 非空：
  在全部候选 S 中，选择 |S ∩ F| 最大的一个
  C 加入 S
  F = F 去掉 S 中的元素
返回 C

因 U 就是输入集合的并，每个未覆盖元素至少属于一个候选，每轮收益必为正；故最多 |U| 轮。每轮重新扫描全部成员出现位置即可算收益，时间 O(n)，朴素总界 O(n|U|)，是多项式。

p.7–9：原例完整执行与符号换名

p.7 一次合法运行如下：选S3新增4，F剩8；选S4新增4，F剩{1,6,11,12}；选S5新增2，F剩{1,6}；选S1新增1，最后选S2新增1。输出5个，最优4个，比为5/4。

上述第一轮完整的剩余集合为 {1,6,7,8,9,10,11,12}；倒数第二步后只剩 {6}，最后为空。每一轮新增收益依次为 4、4、2、1、1，总和 12，恰覆盖所有元素且每个元素只在首次被覆盖时计数。

p.8 的定理给出更强的数量上界 $t\le1+OPT\ln\lvert U\rvert$，进而得到比 $1+\ln\lvert U\rvert$。p.9 重新用 S1,…,St 表示“被选的第1至t个集合”，它们不是p.3固定名字的原顺序。定义 zi 为第 i 轮后未覆盖数，z0=U大小，zt=0，最后一轮前 zt−1≥1。

补充：原例的新增收益逐列核对。 第一次选 S3 后，元素 2、3、4、5 已被覆盖；S1 原大小 3，但只剩元素 1 是新增，收益降为 1。S2 也仅剩 6，收益 1；S4 的四个元素尚未覆盖，收益仍 4。这解释了第二步为何选 S4，不能沿用预先排好的原始大小顺序。

选择会改变别的候选收益，但不会改变这些集合本身的成员。实现可维护剩余元素的标记，重新计算交集；若使用增量计数，则需通过元素到集合的倒排关联表减去新覆盖元素的贡献，避免对同一元素减两次。

p.10–12：最优解中总有一个高收益集合

p.10 $z_i\le z_{i-1}(1-1/\mathrm{OPT})$

p.10 先提出剩余量逐轮下降的不等式；其平均收益依据在 p.12 给出。

p.11 展开到倒数第二轮，并使用 $1-x\le e^{-x}$：

取自然对数，0≤ln|U|−(t−1)/k，移项得 t≤1+k ln|U|。为何不展开到最后一轮？因为zt=0，不能取ln0，也得不到正下界。空全集直接返回空解；k=1时一轮覆盖，可独立处理，避免不必要的0次幂边界。原例k4，第一次实际剩8≤12×3/4=9，界不要求每轮刚好等号。

p.12 是这条式子的原因：最优解的 k=OPT 个集合合起来能覆盖目前 F 的全部 z 个元素，所以其中至少一个覆盖 z/k 个；交集有重复只会让总计数更大，不影响平均下界。已选集合对 F 收益0，那个正收益集合仍是候选。贪心至少取得这么多，于是剩余至多 z(1−1/k)。

进一步排除已选最优集合的期末证明见附录 A1。

p.13–15：击中集选择的是元素

p.13 为转场。p.14 给全集U和其子集族，要选 H⊆U 与每个集合有非空交集。p.15 中U={1,…,6}，12个要求集合分别为 {1},{1,3},{1,3},{2,3},{2,3},{2},{4},{4,6},{4,6},{4,5,6},{5},{5}。单点要求强迫1、2、4、5，因此最优H为这4点。重复要求不会改变最优值，但仍可作为不同输入条目。

p.16–18：相同结构，改变对数里的对象

p.16 延续输入大小与 NP-hard 性；该页沿用“set cover”文字，应按此段主题理解为 hitting set。p.17 最小化近似比仍是输出元素数对最优元素数。p.18 声称可转为集合覆盖，得到 $1+\ln\lvert\mathcal S\rvert$，这里对数是要求集合的个数，不是原全集元素个数。

p.19–20：把关联矩阵转置

图（p.19–20）：左侧12个要求集合，右侧6个元素，包含关系画一条边。元素：右点1连接左S1、S2、S3；右点3连接S2、S3、S4、S5。看什么：选右点击中所有左点，等价于让每个右点的左邻居集成为一个候选覆盖集合。

新全集 U′是12个左侧集合的编号。对原元素 e 建 A_e={编号j：e属于Sj}。选择 H 正好对应选择同样数量的 A_e；可行性和目标值一一对应，最优值也相等。完整转置为 A1={1,2,3}、A2={4,5,6}、A3={2,3,4,5}、A4={7,8,9,10}、A5={10,11,12}、A6={8,9,10}，恰好回到p.3例子。转置时每条包含关系只需改写一次，总成员出现次数不变，故转换为多项式时间；新全集大小是要求条目数12，这就是近似比中使用 ln|𝒮| 的原因。若原要求含空集，则击中无解，应先报告，不能硬套贪心。

五环破坏问题的覆盖建模见附录 A2。

本讲核心考点

• （A 级：Final-2025T1 Q6）用尚未选中的最优集合加强平均收益下界。
• （C 级 通识）推导剩余量的几何下降及自然对数近似比。
• （A 级：Final-2024T1 Q4）将固定长度环破坏转为覆盖，并核算新实例规模。

附录

A1 作业/往年题演练（非讲义内容）：Final-2025T1 第 6 题

题面（Final-2025T1-题目.pdf · Q6(a)(b) · p.3；扫描件，视觉读取；公式按原题重排）

p.3 “6. Let $C^{\ast}$ be an optimal universe cover for the set cover problem. Consider running the set cover algorithm discussed in the lecture. In particular, consider the moment right before the algorithm is to choose the i-th set $S_i$, having chosen already $S_1,S_2,\ldots,S_{i-1}$. Let $z_{i-1}$ be the number of elements in the universe that have not been covered by $S_1\cup S_2\cup\cdots\cup S_{i-1}$. Let $C=\{S_1,S_2,\ldots,S_{i-1}\}\cap C^{\ast}$, i.e., C includes all the sets of $C^{\ast}$ that ‘happened’ to have been selected by our algorithm so far.”

“(a) (2 points) Prove that $C\ne C^{\ast}$.”

“(b) (3 points) Prove that $S_i$ has benefit at least $z_{i-1}/\lvert C^{\ast}\setminus C\rvert$.”

题源：Final-2025T1-题目.pdf（本地课件） p.3 Q6。在第i轮前还有zi−1个未覆盖元素，最优族为C*，C={S1,…,Si−1}∩C*。要求证明(a) C≠C*；(b) 本轮收益至少 zi−1/|C*\C|。

若C=C*，此前已选齐一个最优覆盖，未覆盖数应0，与本轮仍需选集合矛盾。又因为C中的集合都已选，其对剩余F的交集为空，F只能由C*\C覆盖；这些非空候选中至少一个收益达到平均值。贪心选最大收益，故达到题求下界。这比把分母粗写成|C*|更强，但不改变前面标准证明的有效性。

回到正文：平均收益

A2 作业/往年题演练（非讲义内容）：Final-2024T1 第 4 题

题面（Final-2024T1-缺判断-题目.pdf · Problem 4 · p.3；扫描件，视觉读取；公式按原题重排）

p.3 “Problem 4 (10 marks). Let G = (V,E) be a simple undirected graph. A 5-cycle is a cycle with 5 edges. We say that a subset $D\subseteq E$ is a 5-cycle destroyer if removing the edges of D destroys all the 5-cycles in G, namely, $G'=(V,E\setminus D)$ has no 5-cycles. For example, if G is the graph below, there is only one 5-cycle acbdea; a 5-cycle destroyer is {{d,e}}, and so is {{d,e},{c,d}}.”

“Let $D^{\ast}$ be a 5-cycle destroyer with the minimum size. Design an algorithm to find a 5-cycle destroyer of size $O(\lvert D^{\ast}\rvert\cdot\log\lvert V\rvert)$ in time polynomial to $\lvert V\rvert$.”

图（题面，p.3）：五点无向图。 元素：边ac、ae、bc、bd、cd、ce、de。 看什么：唯一五环a–c–b–d–e–a要求至少删其中一条边；删除cd不会单独破坏这个五环。

题源：Final-2024T1-缺判断-题目.pdf（本地课件） p.3 Q4。five-cycle destroyer 是与图中每个五顶点环至少共享一条边的边集D，要求多项式时间输出 $O(\lvert D^{\star}\rvert\log\lvert V\rvert)$ 大小的解。

枚举所有五顶点环作全集U，至多 $O(V^5)$ 个。每条原边e对应包含它的五环集合A_e。选边击中每个环，正好等价于选A_e覆盖U，且最优值相同。运行集合覆盖贪心，选边数至多 $(1+\ln\lvert U\rvert)\lvert D^{\star}\rvert=O(\log V)\lvert D^{\star}\rvert$；五是固定常数，枚举与构造关联表仍为多项式。没有五环时直接返回空集，不计算ln0。

还可以利用每个环恰有5边给出更强常数近似：选任意剩余五环的全部5边，删除与它共享边的全部五环；被选环边集两两不交，任何破坏集必须为每个环各选一条不同边，因此输出≤5OPT。这一补充同样满足题目要求，但不是一般集合覆盖贪心的证明。

回到正文：击中集建模

来源与证据

• 本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。

• 原件：L19-Approximation-03-Set-Cover-Hitting-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。

• 版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。

• 发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。

• 既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无

• 缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。