集合覆蓋問題

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

集合覆蓋的決定性問題是卡普的二十一個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困難問題。

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