笔记 - 精确覆盖问题，重复覆盖问题与 DLX

发表于 更新于 分类于 ， 本文字数： 4.9k 阅读时长 ≈ 18 分钟

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

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

精确覆盖问题

定义 精确覆盖问题

对有限集 \(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} \]

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

表达式 含义
\(w\) 矩阵宽度
\(h\) 矩阵高度
\(N\) 所有结点构成的集合
\(R(i)\) 第 \(i\) 行的所有结点，
或 结点 \(i\) 所在行的所有结点，
或 结点集 \(i\) 中所有结点所在行的所有结点
\(C(i)\) 第 \(i\) 列的所有结点，
或 结点 \(i\) 所在列的所有结点，
或 结点集 \(i\) 中所有结点所在列的所有结点
\(r(i)\) 结点 \(i\) 的对应行
\(c(i)\) 结点 \(i\) 的对应列

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 并还原删除的结点

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

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

Show / Hide Go to the end

\[ \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} \]

  • 首先我们定义栈 \(A\) 用于存储枚举列的编号，初始时 \(A\) 为空

  • 选取第 \(1\) 行，\(A=\{1\}\)

  • 标记 \(R(1)\), \(C(R(1))\)(第 \(1,4,7\) 列), \(R(C(R(1)))\) (第 \(3,4,5,8\) 列)

    我们将三次标记的部分分别染成暗品红色 , 暗黄色 , 暗青色 , 分三次展示

    \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \m 1&\m 0&\m 0&\m 1&\m 0&\m 0&\m 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} \]

    \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \m 1&\m 0&\m 0&\m 1&\m 0&\m 0&\m 1\\ \y 0&0&1&\y 0&1&1&\y 0\\ \y 0&0&0&\y 1&1&0&\y 1\\ \y 0&1&0&\y 0&0&0&\y 1\\ \y 1&0&0&\y 1&0&0&\y 0\\ \y 0&0&1&\y 0&0&1&\y 0\\ \y 0&1&1&\y 0&1&0&\y 0\\ \y 1&0&0&\y 1&0&1&\y 0\\ \end{bmatrix} \]

    \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \m 1&\m 0&\m 0&\m 1&\m 0&\m 0&\m 1\\ \y 0&0&1&\y 0&1&1&\y 0\\ \y 0&\c 0&\c 0&\y 1&\c 1&\c 0&\y 1\\ \y 0&\c 1&\c 0&\y 0&\c 0&\c 0&\y 1\\ \y 1&\c 0&\c 0&\y 1&\c 0&\c 0&\y 0\\ \y 0&0&1&\y 0&0&1&\y 0\\ \y 0&1&1&\y 0&1&0&\y 0\\ \y 1&\c 0&\c 0&\y 1&\c 0&\c 1&\y 0\\ \end{bmatrix} \]

  • 删去标记的元素

    新矩阵即为

    \[ \begin{bmatrix} 0&1&1&1\\ 0&1&0&1\\ 1&1&1&0\\ \end{bmatrix} \]

  • 选取第 \(1\) 行，其在原矩阵中对应编号为 \(2\), \(A=\{1,2\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \m 0&\m 1&\m 1&\m 1\\ \c 0&\y 1&\y 0&\y 1\\ \c 1&\y 1&\y 1&\y 0\\ \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} & \end{bmatrix} \]

  • 我们得到了空矩阵，但第一次标记的行非全 \(1\), 所以返回上一层，\(A=\{1\}\) \[ \begin{bmatrix} 0&1&1&1\\ 0&1&0&1\\ 1&1&1&0\\ \end{bmatrix} \]

  • 选取第 \(2\) 行，其在原矩阵中对应编号为 \(6\), \(A=\{1,6\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \c 0&\y 1&\c 1&\y 1\\ \m 0&\m 1&\m 0&\m 1\\ \c 1&\y 1&\c 1&\y 0\\ \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} & \end{bmatrix} \]

  • 我们得到了空矩阵，但第一次标记的行非全 \(1\), 所以返回上一层，\(A=\{1\}\) \[ \begin{bmatrix} 0&1&1&1\\ 0&1&0&1\\ 1&1&1&0\\ \end{bmatrix} \]

  • 选取第 \(3\) 行，其在原矩阵中对应编号为 \(7\), \(A=\{1,7\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \y 0&\y 1&\y 1&\c 1\\ \y 0&\y 1&\y 0&\c 1\\ \m 1&\m 1&\m 1&\m 0\\ \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} & \end{bmatrix} \]

  • 我们得到了空矩阵，但第一次标记的行非全 \(1\), 返回上一层，\(A=\{1\}\)

    \[ \begin{bmatrix} 0&1&1&1\\ 0&1&0&1\\ 1&1&1&0\\ \end{bmatrix} \]

  • 我们已经选过所有行但均未找到可行解，返回上一层，\(A=\{\}\) \[ \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} \]

  • 选取第 \(2\) 行，\(A=\{2\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} 1&0&\y 0&1&\y 0&\y 0&1\\ \m 0&\m 0&\m 1&\m 0&\m 1&\m 1&\m 0\\ \c 0&\c 0&\y 0&\c 1&\y 1&\y 0&\c 1\\ 0&1&\y 0&0&\y 0&\y 0&1\\ 1&0&\y 0&1&\y 0&\y 0&0\\ \c 0&\c 0&\y 1&\c 0&\y 0&\y 1&\c 0\\ \c 0&\c 1&\y 1&\c 0&\y 1&\y 0&\c 0\\ \c 1&\c 0&\y 0&\c 1&\y 0&\y 1&\c 0\\ \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} 1&0&1&1\\ 0&1&0&1\\ 1&0&1&0\\ \end{bmatrix} \]

  • 选取第 \(1\) 行，其在原矩阵中对应编号为 \(1\), \(A=\{2,1\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \m 1&\m 0&\m 1&\m 1\\ \y 0&\c 1&\y 0&\y 1\\ \y 1&\c 0&\y 1&\y 0\\ \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} & \end{bmatrix} \]

  • 我们得到了空矩阵，但第一次标记的行非全 \(1\), 返回上一层，\(A=\{2\}\) \[ \begin{bmatrix} 1&0&1&1\\ 0&1&0&1\\ 1&0&1&0\\ \end{bmatrix} \]

  • 选取第 \(2\) 行，其在原矩阵中对应编号为 \(4\), \(A=\{2,4\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \c 1&\y 0&\c 1&\y 1\\ \m 0&\m 1&\m 0&\m 1\\ 1&\y 0&1&\y 0\\ \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} 1&1 \end{bmatrix} \]

  • 选取第 \(1\) 行，其在原矩阵中对应编号为 \(5\), \(A=\{2,4,5\}\)

  • 进行三次标记 \[ \def\m#1{\color{e800e8} #1} \def\y#1{\color{e8e800} #1} \def\c#1{\color{00e8e8} #1} \begin{bmatrix} \m 1&\m 1 \end{bmatrix} \]

  • 删去标记的元素 \[ \begin{bmatrix} & \end{bmatrix} \]

  • 我们得到了空矩阵，且第一次标记的行全为 \(1\), 说明我们找到了可行解，返回 \(A=\{2,4,5\}\), 即 \(\{T_2,T_4,T_5\}\) 是我们要找的解

Go back

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 个指针，也就是

Show code

DLX_nodes.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
struct Node {
  struct Node *up;
  struct Node *down;
  struct Node *left;
  struct Node *right;

  Node(Node * const _up = nullptr,
       Node * const _down = nullptr,
       Node * const _left = nullptr,
       Node * const _right = nullptr)
    : up(_up), down(_down), left(_left), right(_right) {}
};

我们也可以用内存池存储

Show code

DLX_nodes_ms.cppview raw
1
2
3
4
5
6
7
8
9
10
11
const std::size_t MAX_SIZE = 1e5 + 5;
struct Node {
  std::size_t up, down, left, right;

  Node(std::size_t _up = 0,
       std::size_t _down = 0,
       std::size_t _left = 0,
       std::size_t _right = 0)
    : up(_up), down(_down), left(_left), right(_right) {}
} nodes[MAX_SIZE];
std::size_t cnt_node;

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

Show code

DLX_nodes_final.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
struct Node {
  std::size_t up, down, left, right;
  std::size_t row, col;

  Node(std::size_t _up = 0,
       std::size_t _down = 0,
       std::size_t _left = 0,
       std::size_t _right = 0,
       std::size_t _row = 0,
       std::size_t _col = 0)
    : up(_up), down(_down), left(_left), right(_right), row(_row), col(_col) {}
};

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

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

最后代码如下

Show code

DLX_nodes_final2.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const std::size_t MAX_SIZE = 1e5 + 5;
const std::size_t MAX_EDGE = 5e3 + 5;

struct Node {
  std::size_t up, down, left, right;
  std::size_t row, col;

  Node(std::size_t _up = 0,
       std::size_t _down = 0,
       std::size_t _left = 0,
       std::size_t _right = 0,
       std::size_t _row = 0,
       std::size_t _col = 0)
    : up(_up), down(_down), left(_left), right(_right), row(_row), col(_col) {}
} nodes[MAX_SIZE];
std::size_t cnt_node;

std::size_t width, height;
std::size_t cnt_col[MAX_EDGE];

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

    A: 实际上

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

    • head 结点存为 node[0]

    • 第 \(i\) 列的首结点存为 node[i]

  • Q: 常数优化是什么

    A: 见 此节内容

另外

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

    Show code

    DLX_macro.cppview raw
    1
    2
    3
    4
    5
    6
    7
    8
    9
    #define _l(id) node[id].l
    #define _r(id) node[id].r
    #define _u(id) node[id].u
    #define _d(id) node[id].d
    #define _row(id) node[id].row
    #define _col(id) node[id].col
    // 沿某方向遍历一条链
    #define _for(i, start, dir) \
      for (std::size_t i = _##dir(start); i != start; i = _##dir(i))

初始化

分成两步

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

Show code

DLX_init.cppview raw
1
2
3
4
5
6
void init(std::size_t _width, std::size_t _height) {
  width = cnt_node = _width;
  height = _height;
  for (std::size_t i = 1; i <= width; ++i) node[i] = {i - 1, i + 1, i, i, 0, i};
  node[_r(width) = 0] = {width, 1, 0, 0, 0, 0};
}
存入其他结点

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

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

代码实现如下

Show code

DLX_insert_row.cppview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * @param std::size_t  _ln       : i
 * @param std::size_t* _cols     : R(i)中所有结点的列编号
 * @param std::size_t  _len_cols : |R(i)|
 */
void insert_row(std::size_t _ln,
                std::size_t * const _cols,
                std::size_t _len_cols) {
  for (std::size_t i = 1; i <= _len_cols; ++i) {
    node[cnt_node + i] = {cnt_node + i - 1,
                          cnt_node + i + 1,
                          _u(_cols[i]),
                          _cols[i],
                          _ln,
                          _cols[i]};
    _d(_u(_cols[i])) = cnt_node + i;
    _u(_cols[i]) = cnt_node + i;
    ++cnt_col[_cols[i]];
    if (_d(_cols[i]) == _cols[i]) _d(_cols[i]) = cnt_node + i;
  }
  _l(cnt_node + 1) = cnt_node + _len_cols;
  _r(cnt_node + _len_cols) = cnt_node + 1;
  cnt_node += _len_cols;
}

求解

删除

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

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

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

Show code

DLX_remove_col.cppview raw
1
2
3
4
5
6
7
8
9
10
void remove_col(std::size_t _now_col) {
  _r(_l(_now_col)) = _r(_now_col);
  _l(_r(_now_col)) = _l(_now_col);
  _for(i, _now_col, d)
    _for(j, i, r) {
      _u(_d(j)) = _u(j);
      _d(_u(j)) = _d(j);
      --cnt_col[_col(j)];
    }
}

恢复

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

Show code

DLX_resume_col.cppview raw
1
2
3
4
5
6
7
8
void resume_col(std::size_t _now_col) {
  _r(_l(_now_col)) = _l(_r(_now_col)) = _now_col;
  _for(i, _now_col, u)
    _for(j, i, r) {
      _u(_d(j)) = _d(_u(j)) = j;
      ++cnt_col[_col(j)];
    }
}

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

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)\) 删除的顺序和恢复的顺序是相反的，即若你删除行中结点是从左向右删，则恢复时要从右向左恢复 (类比递归和回溯的顺序关系)

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

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

Show / Hide Go to the end

我们不考虑常数优化，每次只选取 node[head].r 删除，则一共会执行 \(13\) 次 remove 操作和 \(6\) 次 resume 操作

  1. remove 1

  2. remove 4 & remove 7

  3. remove 2

  4. remove 3 & remove 5

  5. remove 6

  6. resume 6

  7. resume 5 & resume 3

  8. resume 2

  9. resume 7 & resume 4

  10. remove 4

  11. remove 2

  12. remove 7

  13. remove 3

  14. remove 5 & remove 6

Go back

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

Show code

DLX_dance.cppview raw
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
std::size_t find_min_col() {
  std::size_t res = _r(0);
  _for(i, 0, r)
    if (cnt_col[i] < cnt_col[res]) res = i;
  return res;
}

/**
 * @param std::size_t* _ans : 答案
 * @param std::size_t& _len : 答案长度
 * @return bool : 是否有解
 */
bool dance(std::size_t *_ans, std::size_t &_len) {
  if (_r(0) == 0) return true;
  std::size_t now_r = find_min_col();
  remove_col(now_r);
  _for(i, now_r, d) {
    _ans[++_len] = _row(i);
    _for(j, i, r) remove_col(_col(j));
    if (dance(_ans, _len)) {
      _for(j, i, l) resume_col(_col(j));
      return true;
    }
    --_len;
    _for(j, i, l) resume_col(_col(j));
  }
  resume_col(now_r);
  return false;
}

关于删除和恢复的顺序

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

以下图为例

首先我们先删除

操作 结果
remove 1
remove 3
remove 4

之后我们恢复

方向相反 1 方向相同 2
resume 4
 resume 1
resume 3
 resume 3
resume 1
 resume 4

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

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

时间复杂度

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

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

例题

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

    Show code

    Luogu_P4929view raw
    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
    /*
     * @Author: Tifa
     * @Description: From <https://github.com/Tiphereth-A/CP-archives>
     * !!! ATTENEION: All the context below is licensed under a 
     *  GNU Affero General Public License, Version 3.
     *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
     */
    #include <bits/stdc++.h>
    using namespace std;
    template <typename Val_t = int,
              typename ID_t = int,
              const std::size_t _Edge_len = 500 + 5,
              const std::size_t _Node_size = 7000 + 5>
    class DLX {
    private:
      struct Node {
        ID_t l, r, u, d;
        ID_t row, col;
      } node[_Node_size];
      std::size_t width, height;
      std::size_t cnt_node;
      std::size_t cnt_col[_Edge_len];
    #define __l(id) node[id].l
    #define __r(id) node[id].r
    #define __u(id) node[id].u
    #define __d(id) node[id].d
    #define __row(id) node[id].row
    #define __col(id) node[id].col
    #define _for(i, start, dir) \
      for (std::size_t i = __##dir(start); i != start; i = __##dir(i))
      void remove_col(std::size_t _col) {
        __r(__l(_col)) = __r(_col);
        __l(__r(_col)) = __l(_col);
        _for(i, _col, d)
          _for(j, i, r) {
            __u(__d(j)) = __u(j);
            __d(__u(j)) = __d(j);
            --cnt_col[__col(j)];
          }
      }
      void restore_col(std::size_t _col) {
        __r(__l(_col)) = __l(__r(_col)) = _col;
        _for(i, _col, u)
          _for(j, i, r) {
            __u(__d(j)) = __d(__u(j)) = j;
            ++cnt_col[__col(j)];
          }
      }
      std::size_t find_min_col() {
        std::size_t res = __r(0);
        _for(i, 0, r)
          if (cnt_col[i] < cnt_col[res]) res = i;
        return res;
      }
      bool dance(ID_t *_ans, std::size_t &_len) {
        if (__r(0) == 0) return true;
        std::size_t now_r = find_min_col();
        remove_col(now_r);
        _for(i, now_r, d) {
          _ans[++_len] = __row(i);
          _for(j, i, r) remove_col(__col(j));
          if (dance(_ans, _len)) return true;
          --_len;
          _for(j, i, l) restore_col(__col(j));
        }
        restore_col(now_r);
        return false;
      }

    public:
      void clear() {
        memset(node, 0, sizeof(node));
        memset(cnt_col, 0, sizeof(cnt_col));
        width = height = cnt_node = 0;
      }
      void init(std::size_t _width, std::size_t _height) {
        width = cnt_node = _width;
        height = _height;
        for (std::size_t i = 1; i <= width; ++i)
          node[i] = {i - 1, i + 1, i, i, 0, i};
        node[__r(width) = 0] = {width, 1, 0, 0, 0, 0};
      }
      void insert_row(std::size_t _ln, ID_t *_cols, std::size_t _len_cols) {
        for (std::size_t i = 1; i <= _len_cols; ++i) {
          node[cnt_node + i] = {cnt_node + i - 1,
                                cnt_node + i + 1,
                                __u(_cols[i]),
                                _cols[i],
                                _ln,
                                _cols[i]};
          __d(__u(_cols[i])) = cnt_node + i;
          __u(_cols[i]) = cnt_node + i;
          ++cnt_col[_cols[i]];
          if (__d(_cols[i]) == _cols[i]) __d(_cols[i]) = cnt_node + i;
        }
        __l(cnt_node + 1) = cnt_node + _len_cols;
        __r(cnt_node + _len_cols) = cnt_node + 1;
        cnt_node += _len_cols;
      }
      void insert_map(Val_t **_map,
                      std::size_t _width,
                      std::size_t _height,
                      std::size_t _height_phy = _Edge_len) {
        ID_t *_ = (ID_t *)malloc(sizeof(ID_t) * (_width + 1));
        for (std::size_t _ln = 1, len; _ln <= _height; ++_ln) {
          len = 0;
          for (std::size_t _col = 1; _col <= _width; ++_col)
            if (*((Val_t *)_map + _ln * _height_phy + _col)) _[++len] = _col;
          if (len) insert_row(_ln, _, len);
        }
        free(_);
      }
      bool operator()(ID_t *ans, std::size_t &len) {
        len = 0;
        return dance(ans, len);
      }
    #undef __l
    #undef __r
    #undef __u
    #undef __d
    #undef __row
    #undef __col
    #undef _for
    };
    DLX<> a;
    const int N = 505;
    int n, m;
    int maps[N][N];
    int ans[N];
    int main() {
      ios::sync_with_stdio(false);
      cin.tie(0);
      cout.tie(0);
      cin >> n >> m;
      for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) cin >> maps[i][j];
      a.init(m, n);
      a.insert_map((int **)maps, m, n, N);
      std::size_t len_ans = 0;
      if (a((int *)ans, len_ans))
        for (int i = 1; i <= len_ans; ++i) cout << ans[i] << " ";
      else cout << "No Solution!";
      return 0;
    }

  • 洛谷 P1074 靶形数独 -> 题解

  • 洛谷 P4205 [NOI2005] 智慧珠游戏 -> 题解

重复覆盖问题

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

可重复覆盖指 \(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） 相同

Show code

multi_DLX.hppview raw
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
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
/*
 * @Author: Tifa
 * @LastEditTime: 2020-10-25 17:31:27
 * @Description: multi_DLX
 */

#include <bits/stdc++.h>
using namespace std;

template <const std::size_t _Edge_len = 500 + 5,
          const std::size_t _Node_size = 7000 + 5>
class multi_DLX {
private:
  struct Node {
    std::size_t l, r, u, d;
    std::size_t row, col;
  } node[_Node_size + _Edge_len];
  std::size_t width, height;
  std::size_t cnt_node;

  std::size_t cnt_col[_Edge_len];

#define _l(id) node[id].l
#define _r(id) node[id].r
#define _u(id) node[id].u
#define _d(id) node[id].d
#define _row(id) node[id].row
#define _col(id) node[id].col
#define _for(i, start, dir) \
  for (std::size_t i = _##dir(start); i != start; i = _##dir(i))

  void remove_col(std::size_t _now_col) {
    _for(i, _now_col, d) {
      _r(_l(i)) = _r(i);
      _l(_r(i)) = _l(i);
    }
  }

  void resume_col(std::size_t _now_col) {
    _for(i, _now_col, u) _r(_l(i)) = _l(_r(i)) = i;
  }

  std::size_t find_min_col() {
    std::size_t res = _r(0);
    _for(i, 0, r)
      if (cnt_col[i] < cnt_col[res]) res = i;
    return res;
  }

  bool vis[_Edge_len];
  std::size_t H() {
    std::size_t ret = 0;
    memset(vis, 0, sizeof(vis));
    _for(i, 0, r) {
      if (vis[i]) continue;
      ++ret;
      vis[i] = true;
      _for(j, i, d)
        _for(k, j, r) vis[_col(k)] = true;
    }
    return ret;
  }

  bool dance(std::size_t *_ans,
             std::size_t &_ans_len,
             std::size_t max_depth,
             std::size_t now_depth = 1) {
    if (now_depth > max_depth) return false;
    if (_r(0) == 0) return true;
    std::size_t now_col = find_min_col();
    if (now_depth + H() > max_depth) return false;
    _for(i, now_col, d) {
      remove_col(i);
      _ans[++_ans_len] = _row(i);
      _for(j, i, r) remove_col(j);
      if (dance(_ans, _ans_len, max_depth, now_depth + 1)) {
        _for(j, i, l) resume_col(j);
        resume_col(i);
        return true;
      }
      --_ans_len;
      _for(j, i, l) resume_col(j);
      resume_col(i);
    }
    return false;
  }

public:
  void clear() {
    memset(node, 0, sizeof(node));
    memset(cnt_col, 0, sizeof(cnt_col));
    width = height = cnt_node = 0;
  }

  void init(std::size_t _width, std::size_t _height) {
    width = cnt_node = _width;
    height = _height;
    for (std::size_t i = 1; i <= width; ++i)
      node[i] = {i - 1, i + 1, i, i, 0, i};
    node[_r(width) = 0] = {width, 1, 0, 0, 0, 0};
  }

  void insert_row(std::size_t _ln,
                  std::size_t * const _cols,
                  std::size_t _len_cols) {
    for (std::size_t i = 1; i <= _len_cols; ++i) {
      node[cnt_node + i] = {cnt_node + i - 1,
                            cnt_node + i + 1,
                            _u(_cols[i]),
                            _cols[i],
                            _ln,
                            _cols[i]};
      _d(_u(_cols[i])) = cnt_node + i;
      _u(_cols[i]) = cnt_node + i;
      ++cnt_col[_cols[i]];
      if (_d(_cols[i]) == _cols[i]) _d(_cols[i]) = cnt_node + i;
    }
    _l(cnt_node + 1) = cnt_node + _len_cols;
    _r(cnt_node + _len_cols) = cnt_node + 1;
    cnt_node += _len_cols;
  }
  void insert_map(bool ** const _map,
                  std::size_t _width,
                  std::size_t _height,
                  std::size_t _height_phy = _Edge_len) {
    std::size_t *_ = (std::size_t *)malloc(sizeof(std::size_t) * (_width + 1));
    for (std::size_t _ln = 1, len; _ln <= _height; ++_ln) {
      len = 0;
      for (std::size_t _col = 1; _col <= _width; ++_col)
        if (*((bool *)_map + _ln * _height_phy + _col)) _[++len] = _col;
      if (len) insert_row(_ln, _, len);
    }
    free(_);
  }

  std::size_t operator()(std::size_t *ans) {
    std::size_t len = 0, _ = 0;
    std::size_t l = 1, r = height, mid;
    while (l <= r) {
      mid = l + ((std::ptrdiff_t)r - l) / 2;
      _ = 0;
      if (dance(ans, _, mid)) {
        len = _;
        r = _ - 1;
      } else l = mid + 1;
    }
    return len;
  }

#undef _l
#undef _r
#undef _u
#undef _d
#undef _row
#undef _col
#undef _for
};
multi_DLX<> a;

const int N = 505;
int n, m;
bool maps[N][N];
std::size_t ans[N];

void test() {}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n >> m;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= m; ++j) cin >> maps[i][j];
  a.init(m, n);
  a.insert_map((bool **)maps, m, n, N);
  size_t len_ans = 0;
  if ((len_ans = a((std::size_t *)ans)) > 0)
    for (size_t i = 1; i <= len_ans; ++i) cout << ans[i] << " ";
  else cout << "No Solution!";
  return 0;
}

例题

参考资料

  1. 淡紫色的结点是重复恢复的结点，靛蓝色的指针是重复赋值的指针↩︎

  2. 淡紫色的结点是重复恢复一次的结点，浅紫色的结点是重复恢复两次的结点，靛蓝色的指针是重复赋值一次的指针，枣红色的指针是重复赋值两次的指针↩︎