跳转到内容

集合覆盖问题

维基百科,自由的百科全书

集合覆盖问题Set covering problemSCP)是组合数学计算机科学计算复杂性理论中的一个经典问题。

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

定义

[编辑]

给定全集,以及一个包含个集合且这个集合的并集为全集的集合。集合覆盖问题要找到的一个最小的子集,使得他们的并集等于全集。

例如,虽然中所有元素的并集是,但是我们可以找到的一个子集,我们称其为一个集合覆盖。

形式化的定义,给定全集和他的一组子集组成的集合覆盖指一个集合,且的元素的并集为

集合覆盖问题的决定性问题为,给定和一个整数,求是否存在一个大小不超过的覆盖。集合覆盖的最佳化问题为给定,求使用最少的集合的一个覆盖。

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

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