舞蹈鏈
此條目翻譯品質不佳。 (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