精確覆蓋問題

在一個全集X中若干子集的集合為S，精確覆蓋（Exactcover）是指，S的子集S*，滿足X中的每一個元素在S*中恰好出現一次。在計算機科學中，精確覆蓋問題指找出這樣的一種覆蓋，或證明其不存在。

簡介

在一個全集X中若干子集的集合為S，精確覆蓋（Exactcover）是指，S的子集S*，滿足X中的每一個元素在S*中恰好出現一次。在計算機科學中，精確覆蓋問題指找出這樣的一種覆蓋，或證明其不存在。這是一個NP-完全問題，也是卡普的二十一個NP-完全問題之一。

定義

滿足以下條件的集合為一個精確覆蓋：
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。
通過這種矩陣表示法，求一個精確覆蓋轉化為求矩陣的若干個行的集合，使每列有且僅有一個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

	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算法是高德納提出的解決該問題的算法，而舞蹈鏈算法(DancingLinks，DLX)算法是X算法在計算機上的一種高效實現。