X算法

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

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

X 演算法的步驟如下：

　
:

選擇 _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 最少的列，則 X 演算法的執行步驟如下：

**第 0 層**

第一步：矩陣非空，故演算法繼續執行。

第二步：1 最少的列為第一列，含有兩個 1。所以選擇第一列：

　
:

第三步：A 行和 B 行第一列均為 1，所以依次選擇這兩行繼續搜尋。

於是演算法開始搜尋樹的第 1 層第一個分支：

　
: **第 1 層：選擇第 A 行**

　
: 第四步：將第 A 行加入當前局部解。

　
: 第五步：第 A 行第 1、4、7 列均為 1：

　
: :

　
: 第 1 列中第 A 行和第 B 行為 1，第 4 列中第 A、B、C 行為 1，第 7 列中第 A、C、E、F 行為 1。所以移除第 A、B、C、E、F 行和第 1、4、7 列：

　
: :

　
: 第六步：遞迴執行演算法，回到第一步。矩陣 _A_ 現在只剩下第 D 行的第 2、3、5、6 列：

　
: :

　
: 第一步：矩陣非空，故演算法繼續執行。

　
: 第二步：1 最少的列為全是零的第二列：

　
: :

　
: 所以該分支上演算法返回失敗，從當前局部解中移除 A。

　
: 演算法繼續搜尋第 1 層的下一個分支：

　
: **第 1 層：選擇第 B 行**

　
: 第四步：將第 B 行加入當前局部解。

　
: 第 B 行第 1 列和第 4 列為 1：

　
: : :

　
: 第一列中第 A 行和第 B 行為 1，第 4 列中第 A、B、C、行為 1。所以移除第 A、B、C 行和第 1、4 列：

　
: :

　
: 遞迴執行演算法，回到第一步。回到矩陣 _A_ 中現在剩下第 D、E、F 行和第 2、3、5、6、7 列：

　
: :

　
: 第一步：矩陣非空，故演算法繼續執行。

　
: 第二步：1 最少的列為第 5 列，含有一個 1。所以選擇第 5 列：

　
: :

　
: 第三步：第 5 列中第 D 行為 1，所以選擇第 D 行繼續搜尋。

　
: 演算法繼續搜尋第 2 層第一個分支：

　
: : **第 2 層：選擇第 D 行**

　
: : 第四步：將第 D 行加入當前局部解。

　
: : 第五步：第 D 行第 3、5、6 列為 1:

　
: : :

　
: : 第 3 列中第 D、E 行為 1，第 5 列中第 D 行為 1，第 6 列中第 D、E 行為 1。所以移除第 D、E 行和第 3、5、6 列：

　
: : :

　
: : 遞迴執行演算法，回到第一步。矩陣 _A_ 現在剩下第 F 行和第 2、7 列：

　
: : :

　
: : 第一步：矩陣非空，故演算法繼續執行。

　
: : 第二步：1 最少的列為第 2 列，含有 1 個 1。所以選擇第 2 列。

　
: : 第 2 列中第 F 行為 1，所以選擇第 F 行繼續搜尋。

　
: : 演算法繼續搜尋第 3 層第一個分支：

　
: : : **第 3 層：選擇第 F 行**

　
: : : 第四步：將第 F 行加入當前局部解。

　
: : : 第 F 行第 2 列和第 7 列為 1：

　
: : : :

　
: : : 第 2 列中第 F 行和第 7 列中第 F 行均為 1。所以移除第 F 行和第 2、7 列：

　
: : : :

　
: : : 遞迴執行演算法，回到第一步。

　
: 第一步：矩陣 _A_ 為空，演算法結束，返回成功。

　
: : : 當前局部解為第 B、D、F 行，所以最終解即為：

　
: : : :

　
: : : 也就是說子集 {_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 演算法無論在選擇行時還是回溯錯誤的選擇時效率都很高。

## 參見

* 精確覆蓋問題
* 雙向連結串列
* 舞蹈鏈

## 參考文獻

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