跳至內容

舞蹈鏈

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
The Dancing Links algorithm solving a polycube puzzle

電腦科學中, 舞蹈鏈(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皇后問題的可選約束。 棋盤對角線表示可選的約束,因為一些對角線可能不被占用。 如果一個對角線被占用,它只能被占用一次。

參考資料

  1. ^ Knuth, Donald. Dancing links. Millenial Perspectives in Computer Science. P159. 2000, 187 [2006-07-11]. arXiv:cs/0011047可免費查閱. (原始內容存檔於2017-04-21). 
  2. ^ 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. 

外部連結