茶年 · 中文维基百科

舞蹈链

Wikipedia · 2026-06-18 维基百科 👁 1 阅读

问题的舞蹈链算法]]
在计算机科学中，舞蹈链（Dancing Links）算法，也叫DLX算法，是一种高德纳提出的数据结构，用于是快速实现他提出的的X算法。 X算法是一种递归算法，时间复杂度不确定，深度优先，通过回溯寻找精确覆盖问题所有可能的解。有一些著名的精确覆盖问题，包括铺砖块，八皇后问题，数独问题。

这一算法的名字来自于这个算法的工作方式。算法中的迭代让链接与同伴链接"跳舞"，很像“精心编排的舞蹈”。 该算法归功于 Hiroshi Hitotsumatsu 与 Kōhei Noshita 在1979的研究 ， 但Knuth的论文使得舞蹈链算法流行开来。

算法实现
文章的剩余部分将讨论这种算法在X算法中的应用，强烈建议读者先阅读 X算法 。

主要思想
舞蹈链的主要思想来自于 双向链表

x.left.right ← x.right;
x.right.left ← x.left;

以上代码会从链表中移除x元素

x.left.right ← x;
x.right.left ← x;

以上代码会恢复x元素在链表中的位置（如果x的左侧元素和右侧元素没有发生变动）。无论链表中有多少个元素，该算法均可以工作。

高德纳发现用朴素算法实现X算法时需要花费大量的时间来搜索1。当要选择一列的时候，要搜索整个矩阵来找到1。当选择一行的时候，需要在整列中搜索1。为了把搜索时间从 O(n)的时间复杂度 降到 O(1)， 高德纳使用了一个稀疏矩阵，只存放所有1的位置。

无论何时，矩阵中的每个节点都会与左边和右边的节点（原始矩阵中的1的位置）、上面和下面（原始矩阵中同一列的1），以及列头连接。每一行和每一列都会形成一个双向链表。

链表头
每一列都会有特殊的，叫做“列头”的节点，作为列表中的一部分。列头形成了特殊的一行（称为“控制行”），包括了原始矩阵中还存在的每一列。

最后，每一列的头会记录这一列中节点的个数，我们可以在O(n) 的时间复杂度（而非O(n×m)）内用这些信息来定位节点最少的一列，其中n指列的总数，m指的是行的总数。选择节点最少的一列来进行搜索在一些情况下可以提高性能，但不是每个问题中都需要这么做。

搜索
在X算法中，行与列是按照规则生成的，存储着原始矩阵。每次移除一列以及那列中的一行。如果选中的列没有包括任何行，当前的矩阵是无解的，必须回溯。当移除元素时，每一列中与那一行有交叉点的（原始矩阵中的1）都会被移除。列被移除了，因为他们已经被填满，行被移除是因为他们与指定的列有冲突。要移除某一列，要先移除那列的头，接着，遍历所有与这一列有交集的行，把那行与其他行的交点都去掉（这样阻止了这些列与当前列的冲突）。对包含1的列重复这样的列移除操作。这样的做法保证每个节点只被移除一次，并且按照顺序，这样就可以正确地回溯了。如果代入过程的矩阵没有任何的行，那么这已经被填满，选中的列就是一个解。

回溯
回溯操作需要使用前面提到的第二个算法，将之前的操作反过来再次操作一次。Knuth 的论文提供了一个清晰的这两个操作的关系以及移除、恢复操作的具体方式，并放宽了要求。

有可能出现的约束因素
算法也可以解决一个特定的约束是可选的覆盖问题，但是可以满足最多一次。 舞蹈链接可容纳这些必须填充的主要列，次要列是可选的。 这将算法的解决方案测试从没有列的矩阵改变为没有主列的矩阵，并且如果正在使用列中1最少的启发式搜索，那么只需在主列中检查。 Knuth讨论了应用于n皇后问题的可选约束。 棋盘对角线表示可选的约束，因为一些对角线可能不被占用。 如果一个对角线被占用，它只能被占用一次。

參考資料
外部連結

#搜尋演算法 #數獨

评论 (0)

  • 还没有评论，来抢沙发吧。