X演算法

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

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

X演算法的步驟如下：

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

選擇r的不確定性意味著演算法將衍生出若干獨立的子演算法，每個子演算法都從其父演算法中繼承了去除部分行列的A矩陣。如果其中有一列全為零，則當前情況無解，子演算法返回失敗，但不一定意味整個問題無解。

實際上，所有子演算法形成了一棵搜索樹，其中原問題為根節點，樹的第k層由子演算法在第k次所選擇的行組成。整個演算法即用回溯法對搜索樹深度優先遍歷。

第二步中，無論用什麼方法選擇列最終都可以得到解，但有的方法效率明顯較高。為減少迭代次數，高德納建議每次都選取1最少的列。

## 例子

例如，考慮以下精確覆蓋問題：全集U = {1, 2, 3, 4, 5, 6, 7}，現有U的六個子集$\mathcal{S}$ = {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演算法得出本問題只有一個解：$\mathcal{S}^*$ = {B, D, F}。

## 實現

高德納主要想通過X演算法體現舞蹈鏈的實用性。他發現了使用舞蹈鏈的X演算法效率極高，並把這一過程稱為DLX。DLX用矩陣來表示精確覆蓋問題，在內部的存儲結構為舞蹈鏈。舞蹈鏈是一個雙向環形鍊表，每個矩陣中的1都有一個指針指向其左、右、上、下的1。因為精確覆蓋問題中的矩陣一般都是稀疏的，所以舞蹈鏈中的元素很少，既很省時間，又很省空間。可見使用舞蹈鏈的DLX演算法無論在選擇行時還是回溯錯誤的選擇時效率都很高。

## 外部連結

- 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.