跳至內容

X演算法

本頁使用了標題或全文手工轉換
維基百科，自由的百科全書

在電腦科學中，X演算法可用來求解精確覆蓋問題。此名稱最早在高德納的論文《舞蹈鏈》中出現，他認為此演算法是「試錯法中最顯而易見」的。[1] 就技術而言，X演算法是一個深度優先的不確定性回溯演算法。由於X演算法是一個解決精確覆蓋問題的簡潔方法，高德納希望通過該演算法體現舞蹈鏈資料結構的高效性，他把使用後者的X演算法稱為DLX。[1]

X演算法用由0和1組成的矩陣A來表示精確覆蓋問題，目標是選出矩陣的若干行，使得其中的1在所有列中出現且僅出現一次。

X演算法的步驟如下：

  1. 如果矩陣A為空（沒有任何列），則當前局部解即為問題的一個解，返回成功；否則繼續。
  2. 根據一定方法選擇第c列。如果某一列中沒有1，則返回失敗，並去除當前局部解中最新加入的行。
  3. 選擇第r行，使得Ar, c = 1（該步是不確定的）。
  4. 將第r行加入當前局部解中。
  5. 對於滿足Ar, j = 1的每一列j，從矩陣A中刪除所有滿足Ai, j = 1的行，最後再刪除第j列。
  6. 對所得比A小的新矩陣遞迴地執行此演算法。

選擇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. ^ 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 可免費查閱  .

外部連結

[編輯]
取自「https://zh.wikipedia.org/w/index.php?title=X算法&oldid=81777246」