舞蹈鏈（Dancing links）實(shí)際上是一種數(shù)據(jù)結(jié)構(gòu)，可以用來實(shí)現(xiàn) X算法，以解決精確覆蓋問題。

什么是精確覆蓋（Exact Cover）問題呢？維基百科上對(duì)精確覆蓋的定義如下：在一個(gè)全集X中若干子集的集合為S。S* 是 S的一個(gè)子集，當(dāng)且僅當(dāng)X中的每一個(gè)元素在S*中恰好出現(xiàn)一次時(shí)，S*稱之為一個(gè)精確覆蓋。在計(jì)算機(jī)科學(xué)中，精確覆蓋問題指找出這樣的一種覆蓋，或證明其不存在。這是一個(gè)NP-完全問題。

例如，S = {A，B，C，D，E，F(xiàn)} 是全集 X = {1，2，3，4，5，6，7} 的一個(gè)子集的集合，其中：

A = {1, 4, 7}

B = {1, 4}

C = {4, 5, 7}

D = {3, 5, 6}

E = {2, 3, 6, 7}

F = {2, 7}

那么，S的一個(gè)子集 S* = {B, D, F} 是X的一個(gè)精確覆蓋，因?yàn)?X 中的每個(gè)元素恰好在S*中出現(xiàn)了一次。

可以用0-1矩陣來表示精確覆蓋問題。我們用矩陣的每行表示S的一個(gè)元素，也就是X的一個(gè)子集；用矩陣的每列表示X的一個(gè)元素。矩陣中的1代表這一列的元素存在于這一行對(duì)應(yīng)的子集中，0代表不存在。那么精確覆蓋問題可以轉(zhuǎn)化成求出矩陣若干行的集合，使得集合中的每一列恰好都有一個(gè)1。

比如前面的問題可以用矩陣的形式表示成

那么選擇紅色的B，D，F(xiàn)能滿足每列都恰好包含一個(gè)1。

可以用 Knuth 提出的X算法來解決精確覆蓋問題。X算法是一個(gè)非確定性的深度優(yōu)先回溯算法。它的具體步驟如下：

1. 如果矩陣為空（沒有任何列），則當(dāng)前局部解即為問題的一個(gè)解，返回成功；否則繼續(xù)。

2. 根據(jù)一定方法選擇第 c 列。如果某一列中沒有 1，則返回失敗，并去除當(dāng)前局部解中最新加入的行。

選擇第 r 行，使得（該步是非確定性的）。

將第 r 行加入當(dāng)前局部解中。

對(duì)于滿足的每一列j，從矩陣中刪除所有滿足的行，最后再刪除第 j 列。

對(duì)所得比 A 小的新矩陣遞歸地執(zhí)行此算法。

讓我們用 X算法解決上面的精確覆蓋問題。

首先，當(dāng)前矩陣不為空，算法繼續(xù)進(jìn)行。那么先選擇1最少的一列。因?yàn)?1，2，3，5，6 列都只有 2 個(gè) 1，因此我們隨便選擇 1 個(gè)，比如第 1 列。

行 A 和 B 都含有 1，因此要在這兩行中進(jìn)行選擇。

先嘗試選擇行 A。將行A加入到當(dāng)前的解中。

行A的 1，4，7 列為 1，根據(jù)第 5 步，需要把所有在 1，4，7 列中含有 1 的行都刪除掉，因此需要?jiǎng)h除掉行A，B，C，E，F(xiàn)，同時(shí)刪除掉第 1，4，7 列

刪除之后，矩陣只剩下行 D 和第 2，3，5，6 列：

進(jìn)入遞歸，回到第 1 步，矩陣非空，算法繼續(xù)執(zhí)行。

再進(jìn)入第2步，此時(shí)選擇 1 最少的第 2 列，里面沒有 1，因此返回失敗，同時(shí)將行 A 從當(dāng)前的解中移除；

算法進(jìn)入另一個(gè)分支，選擇行 B，并將其加入到當(dāng)前的解中：

行 B 的第 1，4 列為 1，因此要把 1，4 列中包含 1 的行都刪掉。需要?jiǎng)h除掉行 A，B，C，再刪除掉 1，4 列。

此時(shí)矩陣變?yōu)?/p>

進(jìn)入遞歸，回到第 1 步，矩陣非空，因此算法繼續(xù)。

當(dāng)前包含 1 最少的一列是第 5 列，那么將從第 5 列中選擇含有 1 的行進(jìn)行搜索。

第 5 列中行 D 含有 1，因此選擇行 D，將其加入當(dāng)前解中，算法進(jìn)入新的一層搜索。

行 D 的第 3，5，6 列包含 1，我們要?jiǎng)h掉這幾列中包含 1 的所有行，同時(shí)刪掉這幾列

那么我們需要?jiǎng)h掉行 D，E 和第 3，5，6 列，矩陣變?yōu)?/p>

再次遞歸執(zhí)行，回到第 1 步，矩陣非空，因此算法繼續(xù)

選擇當(dāng)前包含 1 最少的一列，這里選擇第 2 列。第 2 列中只有行 F 包含 1， 因此選擇行 F

將行 F 加入到當(dāng)前解中，算法進(jìn)入第 3 層搜索

行 F 中第 2，7列為 1，第 2，7 列中行 F 包含 1，因此移除行 F 和第 2，7 列

算法再次進(jìn)入遞歸執(zhí)行，回到第 1 步，此時(shí)所有的列都被移除了，矩陣為空，因此返回成功，找到了一個(gè)解：{B, D, F}

繼續(xù)搜索，沒有其他可以選擇的行，返回上一層；

第2層也沒有其他可以選擇的行，再返回上一層；

第1層也沒有其他可以選擇的行，再返回上一層；

第0層也沒有其他可以選擇的行，算法終止。

以上就是 X 算法的執(zhí)行過程。Knuth 提出 X 算法主要是為了說明舞蹈鏈的作用，他發(fā)現(xiàn)用舞蹈鏈來執(zhí)行 X 算法效率特別高。那么什么是舞蹈鏈呢？它是基于雙向鏈表的一種數(shù)據(jù)結(jié)構(gòu)。

讓我們先來看看雙向鏈表：

上圖是一個(gè)簡單的雙向鏈表，每個(gè)節(jié)點(diǎn)有兩個(gè)指針，分別指向自己的前驅(qū)和后繼節(jié)點(diǎn)。那么如果我們想把其中一個(gè)節(jié)點(diǎn)，比如 B 從鏈表中刪掉，只需要執(zhí)行下面的操作：

B.left.right = B.right
B.right.left = B.left

注意：此時(shí)雖然 B 從鏈表中移除了，但它的兩個(gè)指針依然保持不變，還是指向之前的前驅(qū)和后繼節(jié)點(diǎn)。

因此，如果我想把 B 再添加到鏈表原來的位置上，此時(shí)并不需要修改 B 的指針，只需要再把 B 的前驅(qū)和后繼節(jié)點(diǎn)的指針恢復(fù)就可以了：

B.left.right = B
B.right.left = B

理解了這一點(diǎn)之后，讓我們?cè)賮砜纯次璧告湹慕Y(jié)構(gòu)是怎么樣的：

上面這個(gè)圖是一個(gè)舞蹈鏈的結(jié)構(gòu)，描述的是前面 X 算法中用到的矩陣。它由幾部分構(gòu)成：

最上面的藍(lán)色部分是一個(gè)水平的環(huán)狀雙向鏈表。最左邊是頭節(jié)點(diǎn)，它是整個(gè)數(shù)據(jù)結(jié)構(gòu)的根節(jié)點(diǎn)。其余是列頭節(jié)點(diǎn)，每個(gè)代表矩陣中的一列。

每一列又是一個(gè)縱向的環(huán)狀雙向鏈表。除了最上面的列頭節(jié)點(diǎn)，其他的每個(gè)節(jié)點(diǎn)都代表前面的矩陣中的一個(gè) 1。這實(shí)際上是一個(gè)稀疏矩陣，為了優(yōu)化存儲(chǔ)和效率，只保留了值為 1 的節(jié)點(diǎn)，把每個(gè)節(jié)點(diǎn)按順序保存到數(shù)組中。最早的 Dancing Links 算法，也就是 Knuth 在 2000 年發(fā)表的論文中，下面的每一行也都是一個(gè)雙向鏈表。但后來他發(fā)現(xiàn)每一行在算法執(zhí)行過程中實(shí)際上不會(huì)發(fā)生變化，因此他把水平的雙向鏈表取消了，只保留了最頂上的列頭節(jié)點(diǎn)之間的水平雙向鏈表。下面的每一行之間的前后節(jié)點(diǎn)可以直接通過數(shù)組的索引得到。兩邊是Space節(jié)點(diǎn)，用來標(biāo)記一行的開始和結(jié)束。

每個(gè)普通節(jié)點(diǎn) A 都包含 4 個(gè) 字段，A.up 和 A.down 代表雙向鏈表的兩個(gè)指針，分別指向 A 上面和下面的節(jié)點(diǎn)。還有一個(gè) A.col ，指向 A 所在列的頭節(jié)點(diǎn)，需要根據(jù)這個(gè)字段定位到節(jié)點(diǎn)所在的列。另外還有一個(gè) A.row，主要是方便在遞歸的過程中緩存當(dāng)前的解。

列頭節(jié)點(diǎn)還要再多幾個(gè)字段，left 和 right 分別指向水平雙向鏈表的左節(jié)點(diǎn)和右節(jié)點(diǎn)。另外還有一個(gè) count 字段，代表這一列當(dāng)前一共有幾個(gè)元素。X 算法的第 2 步，選擇 1 最少的列時(shí)會(huì)用到這個(gè)字段。

理解了舞蹈鏈的數(shù)據(jù)結(jié)構(gòu)之后，我們?cè)賮砜纯词窃鯓佑梦璧告渷韺?shí)現(xiàn) X 算法的。這部分算法很精妙，也是舞蹈鏈這個(gè)名字的來由，通過對(duì)鏈表上的節(jié)點(diǎn)反復(fù)刪除和插入實(shí)現(xiàn)了遞歸的回溯，就好像一個(gè)個(gè)鏈表在舞臺(tái)上翩翩起舞一樣。

具體的算法實(shí)現(xiàn)可以參照 Knuth 的論文，我們還是用圖的方式來說明一下。

（1）首先，判斷鏈表是否為空，可以通過 head.right == head 來判斷。如果為空則返回，并輸出當(dāng)前的解。

（2）不為空則選擇當(dāng)前節(jié)點(diǎn)數(shù)最少的列。如果只有列頭節(jié)點(diǎn)，則返回失敗。

遍歷這一列的每個(gè)節(jié)點(diǎn)，開始進(jìn)行覆蓋操作：

（1）首先將節(jié)點(diǎn)所在行作為解的一部分，加入到當(dāng)前解中；

（2）遍歷這一行的所有節(jié)點(diǎn)，將每個(gè)節(jié)點(diǎn)所在列都刪除掉，同時(shí)刪除掉與這些列有交集的所有行：

2a. 遍歷節(jié)點(diǎn)所在列的每個(gè)節(jié)點(diǎn)，將每個(gè)節(jié)點(diǎn)所在行的所有節(jié)點(diǎn)從它所在的列中移除掉，同時(shí)將列頭節(jié)點(diǎn)的計(jì)數(shù)減 1：

node.up.down = node.down
node.down.up = node.up
col_node.count -= 1

2b. 還要將這一列從鏈表中移除：

col_node.left.right = col_node.right
col_node.right.left = col_node.left

進(jìn)入遞歸調(diào)用，判斷鏈表是否為空；

不為空則選擇節(jié)點(diǎn)數(shù)最少的列，再遍歷這一列的節(jié)點(diǎn)，進(jìn)行覆蓋操作：

移除掉所有節(jié)點(diǎn)之后，進(jìn)入遞歸調(diào)用，發(fā)現(xiàn)鏈表不為空，但節(jié)點(diǎn)數(shù)最少的列中沒有普通節(jié)點(diǎn)了，返回失?。?/p>

開始做鏈表的還原操作。注意還原的順序需要和移除的順序相反。如果我們是從上至下，從左至右移除節(jié)點(diǎn)，那么還原的時(shí)候就從右至左，從下至上。否則的話可能會(huì)出現(xiàn)問題，導(dǎo)致一個(gè)節(jié)點(diǎn)被還原多次，這樣列中節(jié)點(diǎn)的計(jì)數(shù)就不準(zhǔn)確了。

node.up.down = node
node.down.up = node
col_node.count += 1

并且把刪除的列也取消覆蓋

col_node.left.right = col_node
col_node.right.left = col_node

遞歸返回到上一層，還原之后，發(fā)現(xiàn)列中沒有其他節(jié)點(diǎn)可以選擇，再返回到上一層，選擇下一個(gè)節(jié)點(diǎn)所在的行。

和之前的方法相同，遍歷這一行的所有節(jié)點(diǎn)，將每個(gè)節(jié)點(diǎn)所在列都刪除掉，同時(shí)刪除掉與這些列有交集的所有行：

再選擇節(jié)點(diǎn)最少的列，遍歷這一列的所有節(jié)點(diǎn)的所在行：

遍歷這一行的所有節(jié)點(diǎn)，刪除掉每個(gè)節(jié)點(diǎn)所在列，以及與這些列有交集的所有行：

再次進(jìn)入遞歸調(diào)用，判斷矩陣不為空，選擇節(jié)點(diǎn)最少的一列，遍歷每個(gè)節(jié)點(diǎn)，刪除掉所在行的所有列，與這些列有交集的所有行，最后我們得到一個(gè)空矩陣。

此時(shí)將得到的解輸出，并返回，接下來還要進(jìn)行還原操作，然后搜索下一個(gè)解。

以上就是舞蹈鏈算法的執(zhí)行過程。