計算機科學中,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   .

外部連結

編輯