集合覆盖问题

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

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

定义

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

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

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

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

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

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