CSCI3160 T12 集合覆盖与击中集应用

课程：CSCI3160 Design and Analysis of Algorithms 本讲：T12 集合覆盖与击中集应用 · 原件 T12-集合覆盖与击中集-未核-隐藏.pdf（本地课件） p.1–20 定位：辅导；把最大集合大小的保证讲清，再练习设施选址与排期的建模。

p.1–3 再看集合覆盖的对象【延伸 L19 p.2】

p.2 “Find a universe cover with the smallest cost.”

p.1 标题页。p.2 的宇宙 U 是所有必须覆盖的元素，输入集合族中的每个 S 都是可以选择的一个集合；代价是选了多少个集合。主讲的 L19 已说明这种无权版本。

题面（T12-集合覆盖与击中集-未核-隐藏.pdf · Example · p.3；集合按原页重排）

p.3 “An optimal solution is C = {S1, S2, S3, S4}.”

原页给 U={1,2,3,4,5,6,7,8}；S1={1,2,3,4}，S2={2,5,7}，S3={6,7}，S4={1,8}，S5={1,2,3,8}。选 S1、S2、S3、S4 覆盖全部八元素，代价 4。为什么不能三套？元素 4 只在 S1、5 只在 S2、6 只在 S3，这三套必须选；但三套都不含 8，必须再加 S4 或 S5。因此 4 同时是下界和可达的上界。

p.4–6 最大集合大小给出另一种上界

p.4 “add to C a set in S with the largest benefit”

p.4 每次按尚未覆盖元素的数量算 benefit，不按集合原大小。已知对数保证之后，这里改用 h 表示所有输入集合中的最大元素数。p.5 上例 h=4。

p.6 设算法总共选 t 套，每轮挑一个本轮新覆盖的元素作代表。代表不可能重复：它以后已不是新元素。所以 t 不超过宇宙元素数。最优覆盖的每套最多 h 个元素，若有 OPT 套，其覆盖总数不超过 h·OPT。于是

t\le \lvert U\rvert\le \sum_{S\in C_{\mathrm{opt}}}\lvert S\rvert\le h\,\mathrm{OPT}.

原页 p.6 用代表元素作双重计数的完整写法是

t=\sum_{i=1}^{t}1 \le\sum_{i=1}^{t}|\{S\in C^*:e_i\in S\}| \le\sum_{e\in U}|\{S\in C^*:e\in S\}| =\sum_{S\in C^*}|S|\le |C^*|h.

第一步因每个代表必被最优覆盖中的至少一套覆盖，第二步因代表互异、补加其余非负项；等号是按元素计数改成按集合计数，同一批包含关系只换了统计顺序。

求和会重复数到重叠元素，正好给出上界，不能把第二个不等号随意写成等号。这个粗保证只用了“每次至少覆盖一个新元素”；最大 benefit 的选择在主讲更强的对数分析中才发挥关键作用。

算一遍：上例先选 S1，剩 {5,6,7,8}；S2 新增两个，接着 S3 新增 6，最后 S4 新增 8，t=4。逐轮代表可取 1、5、6、8，四个互异。OPT=4、h=4，结论 4≤16 是有效但不紧的上界。

p.7–9 近似保证也要随建模翻译

p.7 “If h = O(1), then our algorithm achieves a constant approximation ratio.”

p.7 说，若每套最多固定常数个元素，h 保证就是常数保证；不是每个输入都有一个有限 h 就能叫常数近似。该页还指出能进一步分析到 1+ln h，但明确说证明不要求。p.8 是转入应用的分节页。

p.9 将 Vertex Cover 变成 Set Cover：宇宙是所有边；每个顶点对应一套“与它相接的边”。选这个集合就等价于选这个顶点，覆盖所有边的条件和代价完全保留。此时 h 是最大顶点度数。三角形中三套各含两条边，先取一套覆盖两条，再取另一套覆盖最后一条，得到两顶点覆盖。

两种已证上界都成立，可取较小者：1+ln 边数和最大度。简单图边数至多是顶点数的二次方量级，故前者也可写成 O(log 顶点数)。讲义提醒此法通常不如 L17 专用的二倍算法；本页练的是建模能力。

p.10–12 设施是集合，顾客是要覆盖的元素

p.10 “assuming the existence of at least one feasible facility set”

p.10 明确 R 与 B 各有 n 个二维点，epsilon 是正整数，目标输出设施数至多 OPT·O(log n)。输入红点候选设施 R、黑点顾客 B 和距离门槛 epsilon，选择尽量少的红点，使每个黑点距某个所选红点不超过门槛。图里虚线圆表示一个设施的服务半径，不是新的候选设施；没有数值坐标，不能从绘图比例虚构距离。

p.11 令宇宙为全部顾客；对每个红点 r 建立集合 Sr，收集距它不超过门槛的黑点。选 Sr 与开设施 r 一一对应，所需最优数量也相同，因此集合覆盖的保证直接变成设施数的对数保证。若某位顾客不在任何 Sr 中，就根本没有可行解；p.10 的假设排除了这种情况。

算一遍（数字是我为演示取的，讲义没给）：三位顾客 1、2、3，设施 A 可服务 {1,2}，B 可服务 {2,3}，C 只可服务 {1}。先选 A 后剩 3，再选 B，总共两个设施；没有单设施服务全部三人，故本例最优也是两个。建立全部集合需检查每对设施与顾客的距离，双方各 n 个时共 n² 对。p.12 是转向 Hitting Set 的分节页。

p.13–15 换成“每个要求至少击中一次”

p.13 “Find a hitting set H of the minimize size.”

p.13 的解 H 由宇宙中的元素组成，要求每个输入集合都与 H 相交；Set Cover 的解却由输入集合组成。原页拼写 minimize 保留，意思是最小化 H 的大小。若输入有空集合，任何 H 都击不中，须先判不可行。

p.14 给 U={1,2,3,4,5}，八套依次为 {1,4,5}、{1,2,5}、{1,5}、{1}、{2}、{3}、{2,3}、{4,5}。单元素要求 {1}、{2}、{3} 强制选 1、2、3；它们都击不中最后一套，必须另选 4 或 5。H={1,2,3,4} 大小 4，且由强制条件知不能更少。

p.15 的转换把“每个输入集合”看成一个待覆盖的要求。原宇宙里每个元素 e 提供一套 Te，包含所有含 e 的要求。选 e 等价于选 Te，所以转成 Set Cover 后的宇宙大小是原集合族的套数，保证为 1+ln 套数，不是 1+ln 原宇宙大小。

将 p.14 具体输入转置，五个候选覆盖集合是 T1={1,2,3,4}、T2={2,5,7}、T3={6,7}、T4={1,8}、T5={1,2,3,8}，下标表示被击中的要求编号。它们正好是 p.3 的五个集合，因此两个原例是同一个包含关系表的两个方向。

p.16–18 同一道设施问题的另一种看法

p.16 “How to cast the problem as an instance of the hitting set problem?”

p.16 再列相同设施输入，并不是换成另一个有收费、容量限制的选址模型。p.17 此次宇宙是红点候选设施；每位黑点顾客 b 产生一个要求 Sb，内含能服务它的所有红点。选一批红点击中所有顾客要求，便让每人至少有一个可用设施。圆此时以顾客为中心找附近设施，和 p.11 从设施出发看顾客是同一距离关系的两种方向。

沿用刚才补充的三顾客例子，三个要求是 {A,C}、{A,B}、{B}。必须选 B，再选 A 或 C 即可，总数 2，正好和 Set Cover 模型一致。p.18 解释保留两种问题名称的用处：实际题目有时直接写成“选项能完成哪些要求”，有时写成“每个要求允许哪些选项”，能识别两边便不用强行改变题意。

补充：把同一个设施例子写成关联表。 一个“是”表示这座设施能服务这位顾客：

顾客／设施	A	B	C
1	是	否	是
2	是	是	否
3	否	是	否

按列读，A提供顾客集合{1,2}，B提供{2,3}，C提供{1}，这是集合覆盖。按行读，顾客1要求选中{A,C}至少一个，顾客2要求{A,B}至少一个，顾客3要求{B}至少一个，这是击中集。转换只是交换“候选”和“要求”视角，实际被选设施以及数量完全不变。由此才可把近似保证带回应用，而不是仅因两个问题都出现集合二字就套公式。

自测：若增加“每座设施最多服务一位顾客”，原覆盖模型还完整吗？

不完整。原来选中B同时覆盖2、3，现在可能必须为二者分配不同设施。集合并集没有表示服务容量和分配冲突，需要新增约束、重新选算法；不能沿用原对数保证而不证明新模型的可行性对应。

p.19–20 排期与参数的最后一次翻译

p.19 “Find the smallest number of dates to schedule all events.”

p.19 有 t 个事件，每个事件 i 允许日期集合 Si，要用最少的不同日期安排全部事件。宇宙是日期，每个事件提供一个要求，选日期击中所有 Si。题目没有说一天最多一个事件，因此可以同日安排多事；擅自加容量限制就变成了另一个问题。

算一遍（数字是我为演示取的，讲义没给）：三个事件分别允许 {周一,周二}、{周二,周三}、{周三}。必须选周三，再选周一或周二；选周二、周三就够两个日期。三套没有共同日期，故一个日期不够。

p.20 问 Set Cover 的 h 在 Hitting Set 中对应什么。转换后一个集合 Te 的大小，是原元素 e 出现在多少个要求里，所以对应的是最大出现次数 f，而非原要求本身的最大大小。上例周二出现于两套、周三出现于两套，因此 f=2。算法保证为 f 倍；与已知的 1+ln 要求数同时成立，可取二者中较小的界。

考试角度：（A 级（扫描件，视觉读取）：Final-2024T1-缺判断-题目.pdf Q4，考的是把“选边破坏所有五环”转成覆盖模型）完整题面与过程见 L19 的往年题附录。

本讲核心考点

每轮代表元素互异，得到最大集合大小乘最优数量的上界（p.4–6；C 级）。
设施选址可用顾客作覆盖宇宙，或设施作击中宇宙（p.10–17；C 级）。
击中集的对数参数是要求套数，h 对应最大出现频率（p.15、20；C 级）。
1+ln h 的更精细证明被原件明确列为不要求（p.7；B 级）。

附录

本讲所需过程已在正文展开。

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：T12-集合覆盖与击中集-未核-隐藏.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：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。