動(dòng)手實(shí)現(xiàn)Dancing Links

前幾天提到舞蹈鏈算法，這兩天有時(shí)間就動(dòng)手實(shí)現(xiàn)了一下。

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

什么是精確覆蓋（Exact Cover）問題呢？維基百科上對精確覆蓋的定義如下：在一個(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 代表這一列的元素存在于這一行對應(yīng)的子集中，0 代表不存在。那么精確覆蓋問題可以轉(zhuǎn)化成求出矩陣若干行的集合，使得集合中的每一列恰好都有一個(gè) 1。

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

\begin{array} {c|ccccccc} & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline A & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ \color{#d00}{B} & \color{#d00}{1} & \color{#d00}{0} & \color{#d00}{0} & \color{#d00}{1} & \color{#d00}{0} & \color{#d00}{0} & \color{#d00}{0} \\ C & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ \color{#d00}{D} & \color{#d00}{0} & \color{#d00}{0} & \color{#d00}{1} & \color{#d00}{0} & \color{#d00}{1} & \color{#d00}{1} & \color{#d00}{0} \\ E & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ \color{#d00}{F} & \color{#d00}{0} & \color{#d00}{1} & \color{#d00}{0} & \color{#d00}{0} & \color{#d00}{0} & \color{#d00}{0} & \color{#d00}{1} \end{array}

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

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

  1. 如果矩陣A為空（沒有任何列），則當(dāng)前局部解即為問題的一個(gè)解，返回成功；否則繼續(xù)。
  2. 根據(jù)一定方法選擇第 c 列。如果某一列中沒有 1，則返回失敗，并去除當(dāng)前局部解中最新加入的行。
  3. 選擇第 r 行，使得A_{r, c} = 1（該步是非確定性的）。
  4. 將第 r 行加入當(dāng)前局部解中。
  5. 對于滿足A_{r, j} = 1的每一列j，從矩陣A中刪除所有滿足A_{i, j} = 1的行，最后再刪除第 j 列。
  6. 對所得比 A 小的新矩陣遞歸地執(zhí)行此算法。

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

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

\begin{array}{c|ccccccc} & \color{#d00}{1} & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline A & \color{#d00}{1} & 0 & 0 & 1 & 0 & 0 & 1 \\ B & \color{#d00}{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 \end{array}

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

先嘗試選擇行 A。將行 A 加入到當(dāng)前的解中。
\begin{array}{c|ccccccc} & \color{#AD3}{1} & 2 & 3 & \color{#AD3}{4} & 5 & 6 & \color{#AD3}{7} \\ \hline \color{#d00}{A} & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} & 0 & 0 & \color{#d00}{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 \end{array}
行 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 列
\begin{array}{c|ccccccc} & \color{#AD3}{1} & 2 & 3 & \color{#AD3}{4} & 5 & 6 & \color{#AD3}{7} \\ \hline \color{#AD3}{A} & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} \\ \color{#AD3}{B} & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} & 0 & 0 & 0 \\ \color{#AD3}{C} & 0 & 0 & 0 & \color{#d00}{1} & 1 & 0 & \color{#d00}{1} \\ D & 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ \color{#AD3}{E} & 0 & 1 & 1 & 0 & 0 & 1 & \color{#d00}{1} \\ \color{#AD3}{F} & 0 & 1 & 0 & 0 & 0 & 0 & \color{#d00}{1} \end{array}
刪除之后，矩陣只剩下行 D 和第 2，3，5，6 列：
\begin{array}{c|cccc} & 2 & 3 & 5 & 6 \\ \hline D & 0 & 1 & 1 & 1 \\ \end{array}
進(jìn)入遞歸，回到第 1 步，矩陣非空，算法繼續(xù)執(zhí)行。
再進(jìn)入第2步，此時(shí)選擇 1 最少的第 2 列，里面沒有 1，因此返回失敗，同時(shí)將行 A 從當(dāng)前的解中移除；

算法進(jìn)入另一個(gè)分支，選擇行 B，并將其加入到當(dāng)前的解中：
\begin{array}{c|ccccccc} & \color{#AD3}{1} & 2 & 3 & \color{#AD3}{4} & 5 & 6 & 7 \\ \hline A & 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ \color{#d00}{B} & \color{#d00}{1} & 0 & 0 & \color{#d00}{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 \end{array}
行 B 的第 1，4 列為 1，因此要把 1，4 列中包含 1 的行都刪掉。需要?jiǎng)h除掉行 A，B，C，再刪除掉 1，4 列。
\begin{array}{c|ccccccc} & \color{#AD3}{1} & 2 & 3 & \color{#AD3}{4} & 5 & 6 & 7 \\ \hline \color{#AD3}{A} & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} & 0 & 0 & 1 \\ \color{#AD3}{B} & \color{#d00}{1} & 0 & 0 & \color{#d00}{1} & 0 & 0 & 0 \\ \color{#AD3}{C} & 0 & 0 & 0 & \color{#d00}{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 \end{array}
此時(shí)矩陣變?yōu)?br> \begin{array}{c|ccccc} & 2 & 3 & 5 & 6 & 7 \\ \hline D & 0 & 1 & 1 & 1 & 0 \\ E & 1 & 1 & 0 & 1 & 1 \\ F & 1 & 0 & 0 & 0 & 1 \end{array}
進(jìn)入遞歸，回到第 1 步，矩陣非空，因此算法繼續(xù)。
當(dāng)前包含 1 最少的一列是第 5 列，那么將從第 5 列中選擇含有 1 的行進(jìn)行搜索。
\begin{array}{c|ccccc} \ & 2 & 3 & \color{#d00}{5} & 6 & 7 \\ \hline D & 0 & 1 & \color{#d00}{1} & 1 & 0 \\ E & 1 & 1 & 0 & 1 & 1 \\ F & 1 & 0 & 0 & 0 & 1 \end{array}

第 5 列中行 D 含有 1，因此選擇行 D，將其加入當(dāng)前解中，算法進(jìn)入新的一層搜索。
\begin{array}{c|ccccc} & 2 & \color{#AD3}{3} & \color{#AD3}{5} &\color{#AD3}{6} & 7 \\ \hline \color{#d00}{D} & 0 & \color{#d00}{1} & \color{#d00}{1} & \color{#d00}{1} & 0 \\ E & 1 & 1 & 0 & 1 & 1 \\ F & 1 & 0 & 0 & 0 & 1 \end{array}
行 D 的第 3，5，6 列包含 1，我們要?jiǎng)h掉這幾列中包含 1 的所有行，同時(shí)刪掉這幾列
\begin{array} {c|ccccc} & 2 & \color{#AD3}{3} & \color{#AD3}{5} &\color{#AD3}{6} & 7 \\ \hline \color{#AD3}{D} & 0 & \color{#d00}{1} & \color{#d00}{1} & \color{#d00}{1} & 0 \\ \color{#AD3}{E} & 1 & \color{#d00}{1} & 0 & \color{#d00}{1} & 1 \\ F & 1 & 0 & 0 & 0 & 1 \end{array}
那么我們需要?jiǎng)h掉行 D，E 和第 3，5，6 列，矩陣變?yōu)?br> \begin {array}{c|cc} & 2 & 7 \\ \hline F & 1 & 1 \end{array}
再次遞歸執(zhí)行，回到第 1 步，矩陣非空，因此算法繼續(xù)
選擇當(dāng)前包含 1 最少的一列，這里選擇第 2 列。第 2 列中只有行 F 包含 1， 因此選擇行 F

將行 F 加入到當(dāng)前解中，算法進(jìn)入第 3 層搜索
\begin{array} {c|cc} & 2 & 7 \\ \hline \color{#d00}{F} & \color{#d00}{1} & \color{#d00}{1} \end{array}
行 F 中第 2，7列為 1，第 2，7 列中行 F 包含 1，因此移除行 F 和第 2，7 列
\begin{array} {c|cc} & \color{#AD3}{2} & \color{#AD3}{7} \\ \hline \color{#AD3}{F} & \color{#d00}{1} & \color{#d00}{1} \end{array}
算法再次進(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)。

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

Doubly linked list

上圖是一個(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 is removed

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

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

理解了這一點(diǎn)之后，讓我們再來看看舞蹈鏈的結(jié)構(gòu)是怎么樣的：

Dancing links

上面這個(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)之后，我們再來看看是怎樣用舞蹈鏈來實(shí)現(xiàn) X 算法的。這部分算法很精妙，也是舞蹈鏈這個(gè)名字的來由，通過對鏈表上的節(jié)點(diǎn)反復(fù)刪除和插入實(shí)現(xiàn)了遞歸的回溯，就好像一個(gè)個(gè)鏈表在舞臺上翩翩起舞一樣。

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

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

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

選擇一列

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

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


      選擇列中的一個(gè)節(jié)點(diǎn)所在的行

    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)所在的行。


    選擇另一個(gè)節(jié)點(diǎn)所在行

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


    移除了選擇行的所有列，和每一列有交集的所有行

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


    選擇節(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è)空矩陣。


    空鏈表，只剩頭節(jié)點(diǎn)

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

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

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲(chǔ)服務(wù)。

友情鏈接更多精彩內(nèi)容