更新时间：2022-08-25 16:56
给定全集 ，以及一个包含n个集合且这n集合的并集为全集的集合 。集合覆盖问题要找到的一个最小的子集，使得他们的并集等于全集。
例如，，虽然中所有元素的并集是}，但是我们可以找到的一个子集，我们称其为一个集合覆盖。
形式化的定义，给定全集和他的一组子集组成的集合，覆盖指一个集合且C的元素的并集为。
集合覆盖问题的决定性问题为，给定和一个整数k，求是否存在一个大小不超过k的覆盖。集合覆盖的最佳化问题为给定，求使用最少的集合的一个覆盖。
决定性问题的集合覆盖是NP完全问题，最佳化问题的集合覆盖是NP困难问题。
此外，问题可以在每个集合上添加权值而变为带权集合覆盖问题。
经典SCP描述包含一个集合U以及U内元素构成的若干各小类集合S，目标是找到S 的一个子集，该子集满足所含元素包含了U中的所有的元素且使小类集合个数最少。例如，U={1,2,3,4,5}，S={{1,2},{3,4},{2,4,5},{4,5}},找到集合能满足条件的可以有O={{1,2},{3,4}{4,5}}或是O={{1,2},{3,4},{2,4,5}}，至于具体选哪种组合，还有引申的一个问题：WSC，即Weighted Set Cover加权集合覆盖，每个集合类被赋予不同的权值，从而由权值决定最终的选择。
对于完全集合覆盖问题的决定版本是NPC（non-deterministic polynomial complete）的，而优化版本是NP-hard的
给定两个集合E和S，元素的集合E和E的子集的集合S，求出S的子集C，使得C中所有集合的并等于E，同时使得|C|最小。这就是经典的集合覆盖问题(SCP)。它是NP-hard类的最优化组合问题。对于NP-HARD类的问题，在P≠NP的假设下，是不存在多项式时间算法的，只能设计求解他们的近似算法或近似方案，或者对于问题条件进行限制使得限制后的子问题是一个非NP-HARD类的问题。集合覆盖问题在实际应用中有好多变型。若对于任意的s∈S有一个权重w(s)，并且同样求c，使得sum from s∈C w(s)最小。问题就成为了带有权重的集合覆盖问题。若对于任意s∈S有一个限制正整数k(s)，使得在s中的至多覆盖k(s)个元素，问题就成为带容量限制的集合覆盖问题(CSCP)，可以看出带权重或带容量限制的集合覆盖问题至少和集合覆盖问题一样难。Lang和Yannakanis证明了集合覆盖问题不存在c(lnn)，c<1/4的近似算法，除非NP(?)...