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