查看“︁集合覆盖问题”︁的源代码

{{multiple issues|
{{expand|time=2014-06-17T10:25:19+00:00}}
{{expert|time=2014-06-17T10:25:19+00:00}}
{{unreferenced|time=2014-06-17T10:25:19+00:00}}
}}
'''集合覆盖问题'''（ '''Set covering problem'''，'''SCP'''）是[[组合数学]]、[[计算机科学]]和[[计算复杂性理论]]中的一个经典问题。

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

== 定义 ==

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

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

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

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

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

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

{{Authority control}}
[[Category:近似演算法]]
[[Category:组合数学]]
[[Category:计算机科学]]
[[Category:計算複雜性理論]]