Dancing Links
本页面将介绍精确覆盖问题、重复覆盖问题,解决这两个问题的算法「X 算法」,以及用来优化 X 算法的双向十字链表 Dancing Link。本页也将介绍如何在建模的配合下使用 DLX 解决一些搜索题。
精确覆盖问题
定义
精确覆盖问题(英文:Exact Cover Problem)是指给定许多集合
解释
例如,若给出
则
问题转化
将
给定一个 01 矩阵,你可以选择一些行(row),使得最终每列(column)1都恰好有一个 1。 举个例子,我们对上文中的例子进行建模,可以得到这么一个矩阵:
其中第
行表示着 ,而这一行的每个数依次表示 。
实现
暴力 1
一种方法是枚举选择哪些行,最后检查这个方案是否合法。
因为每一行都有选或者不选两种状态,所以枚举行的时间复杂度是
而每次检查都需要
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
暴力 2
考虑到 01 矩阵的特殊性质,每一行都可以看做一个
因此原问题转化为
给定
个 位二进制数,要求选择一些数,使得任意两个数的与都为 0,且所有数的或为 。 tmp
表示的是截至目前被选中的二进制数的或。
因为每一行都有选或者不选两种状态,所以枚举行的时间复杂度为
而每次计算 tmp
都需要
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
重复覆盖问题
重复覆盖问题与精确覆盖问题类似,但没有对元素相似性的限制。下文介绍的 X 算法 原本针对精确覆盖问题,但经过一些修改和优化(已标注在其中)同样可以高效地解决重复覆盖问题。
X 算法
Donald E. Knuth 提出了 X 算法 (Algorithm X),其思想与刚才的暴力差不多,但是方便优化。
过程
继续以上文中中提到的例子为载体,得到一个这样的 01 矩阵:
-
此时第一行有
个 ,第二行有 个 ,第三行有 个 ,第四行有 个 ,第五行有 个 ,第六行有 个 。选择第一行,将它删除,并将所有 所在的列打上标记; -
选择所有被标记的列,将它们删除,并将这些列中含
的行打上标记(重复覆盖问题无需打标记); -
选择所有被标记的行,将它们删除;
这表示这一行已被选择,且这一行的所有
所在的列不能有其他 了。于是得到一个新的小 01 矩阵:
-
此时第一行(原来的第二行)有
个 ,第二行(原来的第四行)有 个 ,第三行(原来的第五行)有 个 。选择第一行(原来的第二行),将它删除,并将所有 所在的列打上标记; -
选择所有被标记的列,将它们删除,并将这些列中含
的行打上标记; -
选择所有被标记的行,将它们删除;
这样就得到了一个空矩阵。但是上次删除的行
1 0 1 1
不是全 的,说明选择有误; -
回溯到步骤 4,考虑选择第二行(原来的第四行),将它删除,并将所有
所在的列打上标记; -
选择所有被标记的列,将它们删除,并将这些列中含
的行打上标记; -
选择所有被标记的行,将它们删除;
于是我们得到了这样的一个矩阵:
-
此时第一行(原来的第五行)有
个 ,将它们全部删除,得到一个空矩阵: -
上一次删除的时候,删除的是全
的行,因此成功,算法结束。答案即为被删除的三行:
。
强烈建议自己模拟一遍矩阵删除、还原与回溯的过程后,再接着阅读下文。
通过上述步骤,可将 X 算法的流程概括如下:
- 对于现在的矩阵
,选择并标记一行 ,将 添加至 中; - 如果尝试了所有的
却无解,则算法结束,输出无解; - 标记与
相关的行 和 (相关的行和列与 X 算法 中第 2 步定义相同,下同); - 删除所有标记的行和列,得到新矩阵
; -
如果
为空,且 为全 ,则算法结束,输出被删除的行组成的集合 ;如果
为空,且 不全为 ,则恢复与 相关的行 以及列 ,跳转至步骤 1;如果
不为空,则跳转至步骤 1。
不难看出,X 算法需要大量的「删除行」、「删除列」和「恢复行」、「恢复列」的操作。
一个朴素的想法是,使用一个二维数组存放矩阵,再用四个数组分别存放每一行与之相邻的行编号,每次删除和恢复仅需更新四个数组中的元素。但由于一般问题的矩阵中 0 的数量远多于 1 的数量,这样做的空间复杂度难以接受。
Donald E. Knuth 想到了用双向十字链表来维护这些操作。
而在双向十字链表上不断跳跃的过程被形象地比喻成「跳跃」,因此被用来优化 X 算法的双向十字链表也被称为「Dancing Links」。
Dancing Links 优化的 X 算法
预编译命令
1 |
|
定义
双向十字链表中存在四个指针域,分别指向上、下、左、右的元素;且每个元素
大型的双向链表则更为复杂:
每一行都有一个行首指示,每一列都有一个列指示。
行首指示为 first[]
,列指示是我们新建的 first[]
数组,直接指向 这一行中的首元素。
同时,每一列都有一个 siz[]
表示这一列的元素个数。
特殊地,
1 2 3 4 |
|
过程
remove 操作
remove(c)
表示在 Dancing Links 中删除第
先将
左侧的结点的右结点应为 的右结点。 右侧的结点的左结点应为 的左结点。
即 L[R[c]] = L[c], R[L[c]] = R[c];
。
然后顺着这一列往下走,把走过的每一行都删掉。
如何删掉每一行呢?枚举当前行的指针
上方的结点的下结点应为 的下结点。 下方的结点的上结点应为 的上结点。
注意要修改每一列的元素个数。
即 U[D[j]] = U[j], D[U[j]] = D[j], --siz[col[j]];
。
remove
函数的代码实现如下:
实现
1 2 3 4 5 6 7 8 9 |
|
recover 操作
recover(c)
表示在 Dancing Links 中还原第
recover(c)
即 remove(c)
的逆操作,这里不再赘述。
值得注意的是, recover(c)
的所有操作的顺序与 remove(c)
的操作恰好相反。
recover(c)
的代码实现如下:
实现
1 2 3 4 5 |
|
build 操作
build(r, c)
表示新建一个大小为
新建
第
于是我们得到了一个环状双向链表:
这样就初始化了一个 Dancing Links。
build(r, c)
的代码实现如下:
实现
1 2 3 4 5 6 7 8 9 10 |
|
insert 操作
insert(r, c)
表示在第
插入操作分为两种情况:
-
如果第
行没有元素,那么直接插入一个元素,并使first[r]
指向这个元素。这可以通过
first[r] = L[idx] = R[idx] = idx;
来实现。 -
如果第
行有元素,那么将这个新元素用一种特殊的方式与 和 连接起来。设这个新元素为
,然后:-
把
插入到 的正下方,此时: 下方的结点为原来 的下结点; 下方的结点(即原来 的下结点)的上结点为 ; 的上结点为 ; 的下结点为 。
注意记录
的所在列和所在行,以及更新这一列的元素个数。1 2
col[++idx] = c, row[idx] = r, ++siz[c]; U[idx] = c, D[idx] = D[c], U[D[c]] = idx, D[c] = idx;
强烈建议读者完全掌握这几步的顺序后再继续阅读本文。
-
把
插入到 的正右方,此时: 右侧的结点为原来 的右结点;- 原来
右侧的结点的左结点为 ; 的左结点为 ; 的右结点为 。
1 2
L[idx] = first[r], R[idx] = R[first[r]]; L[R[first[r]]] = idx, R[first[r]] = idx;
强烈建议读者完全掌握这几步的顺序后再继续阅读本文。
-
insert(r, c)
这个操作可以通过图片来辅助理解:
留心曲线箭头的方向。
insert(r, c)
的代码实现如下:
实现
1 2 3 4 5 6 7 8 9 10 |
|
dance 操作
dance()
即为递归地删除以及还原各个行列的过程。
- 如果
号结点没有右结点,那么矩阵为空,记录答案并返回; - 选择列元素个数最少的一列,并删掉这一列;
- 遍历这一列所有有
的行,枚举它是否被选择; - 递归调用
dance()
,如果可行,则返回;如果不可行,则恢复被选择的行; - 如果无解,则返回。
dance()
的代码实现如下:
实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
|
其中 stk[]
用来记录答案。
注意我们每次优先选择列元素个数最少的一列进行删除,这样能保证程序具有一定的启发性,使搜索树分支最少。
对于重复覆盖问题,在搜索时可以用估价函数(与 A* 中类似)进行剪枝:若当前最好情况下所选行数超过目前最优解,则可以直接返回。
模板
模板代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 |
|
性质
DLX 递归及回溯的次数与矩阵中
但实际情况下 DLX 表现良好,一般能解决大部分的问题。
建模
DLX 的难点,不全在于链表的建立,而在于建模。
请确保已经完全掌握 DLX 模板后再继续阅读本文。
我们每拿到一个题,应该考虑行和列所表示的意义:
-
行表示决策,因为每行对应着一个集合,也就对应着选/不选;
-
列表示状态,因为第
列对应着某个条件 。
对于某一行而言,由于不同的列的值不尽相同,我们 由不同的状态,定义了一个决策。
例题 1 P1784 数独
解题思路
先考虑决策是什么。
在这一题中,每一个决策可以用形如
注意到「宫」并不是决策的参数,因为它 可以被每个确定的
因此有
再考虑状态是什么。
我们思考一下
- 第
行用了一个 (用 列表示); - 第
列用了一个 (用 列表示); - 第
宫用了一个 (用 列表示); 中填入了一个数(用 列表示)。
因此有
至此,我们成功地将
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 |
|
例题 2 靶形数独
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
|
例题 3 「NOI2005」智慧珠游戏
解题思路
定义:题中给我们的智慧珠的形态,称为这个智慧珠的标准形态。
显然,我们可以通过改变两个参数
仍然,我们先考虑决策是什么。
在这一题中,每一个决策可以用形如
表示第
巧合的是,我们可以令
因此有
需要注意的是,因为一些不合法的填充,如
所以 在实际操作中,空的智慧珠棋盘也只需要建出
再考虑状态是什么。
这一题的状态比较简单。
我们思考一下,
- 某些格子被占了(用
列表示); - 第
个智慧珠被用了(用 列表示)。
因此有
至此,我们成功地将智慧珠游戏转化成了一个 有
参考代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 |
|
习题
外部链接
- 夜深人静写算法(九)- Dancing Links X(跳舞链)_WhereIsHeroFrom 的博客》
- 跳跃的舞者,舞蹈链(Dancing Links)算法——求解精确覆盖问题 - 万仓一黍
- DLX 算法一览 - zhangjianjunab
- 搜索:DLX 算法 - 静听风吟。
- 《算法竞赛入门经典 - 训练指南》
注释
-
(两岸用语差异)台灣:直行(column)、橫列(row) ↩
本页面最近更新:2024/2/5 00:05:06,更新历史
发现错误?想一起完善? 在 GitHub 上编辑此页!
本页面贡献者:383494, leverimmy, CCXXXI, dkz051, EarthMessenger, Enter-tainer, Great-designer, iamtwz, Ir1d, kenlig, Konano, ksyx, L1nkzz, LeverImmy, NachtgeistW, opsiff, ouuan, SamZhangQingChuan, StudyingFather, W-RJ
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供,附加条款亦可能应用