集合覆盖问题

维基百科,自由的百科全书
跳转至: 导航搜索

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

集合覆盖的决定性问题卡普的二十一个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困难问题

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