集合覆蓋問題

集合覆蓋問題（ Set covering problem，SCP）是組合數學、計算機科學和計算複雜性理論中的一個經典問題。

集合覆蓋的決定性問題是卡普的二十一個NP-完全問題之一。

定義

給定全集${\displaystyle {\mathcal {U}}}$，以及一個包含${\displaystyle n}$個集合且這${\displaystyle n}$個集合的併集為全集的集合${\displaystyle {\mathcal {S}}}$。集合覆蓋問題要找到${\displaystyle {\mathcal {S}}}$的一個最小的子集，使得他們的併集等於全集。

例如${\displaystyle {\mathcal {U}}=\{1,2,3,4,5\}}$，${\displaystyle {\mathcal {S}}=\{\{1,2,3\},\{2,4\},\{3,4\},\{4,5\}\}}$，雖然${\displaystyle {\mathcal {S}}}$中所有元素的併集是${\displaystyle {\mathcal {U}}}$，但是我們可以找到${\displaystyle {\mathcal {S}}}$的一個子集${\displaystyle \{\{1,2,3\},\{4,5\}\}}$，我們稱其為一個集合覆蓋。

形式化的定義，給定全集${\displaystyle {\mathcal {U}}}$和他的一組子集組成的集合${\displaystyle {\mathcal {S}}}$，覆蓋指一個集合${\displaystyle {\mathcal {C}}}$，${\displaystyle {\mathcal {C}}\subseteq {\mathcal {S}}}$，且${\displaystyle {\mathcal {C}}}$的元素的併集為${\displaystyle {\mathcal {U}}}$。

集合覆蓋問題的決定性問題為，給定${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$和一個整數${\displaystyle k}$，求是否存在一個大小不超過${\displaystyle k}$的覆蓋。集合覆蓋的最佳化問題為給定${\displaystyle ({\mathcal {U}},{\mathcal {S}})}$，求使用最少的集合的一個覆蓋。

決定性問題的集合覆蓋是NP完全問題，最佳化問題的集合覆蓋是NP困難問題。

此外，問題可以在每個集合上添加權值而變為帶權集合覆蓋問題。