| 本条目存在以下问题,请协助 改善本条目或在 讨论页针对议题发表看法。
| 此条目需要 精通或熟悉相关主题的编者参与及协助编辑。 (2014年6月17日) 请邀请适合的人士改善本条目。更多的细节与详情请参见讨论页。 |
|
集合覆盖问题( Set covering problem,SCP)是组合数学、计算机科学和计算复杂性理论中的一个经典问题。
集合覆盖的决定性问题是卡普的二十一个NP-完全问题之一。
定义
给定全集
,以及一个包含
个集合且这
个集合的并集为全集的集合
。集合覆盖问题要找到
的一个最小的子集,使得他们的并集等于全集。
例如
,
,虽然
中所有元素的并集是
,但是我们可以找到
的一个子集
,我们称其为一个集合覆盖。
形式化的定义,给定全集
和他的一组子集组成的集合
,覆盖指一个集合
,
,且
的元素的并集为
。
集合覆盖问题的决定性问题为,给定
和一个整数
,求是否存在一个大小不超过
的覆盖。集合覆盖的最佳化问题为给定
,求使用最少的集合的一个覆盖。
决定性问题的集合覆盖是NP完全问题,最佳化问题的集合覆盖是NP困难问题。
此外,问题可以在每个集合上添加权值而变为带权集合覆盖问题。