集合覆蓋問題

集合覆蓋問題Set covering problemSCP)是組合數學計算機科學計算複雜性理論中的一個經典問題。

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

定義

編輯

給定全集 ,以及一個包含 個集合且這 個集合的併集為全集的集合 。集合覆蓋問題要找到 的一個最小的子集,使得他們的併集等於全集。

例如  ,雖然 中所有元素的併集是 ,但是我們可以找到 的一個子集 ,我們稱其為一個集合覆蓋。

形式化的定義,給定全集 和他的一組子集組成的集合 覆蓋指一個集合  ,且 的元素的併集為 

集合覆蓋問題的決定性問題為,給定 和一個整數 ,求是否存在一個大小不超過 的覆蓋。集合覆蓋的最佳化問題為給定 ,求使用最少的集合的一個覆蓋。

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

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