舞蹈鏈
 | 此條目翻譯品質不佳。 (2017年3月28日) |
在計算機科學中, 舞蹈鏈（Dancing Links), 也叫 DLX, 是由 Donald Knuth 提出的數據結構，目的是快速實現他提出的的 X算法.[1] X算法是一種遞歸算法，時間複雜度不確定, 深度優先, 通過回溯尋找精確覆蓋問題所有可能的解。有一些著名的精確覆蓋問題，包括鋪磚塊，八皇后問題，數獨問題。
名字來自於這個算法的工作方式，算法中的迭代讓鏈接與同伴鏈接"跳舞"，很像「精心編排的舞蹈」。 Knuth 歸功於 Hiroshi Hitotsumatsu 與 Kōhei Noshita 在1979的研究 ,[2] 但是Knuth的論文讓舞蹈鏈流行。
算法實現
[編輯]文章的剩餘部分討論這種算法在Algorithm X中的應用，強烈建議讀者先閱讀 X算法 。
主要思想
[編輯]舞蹈鏈的主要思想來自於 雙向鍊表
x.left.right ← x.right; x.right.left ← x.left;
以上代碼會從鍊表中移除x元素
x.left.right ← x; x.right.left ← x;
以上代碼會恢復x元素在鍊表中的位置（如果x的左側元素和右側元素沒有變的話）。不管鍊表中有多少個元素，就算只有一個，算法也可以工作。
Knuth 發現用樸素算法實現Algorithm X會花費大量的時間來搜索1。當要選擇一列的時候，要搜索整個矩陣來找到1。當選擇一行的時候，需要在整列中搜索1。為了把搜索時間從 complexity O(n) 降到 O(1)， Knuth 使用了一個 稀疏矩陣 ，只存放所有1 的位置。
無論何時，矩陣中的每個節點都會與左邊和右邊的節點（原始矩陣中的1的位置）、上面和下面（原始矩陣中同一列的1），以及列頭連接。每一行和每一列都會形成一個雙向鍊表。
鍊表頭
[編輯]每一列都會有特殊的，叫做「列頭」的節點，作為列表中的一部分。列頭形成了特殊的一行，（「控制行」）包括了原始矩陣中還存在的每一列。
最後，每一列的頭會記錄這一列中節點的個數，我們可以用這些信息來定位節點最少的一列，只花費complexity O(n) 的時間複雜度。 （而不是O(n×m)），這裡的n指的是列的個數，m指的是行的個數。選擇節點最少的一列來進行搜索在一些情況下可以提高性能，但不是每個問題中都需要這麼做。
搜索
[編輯]在 Algorithm X中，行與列是按照規則生成的，存儲着原始矩陣。每次移除一列以及那列中的一行。如果選中的列沒有包括任何行，當前的矩陣是無解的，必須回溯。當移除元素時，每一列中與那一行有交叉點的（原始矩陣中的1）都會被移除。列被移除了，因為他們已經被填滿，行被移除是因為他們與指定的列有衝突。要移除某一列，要先移除那列的頭，接着，遍歷所有與這一列有交集的行，把那行與其他行的交點都去掉（這樣阻止了這些列與當前列的衝突）。對包含1的列重複這樣的列移除操作。這樣的做法保證每個節點只被移除一次，並且按照順序，這樣就可以正確地回溯了。如果代入過程的矩陣沒有任何的行，那麼這已經被填滿，選中的列就是一個解。
回溯
[編輯]要回溯，之前的操作需要反過來做一遍，使用剛才提到的第二個算法。Knuth 的論文給了一個清晰的這兩個操作的關係以及移除、恢復操作的具體方式，並放寬了要求。
有可能出現的制約因素
[編輯]算法也可以解決一個特定的約束是可選的覆蓋問題，但是可以滿足最多一次。 舞蹈鏈接可容納這些必須填充的主要列，次要列是可選的。 這將算法的解決方案測試從沒有列的矩陣改變為沒有主列的矩陣，並且如果正在使用列中1最少的啟發式搜索，那麼只需在主列中檢查。 Knuth討論了應用於n皇后問題的可選約束。 棋盤對角線表示可選的約束，因為一些對角線可能不被占用。 如果一個對角線被占用，它只能被占用一次。
參考資料
[編輯]- ^ Knuth, Donald. Dancing links. Millenial Perspectives in Computer Science. P159. 2000, 187 [2006-07-11]. arXiv:cs/0011047
. （原始內容存檔於2017-04-21）.
- ^ Hitotumatu, Hirosi; Noshita, Kohei. A Technique for Implementing Backtrack Algorithms and its Application. Information Processing Letters. 1979, 8 (4): 174–175. doi:10.1016/0020-0190(79)90016-4.
外部連結
[編輯]- A distributed Dancing Links implementation as a Hadoop MapReduce example
- C# implementation of an Exact Cover solver （頁面存檔備份，存於網際網路檔案館） - uses Algorithm X and the Dancing Links trick.
- DlxLib NuGet package （頁面存檔備份，存於網際網路檔案館） - a C# class library that implements DLX