精確覆蓋問題

在一個全集X中若干子集集合為S,精確覆蓋是指,S的子集S*,滿足X中的每一個元素在S*中恰好出現一次。[1]

計算機科學中,精確覆蓋問題指找出這樣的一種覆蓋,或證明其不存在。這是一個NP-完全問題[1],也是卡普的二十一個NP-完全問題之一[2]

定義

滿足以下條件的集合為一個精確覆蓋:

  • S*中任意兩個集合沒有交集,即X中的元素在S*中出現最多一次
  • S*中集合的全集為X,即X中的元素在S*中出現最少一次

合二為一,即X中的元素在S*中出現恰好一次。

舉例

  = {N, O, E, P} 是集合X = {1, 2, 3, 4}的一個子集的集合,並滿足:

  • N = { }
  • O = {1, 3}
  • E = {2, 4}
  • P = {2, 3}.

其中一個子集 {O, E} 是 X的一個精確覆蓋,因為 O = {1, 3} 而 E = {2, 4} 的併集恰好是 X = {1, 2, 3, 4}。同理, {N, O, E} 也是 X.的一個精確覆蓋。空集並不影響結論。

關係表示

通常我們用S的每個子集與X的元素之間包含關係的二元關係來表示精確覆蓋問題。

矩陣表示法

包含關係可以用一個關係矩陣表示。. 矩陣每行表示S的一個子集,每列表示X中的一個元素。矩陣行列交點元素為1表示對應的元素在對應的集合中,不在則為0.[3]

通過這種矩陣表示法,求一個精確覆蓋轉化為求矩陣的若干個行的集合,使每列有且僅有一個1。同時,該問題也是精確覆蓋的典型例題之一。

下圖為其中一個例子:

1 2 3 4 5 6 7
A 1 0 0 1 0 0 1
B 1 0 0 1 0 0 0
C 0 0 0 1 1 0 1
D 0 0 1 0 1 1 0
E 0 1 1 0 0 1 1
F 0 1 0 0 0 0 1

S* = {B, D, F} 便是一個精確覆蓋。

圖論表示法

包含關係也可以用一個二分圖表示。

二分圖左側每個節點表示S的每個集合,右側每個節點表示X的每個元素,而精確覆蓋便是一種匹配,滿足右側的每個點恰好有一條邊。

  

求解方法

X算法高德納提出的解決該問題的算法,而舞蹈鏈算法(Dancing Links,DLX)算法是X算法在計算機上的一種高效實現。

應用舉例

參考文獻

  1. ^ 1.0 1.1 NP Complete, Exact Cover. [2011-08-18]. (原始內容存檔於2011-07-18). 
  2. ^ Stephen Cook. The Complexity of Theorem Proving Procedures. Proceedings of the third annual ACM symposium on Theory of computing. 1971: 151–158.  外部連結存在於|chapter= (幫助)
  3. ^ 3.0 3.1 Exact Cover Matrix. [2011-08-18]. (原始內容存檔於2011-08-06).