集合覆盖问题Set Cover是我在实际开发里遇到比较多的组合优化问题之一你有一堆候选方案每个方案能覆盖一部分需求目标是用最少的方案把所有需求罩住。这次的做法是基于贪心近似算法用Python实现一版能直接跑、能解释、性能跟得上的代码。贪心近似算法的最大价值就一句话在一眼看不出最优解、数据量又不想让人穷举的场景里它能用很短时间给出一个质量可以接受的答案。适合写算法作业的同学、准备面试的开发者也适合正在做选型但又不想引入重量级求解器的工程人员。1. 集合覆盖问题到底在解决什么事1.1 问题定义从数学到实际先做一次形式化。假设你有一个全集 UU 里有 n 个元素还有 m 个子集 S1、S2……Sm每个子集都包含 U 中的一部分元素。集合覆盖问题要求从这 m 个子集里选出数量最少的一批使得它们的并集恰好等于 U。这个“恰好”很重要多选当然也能覆盖但问题要的是“最少数量”不是“随便凑齐”。为什么“最少”这么关键因为每个子集通常都对应一笔真实成本。可能是买一个广告位、部署一台服务器、安排一场宣讲会也可能是给一组监控摄像头选点位。拿一个某高校社团招新的例子来说新生按专业分成 12 个群体宣传组准备了 6 套宣讲方案每套方案能覆盖其中几个群体问最少安排几场宣讲能把 12 个群体全摸到这就是集合覆盖问题群体是 U 的元素方案是子集目标是最小化选择的方案数。这类问题比你想的要普遍我把遇到过的场景整理了一下场景全集 U 里的元素候选子集目标广告投放目标用户各个广告套餐覆盖的人群最少套餐覆盖最多客户安防监控重点点位摄像头能监控的区域最少摄像头覆盖所有点位内容分发城市/区域CDN 节点的服务范围最少节点覆盖全部区域排课调度需求方每个时段能服务的对象集合最少时段满足全部需求这些业务完全不同但底层数学模型完全一致。所以只要把算法实现一次换数据就能换场景这也是这个模型值得单独写一篇的原因。1.2 为什么不能直接硬算集合覆盖问题是教科书级的 NP 完全问题。要精确求出最优解最朴素的办法是枚举所有子集组合m 个子集就有 2^m 种选法。m 等于 30 时组合数已经超过 10 亿m 到 60 时普通机器基本可以放弃治疗。我试过在一台性能不错的笔记本上验证一个 20 多个候选的精确解穷举都要等一会儿从那时起我就不再对超过 15 个候选的问题做全量枚举了。当然精确路线不是只有穷举还有整数规划。成熟的求解器可以解几千个变量的模型结果也是最优质的。但问题在于引入求解器意味着新增依赖、学习建模语言、接受不确定的求解时长。在一个响应式系统里查询接口等不起那么久也没必要为了一个“只差 3% 的改进”付出那么大的成本。工程场景往往不是要绝对最优而是要在可接受时间内拿到一个“95 分以上、逻辑能解释、上线不翻车”的方案。这就是贪心近似算法的主场简单、快速、结果有界。2. 贪心近似算法的设计思路2.1 贪心策略每次都挑最能“开疆拓土”的集合贪心的核心操作特别朴素重复做同一件事——在所有还没被选中的集合里找出能覆盖最多“当前未被覆盖元素”的那个然后把它选进来并把新覆盖的元素从“未覆盖集合”里划掉。重复这个过程直到所有元素都被覆盖。这里特别容易踩一个理解上的坑不是选“覆盖总数最多”的集合而是选“新增覆盖最多”的集合。已经被覆盖的元素再扫一遍没有收益判断标准永远是当前子集 ∩ 尚未覆盖的元素集合的大小。流程拆开就三步初始化uncovered Uselected []。循环直到uncovered为空遍历所有未选集合计算gain |S ∩ uncovered|选 gain 最大的集合加入selected然后执行uncovered - S。返回selected。每次遍历 m 个集合每个集合算一次交集整体最坏复杂度大约在 O(kmn) 这个量级k 是解的大小。实际场景里因为每个集合算的是集合运算速度往往比理论复杂度看起来快很多几百个集合、几千个元素的规模在毫秒级就能出结果。可以用一个生活化的类比理解这个策略你在逛自助餐厅想吃遍所有菜品虽然每道菜分量不同但你已经吃过的不想再拿所以每次只盯着“现在盘子里还没有的菜”里最多的一盘。局部看似只顾当下但由于目标本身就是“覆盖最多”这个局部操作和整体目标的高度一致效果并不差。2.2 近似比为什么可控很多人第一反应是“每次都选局部最大最后不会离最优解很远吗”在最坏情况下它当然会差但这不是无底洞。集合覆盖上贪心算法有理论保证解的集合数量不会超过最优解的(1 ln n)倍其中 n 是全集元素个数。这个结论是值得完整推一遍的因为理解它之后你对这个算法的信任度会完全不一样。假设最优解需要 OPT 个集合。某轮开始前还有 r 个元素没覆盖。既然这些剩余元素一定能被最优解里的 OPT 个集合覆盖掉那么 r 个元素分配给 OPT 个集合必然存在至少一个集合能覆盖剩余 r 个元素中的r / OPT个。贪心算法每轮恰好选的是“新增覆盖最多”的集合所以这一轮它新增的元素数量至少是r / OPT。于是每轮结束之后剩余元素数量最多会变成原来的1 - 1/OPT。从 n 个元素开始经过 k 轮剩余元素数量不会超过n × (1 - 1/OPT)^k。想让这个数小于 1也就是全部覆盖完k 大约需要OPT × ln n这个量级。结论就是贪心解 ≤ OPT × (1 ln n)n 取 100 时系数才 4.6 左右n 取 10000 时系数约 10.2。也就是说即使元素规模涨到一万个最坏情况下解也不会超过最优解的 11 倍左右而实际工程里通常比这个界好得多。对数增长带来的上限正是这个算法最值钱的地方。2.3 和最优解的差距它不是万能的有理论保证不代表它不会犯错。我专门构造过一个坏例子让贪心付了“额外学费”U {1, 2, 3, 4, 5, 6, 7, 8} A {1, 2, 3, 4} B {5, 6, 7, 8} C {1, 2, 5, 6}这个例子里最优解是选 A 和 B2 个集合就能全覆盖。但如果子集顺序是 C、A、B贪心第一轮看到 C 和 A、B 的新增覆盖数都是 4会按下标顺序挑 C第二轮剩下 {3,4,7,8}接下来选 A 或 B 都只能新增 2 个第三轮再补一个最终得到 3 个集合。同一份数据把顺序改成 A、B、C贪心就只需要 2 个集合。这说明两件事第一近似算法确实不等于最优算法第二平手时怎么处理会直接影响最终结果。后面我在避坑章节还会回到“平手策略”这个话题因为很多实际项目的表现差异并不是算法本身造成的而是这里的选择规则造成的。3. Python 实现三版代码进阶3.1 基础版用 set 直接表达“覆盖”Python 的 set 天然适合这个数学模型。全集用 set每个子集也用 set判断“覆盖了多少未覆盖元素”就是一次交集运算选中一个集合后从uncovered里减掉它就是差集运算。代码可以写得非常贴合数学定义。def greedy_set_cover(universe, subsets): 贪心算法求解集合覆盖问题基础版 universe: 可迭代的全集元素 subsets: list[set]候选子集列表 返回: (选中的子集下标列表, 未能覆盖的剩余元素集合) uncovered set(universe) selected [] while uncovered: best_idx -1 best_gain 0 for i, sub in enumerate(subsets): gain len(sub uncovered) # 本次选它能新增多少个元素 if gain best_gain: best_gain gain best_idx i # 所有候选集合都不能再贡献新元素说明覆盖不了全集 if best_gain 0: return selected, uncovered selected.append(best_idx) uncovered - subsets[best_idx] return selected, uncovered这里有几个容易写错的地方提前说一下。第一uncovered set(universe)是拷贝一份全集不要直接uncovered universe否则你会把外部数据一起改掉。第二返回选中的子集下标列表而不是集合对象本身因为调用方需要知道对应原列表里的哪个位置。第三如果best_gain是 0 但uncovered非空说明这个数据集根本不可能全覆盖这时候返回未覆盖集合比原地死循环或者抛出异常更合理调用方可以自己决定是回滚还是换方案。这个版本在小规模数据上已经完全够用。我建议新手先把这个版本理解透再去看后面的优化。毕竟 set 的可读性是位运算完全没法比的。3.2 加权版集合有成本时怎么办现实问题里更常见的版本是“每个方案除了覆盖元素还有一个成本比如经费、人力、带宽目标不是选最少集合而是让总成本最低。”这时候贪心标准也要从“新增最多元素”变成“单位成本新增元素最多”。def weighted_greedy_set_cover(universe, subsets, weights): 加权集合覆盖问题 universe: 全集元素 subsets: list[set]候选子集 weights: list[float]每个子集的成本/权重 返回: (选中下标列表, 未覆盖集合) uncovered set(universe) selected [] while uncovered: best_idx -1 best_value 0.0 for i in range(len(subsets)): if i in selected: continue if not subsets[i]: continue gain len(subsets[i] uncovered) value gain / weights[i] # 单位成本收益 if value best_value: best_value value best_idx i if best_idx -1 or best_value 0: return selected, uncovered selected.append(best_idx) uncovered - subsets[best_idx] return selected, uncovered选择标准变成gain / cost之后理论上限没有基础版本那个1 ln n那么漂亮但实际使用效果通常不错。比如我做过的一个模拟广告投放项目里套餐成本相差几十倍按总覆盖数选会疯狂选中那些又贵又大的套餐改成单位成本收益之后才真正把预算压了下来。如果你的业务里有明确的成本字段优先考虑加权版。3.3 位运算提速版当全集元素规模较大、候选集合很多时set 的哈希计算和内存分配会变成瓶颈。一个更快的思路是用整数的二进制位表示集合第 i 位是 1 表示第 i 个元素在这个集合里。这样交集运算变成按位与未被覆盖的部分用mask ~covered提取统计新增数量变成数二进制里 1 的个数。def sets_to_masks(universe, subsets): 把元素集合列表转为位掩码列表 element_index {x: i for i, x in enumerate(universe)} masks [] for s in subsets: mask 0 for x in s: mask | 1 element_index[x] masks.append(mask) return masks def greedy_set_cover_bits(universe_size, masks): 位运算加速版 universe_size: 全集元素数量 masks: list[int]每个子集的整数位掩码 返回: (选中下标列表, 是否全部覆盖) full_mask (1 universe_size) - 1 covered 0 selected [] while covered ! full_mask: best_idx -1 best_gain 0 for i, mask in enumerate(masks): # int.bit_count() 在 Python 3.8/3.10 可用 # 低版本用 bin(mask ~covered).count(1) 也行 gain bin(mask ~covered).count(1) if gain best_gain: best_gain gain best_idx i if best_gain 0: return selected, False selected.append(best_idx) covered | masks[best_idx] return selected, True为什么这套会快交集和差集全变成了整数位运算这几条指令在现代 CPU 上是微秒级操作没有哈希冲突、没有新对象分配、缓存也友好。Python 3.10 以上可以用int.bit_count()替代bin(x).count(1)速度还能再上一个台阶。我拿一组随机模拟数据对比过全集 1000 个元素800 个候选子集基础版大约要几十毫秒级别位运算版能压到个位数毫秒。如果问题规模到了上百万个候选集合位运算版本几乎是必须的选择否则每次循环里的集合分配就会拖垮整个程序。4. 实例演示跑一遍才理解每一步4.1 一个小规模全流程追踪用一开始提到的 12 元素例子完整推一遍。全集和子集定义如下U {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} S1 {1, 2, 3, 4, 5} S2 {1, 2, 3, 4, 6} S3 {5, 6, 7, 8} S4 {7, 8, 9, 10} S5 {9, 10, 11, 12} S6 {11, 12, 5, 6}第一轮所有集合都没被选uncovered就是整个 U。此时每个集合的新增增益子集容量新增覆盖增益S155S255S344S444S544S644S1 和 S2 都覆盖 5 个代码按顺序选第一个也就是 S1。选中后uncovered {6, 7, 8, 9, 10, 11, 12}。第二轮再看各集合的新增增益子集与剩余集合的交集新增覆盖增益S2{6}1S3{6, 7, 8}3S4{7, 8, 9, 10}4S5{9, 10, 11, 12}4S6{6, 11, 12}2S4 和 S5 都是 4按下标顺序选 S4。这时uncovered {6, 11, 12}。第三轮只剩 S6 能覆盖全部 3 个剩余元素S5 只能覆盖 2 个S2 覆盖 1 个。于是选 S6uncovered变为空集结束。最终输出selected indices: [0, 3, 5] covered count: 12 remaining: set()跑出来的解是 S1、S4、S6 三个集合并集正好是整个 U。而且这个例子里每个集合最多 5 个元素两个集合并起来最多覆盖 10 个所以 3 已经是理论下界贪心在顺风局可以直接摸到最优解。4.2 反例演示平手顺序如何影响结果再回到 2.3 节那个 8 元素反例。如果把子集顺序定成 C、A、Bsubsets [C, A, B] C {1, 2, 5, 6} A {1, 2, 3, 4} B {5, 6, 7, 8}第一轮三个集合增益全是 4选 C。剩余元素变成 {3,4,7,8}。第二轮 A 和 B 增益都是 2按顺序先选 A剩余 {7,8}。第三轮只能再补 B最终 3 个集合。如果把顺序调成 A、B、Csubsets [A, B, C]第一轮选 A增益 4剩余 {5,6,7,8}第二轮 B 的增益是 4直接选 B结束。最终只用 2 个集合。同一个数据集两个结果差距 50%。这说明平手时的选择规则不是细节而是结果的一部分。实际项目里我见过的做法有两种一种是按业务优先级给每个候选集合排一个二级权重另一种是按集合容量降序排序再进贪心等于把容量大的集合放在前面让平手时倾向于优先拿大集合。两种都不增加计算成本但能显著减少随机性。再补一个随机测试的描述我用全集 100 个元素、30 个随机子集、每个子集随机抽取 15 个元素跑了一轮贪心最终用了 12 个子集覆盖全部。理论近似界大约是ln(100) 1 ≈ 5.6倍最坏系数但实际随机数据里通常只比最优解多出 20% 到 50%说明最坏情况在现实中没那么容易出现。5. 常见问题与排查技巧实录5.1 四个高频坑写这个算法的代码大多数问题都不是算法本身而是边界处理。我整理了一张速查表现象根因处理方式程序无限循环候选集合覆盖不了全集uncovered永远清不掉每轮检查best_gain 0直接返回剩余元素选了空集也不自知空集和uncovered的交集为 0但遍历花费时间预处理时过滤掉空集重复元素、重复集合数据源不干净进算法前统一转换成 set 再做去重同一数据结果不稳定平手时下标顺序敏感预先按二级条件排序固定平手规则内存占用高大量使用 set 对象且创建频繁切换到位运算版本重点说一下“全集无法覆盖”的情况。很多初学者以为只要循环跑完就完了但实际数据经常缺胳膊少腿。某次我处理一组从 Excel 读进来的点位数据里面有个点位被漏填了导致没有任何候选集合包含它。这种情况算法不会报错只是不断重复扫描最终发现所有候选集合增益都是 0。所以best_gain 0这个退出条件必须放在循环里并且把未覆盖集合返回给上层否则你会在线上收到一堆脏数据。5.2 性能与扩展优化如果基础 set 版本已经满足性能就不要过度优化。但真要面对大规模数据有几个方向值得做。第一个方向是位运算前面已经写过代码不再重复。第二个方向是提前剪枝遍历候选集合时如果某个mask | covered full_mask说明当前候选单独就能补完剩余元素直接选中退出省掉后续所有循环。第三个方向是针对稀疏大集合的排序优化提前按集合大小降序排列往往前几轮就能覆盖掉大量元素后面循环里的uncovered缩小后集合运算开销也会变小。加权场景再延伸一下如果成本是固定的可以按“先算性价比再算覆盖数”的顺序写如果成本会动态变化那每次循环都要重新计算gain / weights[i]这种场景下缓存的收益一定会被动态变化抵消直接用线性扫描更合适。如果你需要精确解也不一定非要自己实现分支定界。给几百个集合的规模用整数规划求解器是最省事的模型写起来就是一堆线性约束但不要试图拿求解器在秒级响应接口里跑几千集合的问题那是自找麻烦。流式的近似思路我也简单提一句当集合多到内存都放不下可以按元素做随机采样或哈希分桶在每个桶内跑贪心再合并结果这个路子能处理上亿级别规模不过误差会明显上升。5.3 个人经验小结我实际用这个算法最多的场景是“快速验证一种业务策略是否可行”。在这种场景里最优解是什么其实没那么重要更重要的是在几分钟内给出一个可执行方案让产品同学拿去评审等方案方向确定了再考虑要不要花时间上精确求解。有几个经验值得分享。第一每次跑完一定要校验并集覆盖结果不要相信贪心返回的“覆盖完成”就完事因为输入数据的脏问题可能让你的计算全部落空校验代码三行就能写完。第二给子集排个序比想象中的效果大不仅在平手时稳定结果很多时候还能减少一两轮循环成本为零收益白拿。第三如果结果里出现大量候选集合被选中但总元素数又不多先回去检查是不是有许多子集重复了重复集合在贪心算法里不会被自动排除纯属浪费名额。还有一个认知上的收获贪心近似算法最适合的场景不是“一定要最优”而是“快速给出可用方案、并在理论上保证不会太差”。它不适合的场景是那种结果误差直接换成钱的业务比如采购预算分配差一个点就是几十万成本那种情况再麻烦也应该上精确算法或者更精细的拉格朗日松弛。先判断业务对最优性的容忍度再决定要不要用贪心这是比写代码更重要的决策。从基础 set 版本开始捋清楚每一步再根据数据规模切换到位运算版本这个过程花不了多少时间但能让你再遇到任何“选最少覆盖全部”的实际问题时都有现成的工具和踩过坑的底气。希望这篇能帮你少走点弯路。
集合覆盖问题Set Cover是我在实际开发里遇到比较多的组合优化问题之一你有一堆候选方案每个方案能覆盖一部分需求目标是用最少的方案把所有需求罩住。这次的做法是基于贪心近似算法用Python实现一版能直接跑、能解释、性能跟得上的代码。贪心近似算法的最大价值就一句话在一眼看不出最优解、数据量又不想让人穷举的场景里它能用很短时间给出一个质量可以接受的答案。适合写算法作业的同学、准备面试的开发者也适合正在做选型但又不想引入重量级求解器的工程人员。1. 集合覆盖问题到底在解决什么事1.1 问题定义从数学到实际先做一次形式化。假设你有一个全集 UU 里有 n 个元素还有 m 个子集 S1、S2……Sm每个子集都包含 U 中的一部分元素。集合覆盖问题要求从这 m 个子集里选出数量最少的一批使得它们的并集恰好等于 U。这个“恰好”很重要多选当然也能覆盖但问题要的是“最少数量”不是“随便凑齐”。为什么“最少”这么关键因为每个子集通常都对应一笔真实成本。可能是买一个广告位、部署一台服务器、安排一场宣讲会也可能是给一组监控摄像头选点位。拿一个某高校社团招新的例子来说新生按专业分成 12 个群体宣传组准备了 6 套宣讲方案每套方案能覆盖其中几个群体问最少安排几场宣讲能把 12 个群体全摸到这就是集合覆盖问题群体是 U 的元素方案是子集目标是最小化选择的方案数。这类问题比你想的要普遍我把遇到过的场景整理了一下场景全集 U 里的元素候选子集目标广告投放目标用户各个广告套餐覆盖的人群最少套餐覆盖最多客户安防监控重点点位摄像头能监控的区域最少摄像头覆盖所有点位内容分发城市/区域CDN 节点的服务范围最少节点覆盖全部区域排课调度需求方每个时段能服务的对象集合最少时段满足全部需求这些业务完全不同但底层数学模型完全一致。所以只要把算法实现一次换数据就能换场景这也是这个模型值得单独写一篇的原因。1.2 为什么不能直接硬算集合覆盖问题是教科书级的 NP 完全问题。要精确求出最优解最朴素的办法是枚举所有子集组合m 个子集就有 2^m 种选法。m 等于 30 时组合数已经超过 10 亿m 到 60 时普通机器基本可以放弃治疗。我试过在一台性能不错的笔记本上验证一个 20 多个候选的精确解穷举都要等一会儿从那时起我就不再对超过 15 个候选的问题做全量枚举了。当然精确路线不是只有穷举还有整数规划。成熟的求解器可以解几千个变量的模型结果也是最优质的。但问题在于引入求解器意味着新增依赖、学习建模语言、接受不确定的求解时长。在一个响应式系统里查询接口等不起那么久也没必要为了一个“只差 3% 的改进”付出那么大的成本。工程场景往往不是要绝对最优而是要在可接受时间内拿到一个“95 分以上、逻辑能解释、上线不翻车”的方案。这就是贪心近似算法的主场简单、快速、结果有界。2. 贪心近似算法的设计思路2.1 贪心策略每次都挑最能“开疆拓土”的集合贪心的核心操作特别朴素重复做同一件事——在所有还没被选中的集合里找出能覆盖最多“当前未被覆盖元素”的那个然后把它选进来并把新覆盖的元素从“未覆盖集合”里划掉。重复这个过程直到所有元素都被覆盖。这里特别容易踩一个理解上的坑不是选“覆盖总数最多”的集合而是选“新增覆盖最多”的集合。已经被覆盖的元素再扫一遍没有收益判断标准永远是当前子集 ∩ 尚未覆盖的元素集合的大小。流程拆开就三步初始化uncovered Uselected []。循环直到uncovered为空遍历所有未选集合计算gain |S ∩ uncovered|选 gain 最大的集合加入selected然后执行uncovered - S。返回selected。每次遍历 m 个集合每个集合算一次交集整体最坏复杂度大约在 O(kmn) 这个量级k 是解的大小。实际场景里因为每个集合算的是集合运算速度往往比理论复杂度看起来快很多几百个集合、几千个元素的规模在毫秒级就能出结果。可以用一个生活化的类比理解这个策略你在逛自助餐厅想吃遍所有菜品虽然每道菜分量不同但你已经吃过的不想再拿所以每次只盯着“现在盘子里还没有的菜”里最多的一盘。局部看似只顾当下但由于目标本身就是“覆盖最多”这个局部操作和整体目标的高度一致效果并不差。2.2 近似比为什么可控很多人第一反应是“每次都选局部最大最后不会离最优解很远吗”在最坏情况下它当然会差但这不是无底洞。集合覆盖上贪心算法有理论保证解的集合数量不会超过最优解的(1 ln n)倍其中 n 是全集元素个数。这个结论是值得完整推一遍的因为理解它之后你对这个算法的信任度会完全不一样。假设最优解需要 OPT 个集合。某轮开始前还有 r 个元素没覆盖。既然这些剩余元素一定能被最优解里的 OPT 个集合覆盖掉那么 r 个元素分配给 OPT 个集合必然存在至少一个集合能覆盖剩余 r 个元素中的r / OPT个。贪心算法每轮恰好选的是“新增覆盖最多”的集合所以这一轮它新增的元素数量至少是r / OPT。于是每轮结束之后剩余元素数量最多会变成原来的1 - 1/OPT。从 n 个元素开始经过 k 轮剩余元素数量不会超过n × (1 - 1/OPT)^k。想让这个数小于 1也就是全部覆盖完k 大约需要OPT × ln n这个量级。结论就是贪心解 ≤ OPT × (1 ln n)n 取 100 时系数才 4.6 左右n 取 10000 时系数约 10.2。也就是说即使元素规模涨到一万个最坏情况下解也不会超过最优解的 11 倍左右而实际工程里通常比这个界好得多。对数增长带来的上限正是这个算法最值钱的地方。2.3 和最优解的差距它不是万能的有理论保证不代表它不会犯错。我专门构造过一个坏例子让贪心付了“额外学费”U {1, 2, 3, 4, 5, 6, 7, 8} A {1, 2, 3, 4} B {5, 6, 7, 8} C {1, 2, 5, 6}这个例子里最优解是选 A 和 B2 个集合就能全覆盖。但如果子集顺序是 C、A、B贪心第一轮看到 C 和 A、B 的新增覆盖数都是 4会按下标顺序挑 C第二轮剩下 {3,4,7,8}接下来选 A 或 B 都只能新增 2 个第三轮再补一个最终得到 3 个集合。同一份数据把顺序改成 A、B、C贪心就只需要 2 个集合。这说明两件事第一近似算法确实不等于最优算法第二平手时怎么处理会直接影响最终结果。后面我在避坑章节还会回到“平手策略”这个话题因为很多实际项目的表现差异并不是算法本身造成的而是这里的选择规则造成的。3. Python 实现三版代码进阶3.1 基础版用 set 直接表达“覆盖”Python 的 set 天然适合这个数学模型。全集用 set每个子集也用 set判断“覆盖了多少未覆盖元素”就是一次交集运算选中一个集合后从uncovered里减掉它就是差集运算。代码可以写得非常贴合数学定义。def greedy_set_cover(universe, subsets): 贪心算法求解集合覆盖问题基础版 universe: 可迭代的全集元素 subsets: list[set]候选子集列表 返回: (选中的子集下标列表, 未能覆盖的剩余元素集合) uncovered set(universe) selected [] while uncovered: best_idx -1 best_gain 0 for i, sub in enumerate(subsets): gain len(sub uncovered) # 本次选它能新增多少个元素 if gain best_gain: best_gain gain best_idx i # 所有候选集合都不能再贡献新元素说明覆盖不了全集 if best_gain 0: return selected, uncovered selected.append(best_idx) uncovered - subsets[best_idx] return selected, uncovered这里有几个容易写错的地方提前说一下。第一uncovered set(universe)是拷贝一份全集不要直接uncovered universe否则你会把外部数据一起改掉。第二返回选中的子集下标列表而不是集合对象本身因为调用方需要知道对应原列表里的哪个位置。第三如果best_gain是 0 但uncovered非空说明这个数据集根本不可能全覆盖这时候返回未覆盖集合比原地死循环或者抛出异常更合理调用方可以自己决定是回滚还是换方案。这个版本在小规模数据上已经完全够用。我建议新手先把这个版本理解透再去看后面的优化。毕竟 set 的可读性是位运算完全没法比的。3.2 加权版集合有成本时怎么办现实问题里更常见的版本是“每个方案除了覆盖元素还有一个成本比如经费、人力、带宽目标不是选最少集合而是让总成本最低。”这时候贪心标准也要从“新增最多元素”变成“单位成本新增元素最多”。def weighted_greedy_set_cover(universe, subsets, weights): 加权集合覆盖问题 universe: 全集元素 subsets: list[set]候选子集 weights: list[float]每个子集的成本/权重 返回: (选中下标列表, 未覆盖集合) uncovered set(universe) selected [] while uncovered: best_idx -1 best_value 0.0 for i in range(len(subsets)): if i in selected: continue if not subsets[i]: continue gain len(subsets[i] uncovered) value gain / weights[i] # 单位成本收益 if value best_value: best_value value best_idx i if best_idx -1 or best_value 0: return selected, uncovered selected.append(best_idx) uncovered - subsets[best_idx] return selected, uncovered选择标准变成gain / cost之后理论上限没有基础版本那个1 ln n那么漂亮但实际使用效果通常不错。比如我做过的一个模拟广告投放项目里套餐成本相差几十倍按总覆盖数选会疯狂选中那些又贵又大的套餐改成单位成本收益之后才真正把预算压了下来。如果你的业务里有明确的成本字段优先考虑加权版。3.3 位运算提速版当全集元素规模较大、候选集合很多时set 的哈希计算和内存分配会变成瓶颈。一个更快的思路是用整数的二进制位表示集合第 i 位是 1 表示第 i 个元素在这个集合里。这样交集运算变成按位与未被覆盖的部分用mask ~covered提取统计新增数量变成数二进制里 1 的个数。def sets_to_masks(universe, subsets): 把元素集合列表转为位掩码列表 element_index {x: i for i, x in enumerate(universe)} masks [] for s in subsets: mask 0 for x in s: mask | 1 element_index[x] masks.append(mask) return masks def greedy_set_cover_bits(universe_size, masks): 位运算加速版 universe_size: 全集元素数量 masks: list[int]每个子集的整数位掩码 返回: (选中下标列表, 是否全部覆盖) full_mask (1 universe_size) - 1 covered 0 selected [] while covered ! full_mask: best_idx -1 best_gain 0 for i, mask in enumerate(masks): # int.bit_count() 在 Python 3.8/3.10 可用 # 低版本用 bin(mask ~covered).count(1) 也行 gain bin(mask ~covered).count(1) if gain best_gain: best_gain gain best_idx i if best_gain 0: return selected, False selected.append(best_idx) covered | masks[best_idx] return selected, True为什么这套会快交集和差集全变成了整数位运算这几条指令在现代 CPU 上是微秒级操作没有哈希冲突、没有新对象分配、缓存也友好。Python 3.10 以上可以用int.bit_count()替代bin(x).count(1)速度还能再上一个台阶。我拿一组随机模拟数据对比过全集 1000 个元素800 个候选子集基础版大约要几十毫秒级别位运算版能压到个位数毫秒。如果问题规模到了上百万个候选集合位运算版本几乎是必须的选择否则每次循环里的集合分配就会拖垮整个程序。4. 实例演示跑一遍才理解每一步4.1 一个小规模全流程追踪用一开始提到的 12 元素例子完整推一遍。全集和子集定义如下U {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12} S1 {1, 2, 3, 4, 5} S2 {1, 2, 3, 4, 6} S3 {5, 6, 7, 8} S4 {7, 8, 9, 10} S5 {9, 10, 11, 12} S6 {11, 12, 5, 6}第一轮所有集合都没被选uncovered就是整个 U。此时每个集合的新增增益子集容量新增覆盖增益S155S255S344S444S544S644S1 和 S2 都覆盖 5 个代码按顺序选第一个也就是 S1。选中后uncovered {6, 7, 8, 9, 10, 11, 12}。第二轮再看各集合的新增增益子集与剩余集合的交集新增覆盖增益S2{6}1S3{6, 7, 8}3S4{7, 8, 9, 10}4S5{9, 10, 11, 12}4S6{6, 11, 12}2S4 和 S5 都是 4按下标顺序选 S4。这时uncovered {6, 11, 12}。第三轮只剩 S6 能覆盖全部 3 个剩余元素S5 只能覆盖 2 个S2 覆盖 1 个。于是选 S6uncovered变为空集结束。最终输出selected indices: [0, 3, 5] covered count: 12 remaining: set()跑出来的解是 S1、S4、S6 三个集合并集正好是整个 U。而且这个例子里每个集合最多 5 个元素两个集合并起来最多覆盖 10 个所以 3 已经是理论下界贪心在顺风局可以直接摸到最优解。4.2 反例演示平手顺序如何影响结果再回到 2.3 节那个 8 元素反例。如果把子集顺序定成 C、A、Bsubsets [C, A, B] C {1, 2, 5, 6} A {1, 2, 3, 4} B {5, 6, 7, 8}第一轮三个集合增益全是 4选 C。剩余元素变成 {3,4,7,8}。第二轮 A 和 B 增益都是 2按顺序先选 A剩余 {7,8}。第三轮只能再补 B最终 3 个集合。如果把顺序调成 A、B、Csubsets [A, B, C]第一轮选 A增益 4剩余 {5,6,7,8}第二轮 B 的增益是 4直接选 B结束。最终只用 2 个集合。同一个数据集两个结果差距 50%。这说明平手时的选择规则不是细节而是结果的一部分。实际项目里我见过的做法有两种一种是按业务优先级给每个候选集合排一个二级权重另一种是按集合容量降序排序再进贪心等于把容量大的集合放在前面让平手时倾向于优先拿大集合。两种都不增加计算成本但能显著减少随机性。再补一个随机测试的描述我用全集 100 个元素、30 个随机子集、每个子集随机抽取 15 个元素跑了一轮贪心最终用了 12 个子集覆盖全部。理论近似界大约是ln(100) 1 ≈ 5.6倍最坏系数但实际随机数据里通常只比最优解多出 20% 到 50%说明最坏情况在现实中没那么容易出现。5. 常见问题与排查技巧实录5.1 四个高频坑写这个算法的代码大多数问题都不是算法本身而是边界处理。我整理了一张速查表现象根因处理方式程序无限循环候选集合覆盖不了全集uncovered永远清不掉每轮检查best_gain 0直接返回剩余元素选了空集也不自知空集和uncovered的交集为 0但遍历花费时间预处理时过滤掉空集重复元素、重复集合数据源不干净进算法前统一转换成 set 再做去重同一数据结果不稳定平手时下标顺序敏感预先按二级条件排序固定平手规则内存占用高大量使用 set 对象且创建频繁切换到位运算版本重点说一下“全集无法覆盖”的情况。很多初学者以为只要循环跑完就完了但实际数据经常缺胳膊少腿。某次我处理一组从 Excel 读进来的点位数据里面有个点位被漏填了导致没有任何候选集合包含它。这种情况算法不会报错只是不断重复扫描最终发现所有候选集合增益都是 0。所以best_gain 0这个退出条件必须放在循环里并且把未覆盖集合返回给上层否则你会在线上收到一堆脏数据。5.2 性能与扩展优化如果基础 set 版本已经满足性能就不要过度优化。但真要面对大规模数据有几个方向值得做。第一个方向是位运算前面已经写过代码不再重复。第二个方向是提前剪枝遍历候选集合时如果某个mask | covered full_mask说明当前候选单独就能补完剩余元素直接选中退出省掉后续所有循环。第三个方向是针对稀疏大集合的排序优化提前按集合大小降序排列往往前几轮就能覆盖掉大量元素后面循环里的uncovered缩小后集合运算开销也会变小。加权场景再延伸一下如果成本是固定的可以按“先算性价比再算覆盖数”的顺序写如果成本会动态变化那每次循环都要重新计算gain / weights[i]这种场景下缓存的收益一定会被动态变化抵消直接用线性扫描更合适。如果你需要精确解也不一定非要自己实现分支定界。给几百个集合的规模用整数规划求解器是最省事的模型写起来就是一堆线性约束但不要试图拿求解器在秒级响应接口里跑几千集合的问题那是自找麻烦。流式的近似思路我也简单提一句当集合多到内存都放不下可以按元素做随机采样或哈希分桶在每个桶内跑贪心再合并结果这个路子能处理上亿级别规模不过误差会明显上升。5.3 个人经验小结我实际用这个算法最多的场景是“快速验证一种业务策略是否可行”。在这种场景里最优解是什么其实没那么重要更重要的是在几分钟内给出一个可执行方案让产品同学拿去评审等方案方向确定了再考虑要不要花时间上精确求解。有几个经验值得分享。第一每次跑完一定要校验并集覆盖结果不要相信贪心返回的“覆盖完成”就完事因为输入数据的脏问题可能让你的计算全部落空校验代码三行就能写完。第二给子集排个序比想象中的效果大不仅在平手时稳定结果很多时候还能减少一两轮循环成本为零收益白拿。第三如果结果里出现大量候选集合被选中但总元素数又不多先回去检查是不是有许多子集重复了重复集合在贪心算法里不会被自动排除纯属浪费名额。还有一个认知上的收获贪心近似算法最适合的场景不是“一定要最优”而是“快速给出可用方案、并在理论上保证不会太差”。它不适合的场景是那种结果误差直接换成钱的业务比如采购预算分配差一个点就是几十万成本那种情况再麻烦也应该上精确算法或者更精细的拉格朗日松弛。先判断业务对最优性的容忍度再决定要不要用贪心这是比写代码更重要的决策。从基础 set 版本开始捋清楚每一步再根据数据规模切换到位运算版本这个过程花不了多少时间但能让你再遇到任何“选最少覆盖全部”的实际问题时都有现成的工具和踩过坑的底气。希望这篇能帮你少走点弯路。
