[科普中国]-X算法

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

X算法的步骤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最少的列1。

实现高德纳主要想通过X算法体现舞蹈链的实用性。他发现了使用舞蹈链的X算法效率极高，并把这一过程称为DLX。DLX用矩阵来表示精确覆盖问题，在内部的存储结构为舞蹈链。舞蹈链是一个双向环形链表，每个矩阵中的1都有一个指针指向其左、右、上、下的1。因为精确覆盖问题中的矩阵一般都是稀疏的，所以舞蹈链中的元素很少，既很省时间，又很省空间。可见使用舞蹈链的DLX算法无论在选择行时还是回溯错误的选择时效率都很高。

本词条内容贡献者为:

王沛 - 副教授、副研究员 - 中国科学院工程热物理研究所