精確覆蓋問題

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

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

定義

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

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

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

舉例

令 ${\displaystyle {\mathcal {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算法在計算機上的一種高效實現。

應用舉例

• 數獨求解^[3]