X算法

在计算机科学中，X算法可用来求解精确覆盖问题。此名称最早在高德纳的论文《舞蹈链》中出现，他认为此算法是“试错法中最显而易见”的。 就技术而言，X算法是一个深度优先的回溯算法。由于X算法是一个解决精确覆盖问题的简洁方法，高德纳希望通过该算法体现舞蹈链数据结构的高效性，他把使用后者的X算法称为DLX。 X算法用由0和1组成的矩阵A来表示精确覆盖问题，目标是选出矩阵的若干行，使得其中的1在所有列中出现且仅出现一次。 X算法的步骤如下： 选择r的不确定性意味着算法将衍生出若干独立的子算法，每个子算法都从其父算法中继承了去除部分行列的A矩阵。如果其中有一列全为零，则当前情况无解，子算法返回失败，但不一定意味整个问题无解。 实际上，所有子算法形成了一棵搜索树，其中原问题为根节点，树的第k层由子算法在第k次所选择的行组成。整个算法即用回溯法对搜索树深度优先遍历。 第二步中，无论用什么方法选择列最终都可以得到解，但有的方法效率明显较高。为减少迭代次数，高德纳建议每次都选取1最少的列。