Set Cover

释义 Definition

Set cover（集合覆盖/集合覆盖问题）：在给定一个“全集”（所有需要被覆盖的元素）和若干个其子集的情况下，选择尽可能少（或代价最小）的一些子集，使它们的并集覆盖全集中的所有元素。常见于算法、运筹学与组合优化中。（也可泛指“用一组集合去覆盖目标元素集合”的建模方法。）

发音 Pronunciation (IPA)

/sɛt ˈkʌvər/

例句 Examples

We used a set cover model to choose the fewest warehouses that can serve every city.
我们使用集合覆盖模型来选择最少的仓库，使其能够服务所有城市。

Finding the minimum set cover is NP-complete, so practical systems often use greedy approximations with provable bounds.
求最小集合覆盖是 NP 完全问题，因此实际系统常用带有可证明界的贪心近似算法。

词源 Etymology

该术语由 set（集合） + cover（覆盖） 组合而成，字面意思是“用集合去覆盖”。作为一个固定术语，它在20世纪的组合数学、计算复杂性理论与运筹优化中逐渐定型，用来描述一类经典的覆盖型优化问题。

相关词 Related Words

• Approximation
• Cover
• Greedy
• NP-complete
• Optimization
• Subset
• Universe

文学与著作 Literary Works

• Introduction to Algorithms（Cormen, Leiserson, Rivest, Stein）：在近似算法/贪心策略相关章节讨论集合覆盖。
• Computers and Intractability: A Guide to the Theory of NP-Completeness（Garey & Johnson）：作为经典 NP 完全问题之一出现。
• The Design of Approximation Algorithms（Williamson & Shmoys）：用作近似算法分析与界证明的代表性问题。