查看“︁精确覆盖问题”︁的源代码

在一个[[全集]]X中若干[[子集]]的[[集合 (数学)|集合]]为S，'''精确覆盖'''是指，S的子集S*，满足X中的每一个元素在S*中恰好出现一次。<ref name="a">{{Cite web |url=http://www.mathreference.com/lan-cx-np,excov.html |title=NP Complete, Exact Cover |accessdate=2011-08-18 |archive-date=2011-07-18 |archive-url=https://web.archive.org/web/20110718212801/http://www.mathreference.com/lan-cx-np,excov.html |dead-url=no }}</ref>

在[[计算机科学]]中，精确覆盖问题指找出这样的一种覆盖，或证明其不存在。这是一个[[NP-完全]]问题<ref name="a"/>，也是[[卡普的二十一个NP-完全问题]]之一<ref>{{cite book|author = [[Stephen Cook]]|year = 1971|chapter = [http://portal.acm.org/citation.cfm?coll=GUIDE&dl=GUIDE&id=805047 The Complexity of Theorem Proving Procedures]|title = Proceedings of the third annual ACM symposium on Theory of computing|pages = 151–158}}</ref>。

==定义==
满足以下条件的集合为一个精确覆盖：
* S*中任意两个集合没有交集，即X中的元素在S*中出现最多一次
* S*中集合的全集为X，即X中的元素在S*中出现最少一次
合二为一，即X中的元素在S*中出现恰好一次。

===举例===
令 <math>\mathcal{S}</math> = {''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.<ref name="sudoku">{{Cite web |url=http://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm |title=Exact Cover Matrix |accessdate=2011-08-18 |archive-date=2011-08-06 |archive-url=https://web.archive.org/web/20110806103259/http://www.stolaf.edu/people/hansonr/sudoku/exactcovermatrix.htm |dead-url=no }}</ref>

通过这种矩阵表示法，求一个精确覆盖转化为求矩阵的若干个行的集合，使每列有且仅有一个1。同时，该问题也是精确覆盖的典型例题之一。

下图为其中一个例子：

:{| border="1" cellpadding="5" cellspacing="0"
! !! 1 !! 2 !! 3 !! 4 !! 5 !! 6 !! 7
|-
! ''A''
| 1 || 0 || 0 || 1 || 0 || 0 || 1
|-
! <span style="font-weight:bold; color:red">''B''</span>
| <span style="font-weight:bold; color:red">1</span> || 0 || 0 || <span style="font-weight:bold; color:red">1</span> || 0 || 0 || 0
|-
! ''C''
| 0 || 0 || 0 || 1 || 1 || 0 || 1
|-
! <span style="font-weight:bold; color:red">''D''</span>
| 0 || 0 || <span style="font-weight:bold; color:red">1</span> || 0 || <span style="font-weight:bold; color:red">1</span> || <span style="font-weight:bold; color:red">1</span> || 0
|-
! ''E''
| 0 || 1 || 1 || 0 || 0 || 1 || 1
|-
! <span style="font-weight:bold; color:red">''F''</span>
| 0 || <span style="font-weight:bold; color:red">1</span> || 0 || 0 || 0 || 0 || <span style="font-weight:bold; color:red">1</span>
|}

S* = {''B'', ''D'', ''F''} 便是一个精确覆盖。

===图论表示法===
包含关系也可以用一个[[二分图]]表示。

二分图左侧每个节点表示S的每个集合，右侧每个节点表示X的每个元素，而精确覆盖便是一种匹配，满足右侧的每个点恰好有一条边。

[[File:Exact-cover-bigraph.svg|400px|Exact-cover-bigraph]][[File:Exact-cover-bigraph-solved.svg|400px|Exact-cover-bigraph-solved]]

==求解方法==
[[X算法]]是[[高德纳]]提出的解决该问题的算法，而[[舞蹈链]]算法(Dancing Links，DLX)算法是X算法在计算机上的一种高效实现。

==应用举例==
*[[数独]]求解<ref name="sudoku"/>

==参考文献==
{{reflist}}

[[Category:理论计算机科学]]
[[Category:NP完全问题]]