集合覆盖问题

集合覆盖问题（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困难问题。

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