网站建设的目标和需求分析,国外的有趣设计网站,网站开发实战asp制作视频,jquery 网站源码一#xff0c;基本概念
算法简介 舞蹈链算法#xff08;Dancing Links#xff0c;简称 DLX#xff09;是一种高效解决精确覆盖问题的算法#xff0c;实际上是一种数据结构#xff0c;可以用来实现 X算法#xff0c;以解决精确覆盖问题。由高德纳#xff08;Donald E.…一基本概念
算法简介 舞蹈链算法Dancing Links简称 DLX是一种高效解决精确覆盖问题的算法实际上是一种数据结构可以用来实现 X算法以解决精确覆盖问题。由高德纳Donald E. Knuth提出 。
精准覆盖 什么是精确覆盖Exact Cover问题呢就是在一个全集X中若干子集的集合为S。S* 是 S的一个子集当且仅当X中的每一个元素在S*中恰好出现一次时S*称之为一个精确覆盖。在计算机科学中精确覆盖问题指找出这样的一种覆盖或证明其不存在。这是一个NP-完全问题。
舞蹈链 其实是一种特殊的数据结构用于高效地实现对精确覆盖问题的求解。它基于双向循环链表每个节点除了包含指向左右节点的指针外还包含指向上方和下方节点的指针这种结构使得在搜索过程中能够快速地对链表进行插入、删除和恢复操作。
数据结构设计
每个1的节点包含四个指针left, right, up, down形成双向十字链表。
每列有一个列头节点记录该列中1的数量用于优化搜索顺序。
算法流程 选择列优先选择当前剩余1最少的列减少搜索分支。 覆盖列删除该列及其关联的所有行避免后续搜索冲突。 递归搜索对剩余矩阵重复上述步骤。 回溯恢复若当前路径无解恢复被删除的列和行尝试其他分支。 结束条件当舞蹈链中的所有列都被覆盖即矩阵中所有列都被删除时找到了一个精确覆盖解如果遍历完所有可能的分支都没有找到解则说明该问题无解。 二示例 例如S {ABCDEF} 是全集 X {1234567} 的一个子集的集合其中
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。
比如前面的问题可以用矩阵的形式表示成 那么选择红色的BDF能满足每列都恰好包含一个1。
可以用 Knuth 提出的X算法来解决精确覆盖问题。X算法是一个非确定性的深度优先回溯算法。它的具体步骤如下
1. 如果矩阵 为空没有任何列则当前局部解即为问题的一个解返回成功否则继续。
2. 根据一定方法选择第 c 列。如果某一列中没有 1则返回失败并去除当前局部解中最新加入的行。
选择第 r 行使得 该步是非确定性的。
将第 r 行加入当前局部解中。
对于满足 的每一列j从矩阵 中删除所有满足 的行最后再删除第 j 列。
对所得比 A 小的新矩阵递归地执行此算法。
让我们用 X算法解决上面的精确覆盖问题。
首先当前矩阵不为空算法继续进行。那么先选择1最少的一列。因为 12356 列都只有 2 个 1因此我们随便选择 1 个比如第 1 列。 行 A 和 B 都含有 1因此要在这两行中进行选择。
先尝试选择行 A。将行A加入到当前的解中。 行A的 147 列为 1根据第 5 步需要把所有在 147 列中含有 1 的行都删除掉因此需要删除掉行ABCEF同时删除掉第 147 列 删除之后矩阵只剩下行 D 和第 2356 列 进入递归回到第 1 步矩阵非空算法继续执行。
再进入第2步此时选择 1 最少的第 2 列里面没有 1因此返回失败同时将行 A 从当前的解中移除
算法进入另一个分支选择行 B并将其加入到当前的解中 行 B 的第 14 列为 1因此要把 14 列中包含 1 的行都删掉。需要删除掉行 ABC再删除掉 14 列。 此时矩阵变为 进入递归回到第 1 步矩阵非空因此算法继续。
当前包含 1 最少的一列是第 5 列那么将从第 5 列中选择含有 1 的行进行搜索。 第 5 列中行 D 含有 1因此选择行 D将其加入当前解中算法进入新的一层搜索。 行 D 的第 356 列包含 1我们要删掉这几列中包含 1 的所有行同时删掉这几列 那么我们需要删掉行 DE 和第 356 列矩阵变为 再次递归执行回到第 1 步矩阵非空因此算法继续
选择当前包含 1 最少的一列这里选择第 2 列。第 2 列中只有行 F 包含 1 因此选择行 F
将行 F 加入到当前解中算法进入第 3 层搜索 行 F 中第 27列为 1第 27 列中行 F 包含 1因此移除行 F 和第 27 列 算法再次进入递归执行回到第 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皇后问题将棋盘转化为精确覆盖矩阵。 拼图游戏如俄罗斯方块填充、多米诺骨牌覆盖等。 总结
舞蹈链算法通过双向链表的动态调整将精确覆盖问题的搜索效率提升到极致。尽管实现复杂但它在处理组合优化问题时表现卓越尤其适合约束严格的场景。理解其核心在于掌握链表操作与回溯思想的结合。
