X算法

在计算机科学中，X算法可用来求解精确覆盖问题。此名称最早在高德纳的论文《舞蹈链》中出现，他认为此算法是“试错法中最显而易见”的。 就技术而言，X算法是一个深度优先的不确定性回溯算法。由于X算法是一个解决精确覆盖问题的简洁方法，高德纳希望通过该算法体现舞蹈链数据结构的高效性，他把使用后者的X算法称为DLX。

X算法用由0和1组成的矩阵A来表示精确覆盖问题，目标是选出矩阵的若干行，使得其中的1在所有列中出现且仅出现一次。

X算法的步骤如下：
 {| border="1" cellpadding="5" cellspacing="0"
|
 如果矩阵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的六个子集 = {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}。
此问题可用矩阵表示为：
{| border="1" cellpadding="5" cellspacing="0"
! !! 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。所以选择第一列：
{| border="1" cellpadding="5" cellspacing="0"
! !! 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：

{| border="1" cellpadding="5" cellspacing="0"
! !! 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列：

{| border="1" cellpadding="5" cellspacing="0"
! !! 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列：

{| border="1" cellpadding="5" cellspacing="0"
! !! 2 !! 3 !! 5 !! 6
|-
! D
| 0 || 1 || 1 || 1
|}
 第一步：矩阵非空，故算法继续执行。

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

{| border="1" cellpadding="5" cellspacing="0"
! !! 2 !! 3 !! 5 !! 6
|-
! D
| 0 || 1 || 1 || 1
|}
 所以该分支上算法返回失败，从当前局部解中移除A。

 算法继续搜索第1层的下一个分支：

 第1层：选择第B行

 第四步：将第B行加入当前局部解。

 第B行第1列和第4列为1：

{| border="1" cellpadding="5" cellspacing="0"
! !! 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列：

{| border="1" cellpadding="5" cellspacing="0"
! !! 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列：

{| border="1" cellpadding="5" cellspacing="0"
! !! 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列：

{| border="1" cellpadding="5" cellspacing="0"
! !! 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:

{| border="1" cellpadding="5" cellspacing="0"
! !! 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列：

{| border="1" cellpadding="5" cellspacing="0"
! !! 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列：

{| border="1" cellpadding="5" cellspacing="0"
! !! 2 !! 7
|-
! F
| 1 || 1
|}
 第一步：矩阵非空，故算法继续执行。

 第二步：1最少的列为第2列，含有1个1。所以选择第2列。

 第2列中第F行为1，所以选择第F行继续搜索。

 算法继续搜索第3层第一个分支：

 第3层：选择第F行

 第四步：将第F行加入当前局部解。

 第F行第2列和第7列为1：

{| border="1" cellpadding="5" cellspacing="0"
! !! 2 !! 7
|-
! F
| 1 || 1
|}
 第2列中第F行和第7列中第F行均为1。所以移除第F行和第2、7列：

{| border="1" cellpadding="5" cellspacing="0"
! !! 2 !! 7
|-
! F
| 1 || 1
|}
 递归执行算法，回到第一步。
 第一步：矩阵A为空，算法结束，返回成功。

 当前局部解为第B、D、F行，所以最终解即为：

{| border="1" cellpadding="5" cellspacing="0"
! !! 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算法无论在选择行时还是回溯错误的选择时效率都很高。

 参见 
 精确覆盖问题
 双向链表
 舞蹈链

 参考文献 

   .

 外部链接 
 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.

Category:搜尋演算法