X演算法
在電腦科學中，X演算法可用來求解精確覆蓋問題。此名稱最早在高德納的論文《舞蹈鏈》中出現，他認為此演算法是「試錯法中最顯而易見」的。[1] 就技術而言，X演算法是一個深度優先的不確定性回溯演算法。由於X演算法是一個解決精確覆蓋問題的簡潔方法，高德納希望通過該演算法體現舞蹈鏈數據結構的高效性，他把使用後者的X演算法稱為DLX。[1]
X演算法用由0和1組成的矩陣A來表示精確覆蓋問題，目標是選出矩陣的若干行，使得其中的1在所有列中出現且僅出現一次。
X演算法的步驟如下：
選擇r的不確定性意味着演算法將衍生出若干獨立的子演算法，每個子演算法都從其父演算法中繼承了去除部分行列的A矩陣。如果其中有一列全為零，則當前情況無解，子演算法返回失敗，但不一定意味整個問題無解。
實際上，所有子演算法形成了一棵搜尋樹，其中原問題為根節點，樹的第k層由子演算法在第k次所選擇的行組成。整個演算法即用回溯法對搜尋樹深度優先遍歷。
第二步中，無論用什麼方法選擇列最終都可以得到解，但有的方法效率明顯較高。為減少迭代次數，高德納建議每次都選取1最少的列。
例子
[編輯]例如，考慮以下精確覆蓋問題：全集U = {1, 2, 3, 4, 5, 6, 7} ，現有U的六個子集 = {A, B, C, D, E, F}，其中：
- A = {1, 4, 7}；
- B = {1, 4}；
- C = {4, 5, 7}；
- D = {3, 5, 6}；
- E = {2, 3, 6, 7}；
- F = {2, 7}。
此問題可用矩陣表示為：
1 2 3 4 5 6 7 A 1 0 0 1 0 0 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
根據高德納的建議，每次都選取1最少的列，則X演算法的執行步驟如下：
第0層
第一步：矩陣非空，故演算法繼續執行。
第二步：1最少的列為第一列，含有兩個1。所以選擇第一列：
1 2 3 4 5 6 7 A 1 0 0 1 0 0 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
第三步：A行和B行第一列均為1，所以依次選擇這兩行繼續搜尋。
於是演算法開始搜尋樹的第1層第一個分支：
- 第1層：選擇第A行
- 第四步：將第A行加入當前局部解。
- 第五步：第A行第1、4、7列均為1：
1 2 3 4 5 6 7 A 1 0 0 1 0 0 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
- 第1列中第A行和第B行為1，第4列中第A、B、C行為1，第7列中第A、C、E、F行為1。所以移除第A、B、C、E、F行和第1、4、7列：
1 2 3 4 5 6 7 A 1 0 0 1 0 0 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
- 第六步：遞歸執行演算法，回到第一步。矩陣A現在只剩下第D行的第2、3、5、6列：
2 3 5 6 D 0 1 1 1
- 第一步：矩陣非空，故演算法繼續執行。
- 第二步：1最少的列為全是零的第二列：
2 3 5 6 D 0 1 1 1
- 所以該分支上演算法返回失敗，從當前局部解中移除A。
- 演算法繼續搜尋第1層的下一個分支：
- 第1層：選擇第B行
- 第四步：將第B行加入當前局部解。
- 第B行第1列和第4列為1：
1 2 3 4 5 6 7 A 1 0 0 1 0 0 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
- 第一列中第A行和第B行為1，第4列中第A、B、C、行為1。所以移除第A、B、C行和第1、4列：
1 2 3 4 5 6 7 A 1 0 0 1 0 0 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
- 遞歸執行演算法，回到第一步。回到矩陣A中現在剩下第D、E、F行和第2、3、5、6、7列：
2 3 5 6 7 D 0 1 1 1 0 E 1 1 0 1 1 F 1 0 0 0 1
- 第一步：矩陣非空，故演算法繼續執行。
- 第二步：1最少的列為第5列，含有一個1。所以選擇第5列：
2 3 5 6 7 D 0 1 1 1 0 E 1 1 0 1 1 F 1 0 0 0 1
- 第三步：第5列中第D行為1，所以選擇第D行繼續搜尋。
- 演算法繼續搜尋第2層第一個分支：
- 第2層：選擇第D行
- 第四步：將第D行加入當前局部解。
- 第五步：第D行第3、5、6列為1:
2 3 5 6 7 D 0 1 1 1 0 E 1 1 0 1 1 F 1 0 0 0 1
- 第3列中第D、E行為1，第5列中第D行為1，第6列中第D、E行為1。所以移除第D、E行和第3、5、6列：
2 3 5 6 7 D 0 1 1 1 0 E 1 1 0 1 1 F 1 0 0 0 1
- 遞歸執行演算法，回到第一步。矩陣A現在剩下第F行和第2、7列：
2 7 F 1 1
- 第一步：矩陣非空，故演算法繼續執行。
- 第二步：1最少的列為第2列，含有1個1。所以選擇第2列。
- 第2列中第F行為1，所以選擇第F行繼續搜尋。
- 演算法繼續搜尋第3層第一個分支：
- 第3層：選擇第F行
- 第四步：將第F行加入當前局部解。
- 第F行第2列和第7列為1：
2 7 F 1 1
- 第2列中第F行和第7列中第F行均為1。所以移除第F行和第2、7列：
2 7 F 1 1
- 遞歸執行演算法，回到第一步。
- 第一步：矩陣A為空，演算法結束，返回成功。
- 當前局部解為第B、D、F行，所以最終解即為：
1 2 3 4 5 6 7 B 1 0 0 1 0 0 0 D 0 0 1 0 1 1 0 F 0 1 0 0 0 0 1
- 也就是說子集{B, D, F}就是全集U的一個精確覆蓋，每個元素都恰好只出現了一次：B = {1, 4}，D = {3, 5, 6}，F = {2, 7}。
- 如果繼續搜尋，則第3層沒有其他可選擇的行，演算法返回第2層下一個分支。
- 第2層沒有其他可選擇的行，演算法返回第1層下一個分支。
- 第1層沒有其他可選擇的行，演算法返回第0層下一個分支。
第0層沒有其他可選擇的行，演算法最終停止。
綜上所述，用X演算法得出本問題只有一個解： = {B, D, F}。
實現
[編輯]高德納主要想通過X演算法體現舞蹈鏈的實用性。他發現了使用舞蹈鏈的X演算法效率極高，並把這一過程稱為DLX。DLX用矩陣來表示精確覆蓋問題，在內部的儲存結構為舞蹈鏈。舞蹈鏈是一個雙向環形鏈結串列，每個矩陣中的1都有一個指標指向其左、右、上、下的1。因為精確覆蓋問題中的矩陣一般都是稀疏的，所以舞蹈鏈中的元素很少，既很省時間，又很省空間。可見使用舞蹈鏈的DLX演算法無論在選擇行時還是回溯錯誤的選擇時效率都很高。[1]
參見
[編輯]參考文獻
[編輯]- ^ 1.0 1.1 1.2 Knuth, Donald. Dancing links. 2000. arXiv:cs/0011047
.
- Knuth, Donald E., Dancing links, Davies, Jim; Roscoe, Bill; Woodcock, Jim (編), Millennial Perspectives in Computer Science: Proceedings of the 1999 Oxford-Microsoft Symposium in Honour of Sir Tony Hoare, Palgrave: 187–214, 2000, ISBN 978-0-333-92230-9, arXiv:cs/0011047 .
外部連結
[編輯]- Free Software implementation of Algorithm X in C （頁面存檔備份，存於互聯網檔案館） - uses the Dancing Links optimization. Includes examples for using the library to solve sudoku and logic grid puzzles.
- Polycube solver （頁面存檔備份，存於互聯網檔案館） Program (with Lua source code) to fill boxes with polycubes using Algorithm X.
- Knuth's Paper describing the Dancing Links optimization （頁面存檔備份，存於互聯網檔案館） - Gzip'd postscript file.