首页 C++ 算法

[toc] https://oiwiki.com/graph/

# Dancing Links

Dacing Links 主要可以用来解决 精确覆盖问题

# 精确覆盖问题

OI Wiki 上对与精确覆盖问题是这样定义的：精确覆盖问题: (Exact Cover Problem) 是指给定许多集合S_i(1<=i<=N)S\_i(1<=i<=N) 以及一个集合 X, 求满足以下条件的无序多元组 (T_1,T_2,...,T_mT\_1,T\_2,...,T\_m):

  1. \\forall i,j \\in \[1,m\],T\_i\\cap T\_j=\\emptyset (i\\neq j)
  2. X=cup_i=1mT_iX = \\cup\_{i=1}^m T\_i
  3. $\forall i\in [1,m],T_i\in S_1,S_2,…S_n $

问题可以转化为将数字与下标进行对齐的一个矩阵

# 暴力解法 1

枚举所有可能的状态，即，枚举所有可以选择的情况

由于每行都有可选与不可选状态，所以总状态数量为 2^N
枚举状态后，对每个状态进行合理性检查

伪代码如下 ```c++ int ok = 0; for (int state = 0; state < 1 << n; ++state) { // 枚举每行是否被选 for (int i = 1; i <= n; ++i) if ((1 << i - 1) & state) for (int j = 1; j <= m; ++j) a [i][j] = 1; int flag = 1; for (int j = 1; j <= m; ++j) for (int i = 1, bo = 0; i <= n; ++i) if (a [i][j]) { if (bo) flag = 0; else bo = 1; } if (!flag) continue; else { ok = 1; for (int i = 1; i <= n; ++i) if ((1 << i - 1) & state) printf ("% d “, i); puts (”"); } memset (a, 0, sizeof (a)); } if (!ok) puts (“No solution.”);

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
### 暴力解法2

> 考虑到01矩阵的性质,每一行都可以看做一个m位二进制数,问题转化为:  
**给定n个m位二进制数,要求选择一些数,使得任意两个数的与都为0,且所有数的或为$2^m-1$。`tmp`表示的是截至目前被选中的二进制数的或**

1. 同样需要枚举状态
2. 省略了检查的步骤,直接对所有可能性进行与和或即可

```cpp
int ok = 0;
for (int i = 1; i <= n; ++i)
  for (int j = m; j >= 1; --j) num[i] = num[i] << 1  a[i][j];
for (int state = 0; state < 1 << n; ++state) {
  int tmp = 0;
  for (int i = 1; i <= n; ++i)
    if ((1 << i - 1) & state) {
      if (tmp & num[i]) break;
      tmp = num[i];
    }
  if (tmp == (1 << m) - 1) {
    ok = 1;
    for (int i = 1; i <= n; ++i)
      if ((1 << i - 1) & state) printf("%d ", i);
    puts("");
  }
}
if (!ok) puts("No solution.");

# X 算法

X 算法的核心是方便优化，其原理比较简单，即不断地降低遍历区间，这里直接放上 X 算法的截图: B 不难看出这个过程涉及到大量的删除行 / 删除列 / 恢复行 / 恢复列的行为.
基于这个方法产生的问题，Donald E.Knuth 想出了使用双向十字链表来维护这些操作 如上图所示，每一行 / 每一列都有一个指示 具体算法实现如下: https://oiwiki.com/search/dlx/ 有了这个算法后，就可以很好地实现数独问题的求解了