精確覆蓋問題

在一個全集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算法在計算機上的一種高效實現。

相關詞條

熱門詞條

聯絡我們