跳至內容

集合覆蓋問題

維基百科,自由的百科全書

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

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

定義

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

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

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

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

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

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