CSCI3160 Special 14：Hitting Set、五环破坏与最远点中心
原件：Sp14 题目（本地课件） p.1；两个图已视觉核对。 每题先题解后解析。Q2原题注明来自2022 Fall Final，其余不据此推断考试范围。
Problem 1：用集合覆盖表达单词命中
题解
新宇宙是十个单词本身。对每个字母c建立集合T꜀，包含所有出现c的单词；选字母命中每词，等价于选这些T꜀覆盖十词，目标数量不变。
具体解析
完整候选表如下：
| 字母 | 覆盖的单词 |
|---|---|
| a | arid、dash、drain、heard、slate、snare、thread |
| d | arid、dash、drain、heard、thread |
| e | heard、nose、slate、snare、thread |
| h | dash、heard、shun、thread |
| i | arid、drain |
| l | lost、slate |
| n | drain、nose、shun、snare |
| o | lost、nose |
| r | arid、drain、heard、snare、thread |
| s | dash、lost、nose、shun、slate、snare |
| t | lost、slate、thread |
| u | shun |
例如选a与s，可以命中全部词：a覆盖大量含a的词，剩下lost、nose、shun都含s。没有单个字母同时出现在全部十词，表中每行均不足十个，所以本例最小命中集大小2。题目只要求归约，这个数值是额外核验。
与Special13 Q1相反，那里选的是单词覆盖字母，这里选的是字母覆盖单词。关联关系相同，但决策对象与宇宙互换了。
Problem 2：破坏所有五环的对数近似
题解
枚举图中全部简单五环，作为集合覆盖的宇宙U；每条原边e对应集合Sₑ，包含经过e的五环。用贪心集合覆盖选若干Sₑ，删掉对应原边，即得大小O(OPT·log|V|)的五环破坏集。
具体解析
删除边集D能破坏每个五环，当且仅当每个五环至少包含一条D中的边，也就是对应集合覆盖U。删边不可能创建新环，所以只需覆盖原来存在的五环，不用每次重枚举来防止出现新对象。
设n=|V|，枚举5个互异顶点的有序序列并检查首尾闭合，O(n⁵)次常数检查（邻接矩阵）；去掉旋转和反向重复即可，或保留重复约束也不影响正确性及多项式规模。五环数N≤n⁵，每个环恰给五个边集合添加元素。贪心保证(1+ln N)OPT≤(1+5ln n)OPT，即所求界。没有五环时直接返回空集，不对ln0做运算。
题面示例图边为ac、ae、bc、bd、cd、de，五环a,c,b,d,e,a中每条边删一条都能破坏该环；图中三角形b,c,d不是本题必须破坏的对象。不能误归约成“破坏所有环”的反馈边集问题。
Problem 3：k=3，首中心f时的第二、第三中心
题解
第二中心a=(2,2)，第三中心j=(9,2)。选择顺序为f、a、j。
具体解析
原图点坐标为a(2,2)、b(3,3)、c(4,2)、d(4,8)、e(5,6)、f(6,7)、g(7,4)、h(8,3)、i(9,4)、j(9,2)。比较平方距离即可，无需开根号。
| 点 | 到f的距离平方 | 到{f,a}中最近中心的距离平方 |
|---|---|---|
| a | 41 | 0 |
| b | 25 | 2 |
| c | 29 | 4 |
| d | 5 | 5 |
| e | 2 | 2 |
| f | 0 | 0 |
| g | 10 | 10 |
| h | 20 | 20 |
| i | 18 | 18 |
| j | 34 | 34 |
第一列最大41，对应a。加入a后，对每点取到f、a两个距离的较小者，第二列最大34，对应j。不能第三步只找离a最远的点，也不能对已有中心距离取最大；目标是选“离最近中心仍然最远”的点。
例如c离f平方29看起来远，但离a只平方4，已被新中心照顾，所以第三轮优先级下降；j距f平方34、距a平方49，较近也仍是34，因此应选j。
第三中心选完后还要更新一次，才能报告覆盖半径。 在 Q3 的表上加入 j，用它到各点的平方距离再取 min，最终按 a 至 j 的平方最近距离为
例如 g 到旧中心最近平方距离 10，到 j 为 ，故改为 8；h 从 20 改为 2。最大值是 g 的 8，所以本次三个中心的真实半径为 。选第三中心前表中的 34 是两中心时的半径平方，不是最终结果。
自测：既然选择可用平方距离，二倍证明能否直接把平方距离当度量？
不能。平方距离通常不满足三角不等式；证明用欧氏距离得到 。若目标改写成半径平方，只能由此推出 。比较次序的等价，不等于近似倍数也相同。
Problem 4：推广到三维并证明二倍界
题解
输入三维点集P、整数1≤k≤|P|，选k个输入点作为中心，最小化所有点到最近中心的最大欧氏距离。仍任选首中心、反复加入最近中心距离最大的点，得到二倍近似。
具体解析
三维欧氏距离为平方坐标差和再开根号，满足三角不等式。设贪心最终半径r，取最终最远点q；k个中心加q共k+1点，任意两点距离至少r，因为后来点选入时的最近距离不小于最后半径。
最优k中心半径R覆盖这k+1点，至少两点落在同一个最优中心的R球内。三角不等式使这两点距离≤2R，于是r≤2R。证明只用了三角不等式和鸽巢原理，没有用平面角度或二维坐标，所以直接推广到三维，甚至一般度量空间。
若r=0，结果已经最优；有重合点时仍选不同输入记录，距离可以为0，不影响不等式。自取三维共线点(0,0,0)、(1,0,0)、(3,0,0)，k=1首选0时半径3，最优中心1半径2，满足3≤4。
Problem 5：实现O(nk)
题解
保存每点当前到最近中心的距离D[p]。新中心c加入后，对所有点做D[p]=min(D[p],dist(p,c))；再一次扫描找最大D的未选点。每轮O(n)，k轮O(nk)，辅助空间O(n)。
具体解析
加入新中心只增加一个候选，旧中心的最小距离已经压缩在D里，所以不用重新遍历全部中心。若每轮对n个点重新算到当前i个中心的距离，再对i求和，就会变成O(nk²)，是常见多算一层的错误。
可在同一轮更新时顺便找下一个最大点，不必严格分两次扫描；初始化第一次D也只需O(n)。如只要求中心集合，可维护平方距离保持比较次序；题目已允许单次距离O(1)，因此直接距离版本也满足界。k=n时可直接返回全部点，不过一般算法O(nk)仍符合要求。
来源与证据
Sp14 p.1；Q3坐标已视觉读取并独立计算平方距离表。Q2题面注明2022 Fall Final来源，证明为自行推导，并非官方试卷答案。