精確覆起問題

佇一个全集 X 中間若干子集的集合做 S，精確覆起是講，S 的子集 S \ *，滿足 X 每一个元素佇咧 S \ * 中拄仔好出現一改。

佇計算機科學內底，精確覆起問題指頭仔揣出按呢的一款崁，抑是證明其實無存在。這是一个 NP-完全問題，原仔是卡普的二十一个 NP-完全問題之一。

定義

滿足以下的條件的集合做一个精確覆起：

• S \ * 中任意兩个集合無交集，即 X 中元素佇咧 S \ * 中出現上濟一改
• S \ * 中集合的全集為 X，即 X 中元素佇咧 S \ * 中出現上少一改合二為一，即 X 中元素佇咧 S \ * 中出現拄好一擺。

舉例

令 $ { \ mathcal { S } } $={ _ N _ , _ O _ , _ E _ , _ P _ } 是集合 _ X _={ 一 , 二 , 三 , 四 } 的一个子集的集合，並滿足：

• _ N _={ }
• _ O _={ 一 , 三 }
• _ E _={ 二 , 四 }
• _ P _={ 二 , 三 } .

其中一个子集 { _ O _ , _ E _ } 是 _ X _ 的一个精確崁去，因為乎 _ O _={ 一 , 三 } 而且 _ E _={ 二 , 四 } 的併集拄好是 _ X _={ 一 , 二 , 三 , 四 }。同理，{ _ N _ , _ O _ , _ E _ } 嘛是啦 _ X _ . 的一个精確崁去。空集並無影響結論。

關係表示

通常阮用 S 的逐个子集佮 X 的元素之間包含關係的二箍關係來表示精確覆蓋問題。

矩陣表示法

包括關係會當用一个關係矩陣表示。. 矩陣逐家表示 S 的一个子集，逐列表示 X 中的一个元素。矩陣行列交點元素為一表示對應的元素佇對應的集合中，無佇咧無咧共零 .

通過這个矩陣表示法，求一个精確確定欲轉化做求矩陣的若干焦個行的集合，使逐列有而且干焦一个一。同時，該當問題嘛是確定欲改變的典型例題之一。

下圖為其中一个例：

S \ *={ _ B _ , _ D _ , _ F _ } 就是一个精確崁去。

圖論表示法

包含關係嘛會當用一个二分圖表示。

二分圖倒爿每一个節點表示 S 的逐个集合，正爿每一个節點表示 X 的逐个元素，精確確認改做就是一款匹配，滿足正爿的每一个點拄好有一條邊。

求解方法

X 算法是高德納提出的解決該問題的算法，猶閣舞蹈鍊算法 ( Dancing Links，DLX ) 算法是 X 算法咧算機頂的一種高效實現。

應用舉例

• 數獨求解