算法——舞蹈链算法

一，基本概念

算法简介 

        舞蹈链算法（Dancing Links，简称 DLX）是一种高效解决精确覆盖问题的算法，实际上是一种数据结构，可以用来实现 X算法，以解决精确覆盖问题。由高德纳（Donald E. Knuth）提出 。

精准覆盖 

        什么是精确覆盖（Exact Cover）问题呢？就是在一个全集X中若干子集的集合为S。S* 是 S的一个子集，当且仅当X中的每一个元素在S*中恰好出现一次时，S*称之为一个精确覆盖。在计算机科学中，精确覆盖问题指找出这样的一种覆盖，或证明其不存在。这是一个NP-完全问题。

舞蹈链

        其实是一种特殊的数据结构，用于高效地实现对精确覆盖问题的求解。它基于双向循环链表，每个节点除了包含指向左右节点的指针外，还包含指向上方和下方节点的指针，这种结构使得在搜索过程中能够快速地对链表进行插入、删除和恢复操作。

数据结构设计

每个1的节点包含四个指针：left, right, up, down，形成双向十字链表。

每列有一个列头节点，记录该列中1的数量（用于优化搜索顺序）。

算法流程

1. 选择列：优先选择当前剩余1最少的列（减少搜索分支）。

2. 覆盖列：删除该列及其关联的所有行（避免后续搜索冲突）。

3. 递归搜索：对剩余矩阵重复上述步骤。

4. 回溯恢复：若当前路径无解，恢复被删除的列和行，尝试其他分支。

5. 结束条件：当舞蹈链中的所有列都被覆盖（即矩阵中所有列都被删除）时，找到了一个精确覆盖解；如果遍历完所有可能的分支都没有找到解，则说明该问题无解。

 二，示例

例如，S = {A，B，C，D，E，F} 是全集 X = {1，2，3，4，5，6，7} 的一个子集的集合，其中：

A = {1, 4, 7}

B = {1, 4}

C = {4, 5, 7}

D = {3, 5, 6}

E = {2, 3, 6, 7}

F = {2, 7}

那么，S的一个子集 S* = {B, D, F} 是X的一个精确覆盖，因为 X 中的每个元素恰好在S*中出现了一次。

可以用0-1矩阵来表示精确覆盖问题。我们用矩阵的每行表示S的一个元素，也就是X的一个子集；用矩阵的每列表示X的一个元素。矩阵中的1代表这一列的元素存在于这一行对应的子集中，0代表不存在。那么精确覆盖问题可以转化成求出矩阵若干行的集合，使得集合中的每一列恰好都有一个1。

比如前面的问题可以用矩阵的形式表示成

那么选择红色的B，D，F能满足每列都恰好包含一个1。

可以用 Knuth 提出的X算法来解决精确覆盖问题。X算法是一个非确定性的深度优先回溯算法。它的具体步骤如下：

1. 如果矩阵

为空（没有任何列），则当前局部解即为问题的一个解，返回成功；否则继续。

2. 根据一定方法选择第 c 列。如果某一列中没有 1，则返回失败，并去除当前局部解中最新加入的行。

选择第 r 行，使得

（该步是非确定性的）。

将第 r 行加入当前局部解中。

对于满足

的每一列j，从矩阵

中删除所有满足

的行，最后再删除第 j 列。

对所得比 A 小的新矩阵递归地执行此算法。

让我们用 X算法解决上面的精确覆盖问题。

首先，当前矩阵不为空，算法继续进行。那么先选择1最少的一列。因为 1，2，3，5，6 列都只有 2 个 1，因此我们随便选择 1 个，比如第 1 列。

行 A 和 B 都含有 1，因此要在这两行中进行选择。

先尝试选择行 A。将行A加入到当前的解中。

行A的 1，4，7 列为 1，根据第 5 步，需要把所有在 1，4，7 列中含有 1 的行都删除掉，因此需要删除掉行A，B，C，E，F，同时删除掉第 1，4，7 列

删除之后，矩阵只剩下行 D 和第 2，3，5，6 列：

进入递归，回到第 1 步，矩阵非空，算法继续执行。

再进入第2步，此时选择 1 最少的第 2 列，里面没有 1，因此返回失败，同时将行 A 从当前的解中移除；

算法进入另一个分支，选择行 B，并将其加入到当前的解中：

行 B 的第 1，4 列为 1，因此要把 1，4 列中包含 1 的行都删掉。需要删除掉行 A，B，C，再删除掉 1，4 列。

此时矩阵变为

进入递归，回到第 1 步，矩阵非空，因此算法继续。

当前包含 1 最少的一列是第 5 列，那么将从第 5 列中选择含有 1 的行进行搜索。

第 5 列中行 D 含有 1，因此选择行 D，将其加入当前解中，算法进入新的一层搜索。

行 D 的第 3，5，6 列包含 1，我们要删掉这几列中包含 1 的所有行，同时删掉这几列

那么我们需要删掉行 D，E 和第 3，5，6 列，矩阵变为

再次递归执行，回到第 1 步，矩阵非空，因此算法继续

选择当前包含 1 最少的一列，这里选择第 2 列。第 2 列中只有行 F 包含 1， 因此选择行 F

将行 F 加入到当前解中，算法进入第 3 层搜索

行 F 中第 2，7列为 1，第 2，7 列中行 F 包含 1，因此移除行 F 和第 2，7 列

算法再次进入递归执行，回到第 1 步，此时所有的列都被移除了，矩阵为空，因此返回成功，找到了一个解：{B, D, F}

继续搜索，没有其他可以选择的行，返回上一层；

第2层也没有其他可以选择的行，再返回上一层；

第1层也没有其他可以选择的行，再返回上一层；

第0层也没有其他可以选择的行，算法终止。

以上就是 X 算法的执行过程。Knuth 提出 X 算法主要是为了说明舞蹈链的作用，他发现用舞蹈链来执行 X 算法效率特别高。那么什么是舞蹈链呢？它是基于双向链表的一种数据结构。

让我们先来看看双向链表：

上图是一个简单的双向链表，每个节点有两个指针，分别指向自己的前驱和后继节点。那么如果我们想把其中一个节点，比如 B 从链表中删掉，只需要执行下面的操作：

B.left.right = B.rightB.right.left = B.left

注意：此时虽然 B 从链表中移除了，但它的两个指针依然保持不变，还是指向之前的前驱和后继节点。

因此，如果我想把 B 再添加到链表原来的位置上，此时并不需要修改 B 的指针，只需要再把 B 的前驱和后继节点的指针恢复就可以了：

B.left.right = BB.right.left = B

理解了这一点之后，让我们再来看看舞蹈链的结构是怎么样的：

上面这个图是一个舞蹈链的结构，描述的是前面 X 算法中用到的矩阵。它由几部分构成：

最上面的蓝色部分是一个水平的环状双向链表。最左边是头节点，它是整个数据结构的根节点。其余是列头节点，每个代表矩阵中的一列。

每一列又是一个纵向的环状双向链表。除了最上面的列头节点，其他的每个节点都代表前面的矩阵中的一个 1。这实际上是一个稀疏矩阵，为了优化存储和效率，只保留了值为 1 的节点，把每个节点按顺序保存到数组中。最早的 Dancing Links 算法，也就是 Knuth 在 2000 年发表的论文中，下面的每一行也都是一个双向链表。但后来他发现每一行在算法执行过程中实际上不会发生变化，因此他把水平的双向链表取消了，只保留了最顶上的列头节点之间的水平双向链表。下面的每一行之间的前后节点可以直接通过数组的索引得到。两边是Space节点，用来标记一行的开始和结束。

每个普通节点 A 都包含 4 个 字段，A.up 和 A.down 代表双向链表的两个指针，分别指向 A 上面和下面的节点。还有一个 A.col ，指向 A 所在列的头节点，需要根据这个字段定位到节点所在的列。另外还有一个 A.row，主要是方便在递归的过程中缓存当前的解。

列头节点还要再多几个字段，left 和 right 分别指向水平双向链表的左节点和右节点。另外还有一个 count 字段，代表这一列当前一共有几个元素。X 算法的第 2 步，选择 1 最少的列时会用到这个字段。

理解了舞蹈链的数据结构之后，我们再来看看是怎样用舞蹈链来实现 X 算法的。这部分算法很精妙，也是舞蹈链这个名字的来由，通过对链表上的节点反复删除和插入实现了递归的回溯，就好像一个个链表在舞台上翩翩起舞一样。

具体的算法实现可以参照 Knuth 的论文，我们还是用图的方式来说明一下。

（1）首先，判断链表是否为空，可以通过 head.right == head 来判断。如果为空则返回，并输出当前的解。

（2）不为空则选择当前节点数最少的列。如果只有列头节点，则返回失败。

遍历这一列的每个节点，开始进行覆盖操作：

（1）首先将节点所在行作为解的一部分，加入到当前解中；

（2）遍历这一行的所有节点，将每个节点所在列都删除掉，同时删除掉与这些列有交集的所有行：

2a. 遍历节点所在列的每个节点，将每个节点所在行的所有节点从它所在的列中移除掉，同时将列头节点的计数减 1：

node.up.down = node.downnode.down.up = node.upcol_node.count -= 1

2b. 还要将这一列从链表中移除：

col_node.left.right = col_node.rightcol_node.right.left = col_node.left

进入递归调用，判断链表是否为空；

不为空则选择节点数最少的列，再遍历这一列的节点，进行覆盖操作：

移除掉所有节点之后，进入递归调用，发现链表不为空，但节点数最少的列中没有普通节点了，返回失败；

开始做链表的还原操作。注意还原的顺序需要和移除的顺序相反。如果我们是从上至下，从左至右移除节点，那么还原的时候就从右至左，从下至上。否则的话可能会出现问题，导致一个节点被还原多次，这样列中节点的计数就不准确了。

node.up.down = nodenode.down.up = nodecol_node.count += 1

并且把删除的列也取消覆盖

col_node.left.right = col_nodecol_node.right.left = col_node

递归返回到上一层，还原之后，发现列中没有其他节点可以选择，再返回到上一层，选择下一个节点所在的行。

和之前的方法相同，遍历这一行的所有节点，将每个节点所在列都删除掉，同时删除掉与这些列有交集的所有行：

再选择节点最少的列，遍历这一列的所有节点的所在行：

遍历这一行的所有节点，删除掉每个节点所在列，以及与这些列有交集的所有行：

再次进入递归调用，判断矩阵不为空，选择节点最少的一列，遍历每个节点，删除掉所在行的所有列，与这些列有交集的所有行，最后我们得到一个空矩阵。

此时将得到的解输出，并返回，接下来还要进行还原操作，然后搜索下一个解。

三、代码

class Node:def __init__(self):self.left = self.right = self.up = self.down = selfself.column = None  # 列头节点self.row = None     # 行标识def solve(matrix):# 构建舞蹈链head = build_dancing_links(matrix)solution = []search(head, solution)def search(head, solution):if head.right == head:# 找到解，输出结果return True# 选择1最少的列col = choose_column(head)cover(col)# 遍历该列的每一行row_node = col.downwhile row_node != col:solution.append(row_node.row)# 覆盖该行关联的所有列right_node = row_node.rightwhile right_node != row_node:cover(right_node.column)right_node = right_node.right# 递归搜索if search(head, solution):return True# 回溯solution.pop()left_node = row_node.leftwhile left_node != row_node:uncover(left_node.column)left_node = left_node.leftrow_node = row_node.downuncover(col)return False

class Node:def __init__(self):self.left = self.right = self.up = self.down = selfself.col = self.row = Noneclass DLX:def __init__(self):self.root = Node()self.columns = {}self.answer = []def add_column(self, name):node = Node()node.col = nodenode.row = Nonenode.left = self.root.leftnode.right = self.rootself.root.left.right = nodeself.root.left = nodeself.columns[name] = nodedef add_row(self, row_data):first = Nonelast = Nonefor col_name, value in row_data.items():if value == 1:node = Node()node.col = self.columns[col_name]node.row = row_datanode.up = node.col.upnode.down = node.colnode.col.up.down = nodenode.col.up = nodeif first is None:first = nodeelse:last.right = nodenode.left = lastlast = nodefirst.left = lastlast.right = firstdef cover_column(self, col):col.right.left = col.leftcol.left.right = col.righti = col.downwhile i!= col:j = i.rightwhile j!= i:j.down.up = j.upj.up.down = j.downj = j.righti = i.downdef uncover_column(self, col):i = col.upwhile i!= col:j = i.leftwhile j!= i:j.down.up = jj.up.down = jj = j.lefti = i.upcol.right.left = colcol.left.right = coldef search(self, k):if self.root.right == self.root:print("Solution found:", self.answer)return Truec = self.root.righti = c.downmin_size = float('inf')while i!= c:size = 0j = i.rightwhile j!= i:size += 1j = j.rightif size < min_size:min_size = sizec = ii = i.downself.cover_column(c.col)i = c.downwhile i!= c:self.answer.append(i.row)j = i.rightwhile j!= i:self.cover_column(j.col)j = j.rightif self.search(k + 1):return Trueself.answer.pop()i = i.downj = i.leftwhile j!= i:self.uncover_column(j.col)j = j.leftself.uncover_column(c.col)return False

 运行

# 使用示例
dlx = DLX()
dlx.add_column('C1')
dlx.add_column('C2')
dlx.add_column('C3')
dlx.add_row({'C1': 1, 'C2': 0, 'C3': 1})
dlx.add_row({'C1': 0, 'C2': 1, 'C3': 1})
dlx.add_row({'C1': 1, 'C2': 1, 'C3': 0})
dlx.search(0)

四、算法优势

• 高效剪枝：通过列头节点统计剩余1的数量，优先选择约束最强的列，大幅减少搜索空间。

• 快速状态恢复：链表删除和恢复的时间复杂度为O(1)，回溯代价极低。

• 通用性：适用于所有可转化为精确覆盖的问题。

五、应用领域

• 数独求解：数独问题可以很自然地转化为精确覆盖问题，舞蹈链算法能够快速有效地解决数独谜题，无论是人工设计的数独题目还是大规模生成数独游戏。
• 计算机视觉：在图像分割、目标识别等任务中，舞蹈链算法可用于解决一些组合优化问题，例如将图像中的像素点精确地划分到不同的目标区域。
• 网络设计：在网络拓扑设计、资源分配等方面，舞蹈链算法可以帮助找到满足特定要求的最优网络配置方案，例如在保证网络连通性的前提下，合理分配网络设备和链路资源。

• N皇后问题：将棋盘转化为精确覆盖矩阵。

• 拼图游戏：如俄罗斯方块填充、多米诺骨牌覆盖等。

总结

舞蹈链算法通过双向链表的动态调整，将精确覆盖问题的搜索效率提升到极致。尽管实现复杂，但它在处理组合优化问题时表现卓越，尤其适合约束严格的场景。理解其核心在于掌握链表操作与回溯思想的结合。