集合覆盖问题 - 维基百科，自由的百科全书

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。 此條目需要擴充。 (2014年6月17日) 请協助改善这篇條目，更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。 此條目需要精通或熟悉相关主题的编者参与及协助编辑。 (2014年6月17日) 請邀請適合的人士改善本条目。更多的細節與詳情請參见討論頁。 此條目没有列出任何参考或来源。 (2014年6月17日) 維基百科所有的內容都應該可供查證。请协助補充可靠来源以改善这篇条目。无法查证的內容可能會因為異議提出而被移除。

集合覆盖问题（ Set covering problem，SCP）是组合数学、计算机科学和计算复杂性理论中的一个经典问题。

集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。

给定全集${\displaystyle {\mathcal {U}}}$，以及一个包含${\displaystyle n}$个集合且这${\displaystyle n}$个集合的并集为全集的集合${\displaystyle {\mathcal {S}}}$。集合覆盖问题要找到${\displaystyle {\mathcal {S}}}$的一个最小的子集，使得他们的并集等于全集。

例如${\displaystyle {\mathcal {U}}=\{1,2,3,4,5\}}$，${\displaystyle {\mathcal {S}}=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}}$，虽然${\displaystyle {\mathcal {S}}}$中所有元素的并集是${\displaystyle {\mathcal {U}}}$，但是我们可以找到${\displaystyle {\mathcal {S}}}$的一个子集${\displaystyle \{\{1,2,3\},\{4,5\}\}}$，我们称其为一个集合覆盖。

形式化的定义，给定全集${\displaystyle {\mathcal {U}}}$和他的一组子集组成的集合${\displaystyle {\mathcal {S}}}$，覆盖指一个集合${\displaystyle {\mathcal {C}}}$，${\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}$，且${\displaystyle {\mathcal {C}}}$的元素的并集为${\displaystyle {\mathcal {U}}}$。

集合覆盖问题的决定性问题为，给定${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$和一个整数${\displaystyle k}$，求是否存在一个大小不超过${\displaystyle k}$的覆盖。集合覆盖的最佳化問題为给定${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$，求使用最少的集合的一个覆盖。

决定性问题的集合覆盖是NP完全问题，最佳化问题的集合覆盖是NP困难问题。

此外，问题可以在每个集合上添加权值而变为带权集合覆盖问题。