版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！

仓库源文，站点原文

title: 笔记 - 精确覆盖问题, 重复覆盖问题与DLX categories:

• 笔记
• 算法竞赛 tags:
• 算法竞赛
• 笔记
• 模板
• 数据结构
• 精确覆盖问题
• X算法
• DLX
• 重复覆盖问题
• 搜索
• 剪枝
• 迭代加深搜索
• IDA*
• 链表
• 双向十字链表 date: 2020-10-25 16:54:34

DLX(Dancing Links X)是一种用于解决精确覆盖问题的优美算法

{% note warning %} https://cplib.tifa-233.com/src/code/util/dlx.hpp 存放了笔者对该算法/数据结构的最新实现, 建议前往此处查看相关代码 {% endnote %}

精确覆盖问题

定义 精确覆盖问题

对有限集 $S={a_i|i\in[1,n]\cap\mathbb{N}}$, 给定集合 $T={T_i\subseteq S|i\in[1,m]\cap\mathbb{N}}$, 设 $T^:={T_i^|i\in[1,l]\cap\mathbb{N},l\leqslant m}\subseteq 2^T$ 满足

• $\displaystyle\bigcup_{T_i^\in T^} T_i^*=S$
• $\forall A,B\in T^*,A\cap B\ne\varnothing\iff A=B$

称 寻找 $T^*$ 这一问题为精确覆盖问题

换句话说就是在给定的 $S$ 若干子集中寻找能精确覆盖 $S$ 的部分

精确覆盖指 $S$ 中任意元素在这些集合中恰好出现一次

如设

$$ S={1,2,3,4,5,6,7} $$

$$ \begin{matrix} T_1 ={1,4,7}&T_2 ={3,5,6}&T_3 ={4,5,7}&T_4 ={2,7}\phantom{,1}\ T_5 ={1,4}\phantom{,1}&T_6 ={3,6}\phantom{,1}&T_7 ={2,3,6}&T_8 ={1,4,6} \end{matrix} $$

则 ${T_2,T_4,T_5}$ 即是我们要找的解

X 算法

X 算法即是一种用于解决精确覆盖问题的算法, 在介绍其流程前, 我们先做一些必要的准备工作

以上节例子为例, 我们先画个这样的表格

$$ \def\arraystretch{1.5} \begin{array}{c|ccccccc} \texttt{head}&1&2&3&4&5&6&7\ \hline 1&1&0&0&1&0&0&1\ 2&0&0&1&0&1&1&0\ 3&0&0&0&1&1&0&1\ 4&0&1&0&0&0&0&1\ 5&1&0&0&1&0&0&0\ 6&0&0&1&0&0&1&0\ 7&0&1&1&0&1&0&0\ 8&1&0&0&1&0&1&0\ \end{array} $$

其中第 $i$ 行第 $j$ 列表示 $T_i$ 内是否有 $a_j$, $1$ 代表有, $0$ 代表没有

可以记作

$$ \begin{matrix} \texttt{h} & \begin{matrix} 1&2&3&4&5&6&7 \end{matrix} \ \begin{matrix} 1\2\3\4\5\6\7\8 \end{matrix} & \begin{bmatrix} 1&0&0&1&0&0&1\ 0&0&1&0&1&1&0\ 0&0&0&1&1&0&1\ 0&1&0&0&0&0&1\ 1&0&0&1&0&0&0\ 0&0&1&0&0&1&0\ 0&1&1&0&1&0&0\ 1&0&0&1&0&1&0\ \end{bmatrix} \end{matrix} $$

为了方便查看, 我们省去多余成分, 并将其看作矩阵, 即

$$ \begin{bmatrix} 1&0&0&1&0&0&1\ 0&0&1&0&1&1&0\ 0&0&0&1&1&0&1\ 0&1&0&0&0&0&1\ 1&0&0&1&0&0&0\ 0&0&1&0&0&1&0\ 0&1&1&0&1&0&0\ 1&0&0&1&0&1&0\ \end{bmatrix} $$

为了方便之后的叙述, 我们做如下约定

X 算法的流程如下

此时我们认为矩阵中的元素即为结点

1. 选取 $|R(l)|>0$ 的行 $l$
2. 如果没有可选行或尝试了所有可选的行仍未找到可行解, 则无解, 返回上一层
3. 记录 $r(l)$
4. 标记并删除 $R(l)$, $C(R(l))$ 和 $R(C(R(l)))$
5. 若矩阵为空矩阵
   1. 若 $R(l)$ 里结点全为 $1$, 则说明找到了一组可行解, 输出所有标记的编号并退出
   2. 若 $R(l)$ 里结点有 $0$, 则不能构成覆盖, 还原删除的结点并返回上一层
6. 对新矩阵递归调用该算法
7. 取消 3 并还原删除的结点

估计看到这里的你们是一脸懵逼的, 下面我们对上例跑一遍流程

强烈建议初学者手动模拟一遍

DLX

我们发现 X 算法涉及大量的删除/恢复某行&列, 所以如果只是暴力实现, 即使它很高效, 我们也很难接受其巨大的常数

所幸真神Donald E. Knuth 设计了一个数据结构(双向十字链表)使得上述操作能高效实现, 同时代码还足够简洁 (原文 点此下载)

因为在双向十字链表上进行删除和恢复操作时可看作是指针在不停跳动, 所以这个数据结构又被称为舞蹈链(Dancing links), 用舞蹈链优化的 X 算法就被叫做DLX 算法(Dancing Links X algorithm)

对于舞蹈链中的一个结点, 其连接方式如下

其删除与恢复自然和双向链表一致

我们看看对下例建立的舞蹈链是什么样子的

$$ \def\arraystretch{1.5} \begin{array}{c:ccccccc} \texttt{head}&1&2&3&4&5&6&7\ \hline 1&1&0&0&1&0&0&1\ 2&0&0&1&0&1&1&0\ 3&0&0&0&1&1&0&1\ 4&0&1&0&0&0&0&1\ 5&1&0&0&1&0&0&0\ 6&0&0&1&0&0&1&0\ 7&0&1&1&0&1&0&0\ 8&1&0&0&1&0&1&0\ \end{array} $$

这回我们略去所有的 $0$, 因为其不会在链表里出现

$$ \begin{matrix} \texttt{head}&1&2&3&4&5&6&7\ \texttt{1}&1& & &1& & &1\ \texttt{2}& & &1& &1&1& \ \texttt{3}& & & &1&1& &1\ \texttt{4}& &1& & & & &1\ \texttt{5}&1& & &1& & & \ \texttt{6}& & &1& & &1& \ \texttt{7}& &1&1& &1& & \ \texttt{8}&1& & &1& &1& \ \end{matrix} $$

对应的舞蹈链就是这样的

代码具体如何实现呢

建议在看完准备工作后自行尝试实现初始化, 删除与恢复操作

准备工作

存储

对于任意一个结点, 其均具有 4 个指针, 也就是

我们也可以用内存池存储

其次, 我们还需要记录结点所在行和列的编号, 最后结点的代码如下

除此之外我们还需如下变量

• width : 宽度(即 $|S|$)
• height : 高度(即 $|B|$)
• cnt_col[] : 每一列的结点数, 用于常数优化

最后代码如下

• Q: head结点, 行首结点和列首结点存在哪里

  A: 实际上

  • 行首结点是虚拟结点, 不需要存

  • head结点存为 node[0]

  • 第 $i$ 列的首结点存为 node[i]

• Q: 常数优化是什么

  A: 见 此节内容

另外

• 为了方便后面写代码, 我们做如下宏定义

  <details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb blog lang:cpp dlx/DLX_macro.cpp %} </details>

初始化

分成两步

• 存入head结点和列首结点
• 存入其他结点

存入head结点和列首结点

存入其他结点

在实现中往往是顺次插入 $R(1)$ 到 $R(h)$ 的, 此时当我们插入某个点x时, 我们发现:

• node[x].l即为上一个插入的结点下标, 即x-1
• node[x].r即为第一个插入的结点下标
• node[x].u即为列首结点上方结点的下标, 即_u(_col(x))
• node[x].d即为列首结点下标, 即_col(x)

代码实现如下

求解

删除

我们这样定义删除操作remove:

• 接收一个参数_col: 代表要删除的列
• 功能是删除某一列和与这一列相交的所有行

结合该图我们不难写出代码

恢复

恢复操作和删除操作类似, 在此不再赘述

上面的都是舞蹈链的操作, 接下来才是重点

dance

我们根据舞蹈链的性质, 对 X 算法流程进行一些调整

1. 选取某一列 $i$ 并对其执行remove操作
2. 枚举 $C(i)$ 中的结点 $j$
   1. 记录 $r(j)$, 对 $R(j)$ 中所有结点的列编号执行remove操作
   2. 若node[head].r == head, 则说明找到了解, 对 $R(j)$ 中所有结点的列编号执行resume操作并返回true
   3. 对 $R(j)$ 中所有结点的列编号执行resume操作
3. 对列 $i$ 中所有结点的列编号执行resume操作
4. 返回false

我们注意到第一步中选取的列不影响最终答案, 所以我们可以加个常数优化, 即选取 $|C(i)|$ 最小的 $i$

值得注意的是, $R(j)$ 删除的顺序和恢复的顺序是相反的, 即若你删除行中结点是从左向右删, 则恢复时要从右向左恢复 (类比递归和回溯的顺序关系)

如果相同则会显著降低代码速度, 具体在后文讲述

我们可以结合例子模拟一遍

加上常数优化后, 代码就是这样的

关于删除和恢复的顺序

我在上面说过: 删除和恢复的方向相同时速度会显著变慢, 这里举一例来具体说明

以下图为例

首先我们先删除

操作	结果
remove 1
remove 3
remove 4

之后我们恢复

方向相反1	方向相同2
resume 4<br>	resume 1<br>
resume 3<br>	resume 3<br>
resume 1<br>	resume 4<br>

我们注意到这两种方式都是正确的, 但是如果删除和恢复的方向相同, 则会重复恢复更多结点, 连带着也会重复赋值更多指针, 所以就会变慢

比较极端的情况可以在 洛谷 P1074 靶形数独 中的数据点#13 找到, 两种不同的恢复顺序能使得最后时间相差十多倍

时间复杂度

不难发现是 $O(c^n)$ 的, 其中 $c$ 是个接近 $1$ 的数, $n$ 是舞蹈链中结点个数

在实际应用中, 因为 $c$ 足够接近 $1$, 所以 DLX 效率很高

例题

• 洛谷 P4929 【模板】舞蹈链（DLX）

  <details open> <summary><font color='orange'>Show code</font></summary> {% icodeweb cpa_cpp title:Luogu_P4929 Luogu/P4929/0.cpp %} </details>

• 洛谷 P1074 靶形数独 -> {% post_link luogu-p1074 题解 %}

• 洛谷 P4205 [NOI2005]智慧珠游戏 -> {% post_link luogu-p4205 题解 %}

重复覆盖问题

从字面意思上看, 重复覆盖问题只需要将精确覆盖问题里的精确覆盖改为可重复覆盖即可

可重复覆盖指 $S$ 中任意元素在这些集合中至少出现一次

因为改为可重复覆盖后很容易出现多解, 所以我们更关心用于覆盖的集合个数最小的解

所以我们定义重复覆盖问题如下

定义 重复覆盖问题

对有限集 $S={a_i|i\in[1,n]\cap\mathbb{N}}$, 给定集合 $T={T_i\subseteq S|i\in[1,m]\cap\mathbb{N}}$, 设 $T^:={T_i^|i\in[1,l]\cap\mathbb{N},l\leqslant m}\subseteq 2^T$ 满足

• $\displaystyle\bigcup_{T_i^\in T^} T_i^*=S$
• $\displaystyle|T^*|=\min_{T'\in 2^T}{|T'|}$

称 寻找 $T^*$ 这一问题为重复覆盖问题

解法

解决重复覆盖问题时我们只需省去在精确覆盖问题中三次标记中的最后一次标记即可

而这样做会导致状态空间爆炸, 所以我们需要做优化

我们发现这和迭代加深搜索的思想有契合之处, 即预设一个最大深度max_depth (在此处即为预设 $|B^*|$ 的最大值 $M$), 然后尝试求解, 根据返回情况调整max_depth

求解的流程如下

1. 选取使 $|C(i)|$ 最小的列 $i$
2. 如果没有可选列或尝试了所有可选列仍未找到可行解, 则返回false
3. 枚举 $C(i)$ 中的结点 $j$
   1. 记录 $r(j)$
   2. 删除 $R(j),C(j)$
   3. 若当前已删除了 $M$ 行且仍为找到结果, 则返回false
   4. 对当前矩阵递归搜索
      1. 若返回true, 则恢复矩阵并返回true
   5. 取消记录 $r(j)$ 并还原删除的结点
4. 还原删除的结点
5. 返回false

我们还可以设计估价函数 $H$ 来加速求解过程, 也就是应用 IDA*

接下来枚举或者二分max_depth即可

附模板, 输入方式与 洛谷 P4929 【模板】舞蹈链（DLX） 相同

例题

• POJ 1084 Square Destroyer
• FZU 1686 神龙的难题

参考资料

• https://www.cnblogs.com/grenet/p/3145800.html
• https://leverimmy.top/posts/lectures/dlx
• https://blog.csdn.net/whereisherofrom/article/details/79220897