精确覆盖问题(Exact Cover)

  定义:给定一个\(R\times C\)的\(0,1\)矩阵，问是否存在一个行集合，使得集合每一列恰好有一个\(1\)。

  • 穷举法

  每一行都有选与不选两种状态，枚举行的时间复杂度为\(O(2^R)\)，每次选行时需要遍历之前已选行的所有列以检查是否有冲突，检查需要的时间复杂度为\(O(RC)\)，因此总的复杂度为\(O(RC\times 2^R)\)。 

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
int n, m;
int a[N][N], v[N];

void solve() {
int ok = 0;
    for (int state = 1; state < 1 << n; ++state) {
        memset(v, 0, sizeof(v));
        int flag = 1;
        for (int i = 1; i <= n; ++i) if (flag && ((1 << i - 1) & state))
            for (int j = 1; j <= m; ++j) {
                if (a[i][j]) {
                    if (v[j]) { flag = 0; break; }
                    else v[j] = 1;
                }
            }
        for (int i = 1; i <= m; ++i) if (!v[i]) flag = 0;
        if (!flag) continue;
        else {
            ok = 1;
            for (int i = 1; i <= n; ++i)
                if ((1 << i - 1) & state) printf("%d ", i);
            puts("");
        }

    }
    if (!ok) puts("No Solution!");
}

  • 状态压缩

  把每一行看作一个\(C\)位二进制数，问题转化为在\(R\)个\(C\)位二进制数中, 选择数使得 (1)任意两个数的与为0；(2)所有数的或为\(2^C-1\)；令\(tmp\)表示当前所有被选择了的\(C\)位二进制数的或。时间复杂度\(O(R\times 2^R)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int n, m;
int a[N][N], num[N];

void solve() {
    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 = 1; 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!");
}

Dancing Links(Algorithm X)

红色的框代表选中的行，蓝色的框代表删除的列，绿色的框代表删除的行

Dancing Links(2000)

Dancing Links(2018)

  算法大师Donald Knuth提出了“X算法”，Dancing Links翻译成舞蹈链，并不是算法本身，而是一种链式的数据结构，利用十字链表缓存和回溯矩阵，不需要额外开辟空间。

【模板】舞蹈链（DLX）

这里给出我个人的板子 

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
struct DLX {
    int n, m, cnt;
    int l[maxnode], r[maxnode], u[maxnode], d[maxnode], row[maxnode], col[maxnode];
    int h[maxn], s[maxm];
    int ansd, ans[maxn];
    void init(int _n, int _m) {
        n = _n, m = _m;
        for (int i = 0; i <= m; ++i) {
            l[i] = i - 1;
            r[i] = i + 1;
            u[i] = d[i] = i;
        }
        r[m] = 0; l[0] = m;
        memset(h, -1, sizeof(h));
        memset(s, 0, sizeof(s));
        cnt = m + 1;
    }
    void link(int R, int C) {
        s[C]++;
        row[cnt] = R, col[cnt] = C;
        u[cnt] = C;
        d[cnt] = d[C];
        u[d[C]] = cnt;
        d[C] = cnt;
        if (h[R] == -1) h[R] = l[cnt] = r[cnt] = cnt;
        else {
            r[cnt] = h[R];
            l[cnt] = l[h[R]];
            r[l[h[R]]] = cnt;
            l[h[R]] = cnt;
        }
        cnt++; 
    }
    void remove(int C) {
        l[r[C]] = l[C], r[l[C]] = r[C];
        for (int i = d[C]; i != C; i = d[i])
            for (int j = r[i]; j != i; j = r[j]) {
                u[d[j]] = u[j];
                d[u[j]] = d[j];
                s[col[j]]--;
            }
    }
    void resume(int C) {
        for (int i = u[C]; i != C; i = u[i])
            for (int j = l[i]; j != i; j = l[j]) {
                u[d[j]] = j;
                d[u[j]] = j;
                s[col[j]]++;
            }
        l[r[C]] = r[l[C]] = C;
    }
    bool dance(int deep) {
        if (!r[0]) {
            for (int i = 0; i < deep; ++i) str[(ans[i] - 1) / 9] = '1' + (ans[i] - 1) % 9;
            puts(str);
            return 1;
        }
        int c = r[0];
        for (int i = r[0]; i != 0; i = r[i]) if (s[i] < s[c]) c = i;
        remove(c);
        for (int i = d[c]; i != c; i = d[i]) {
            ans[deep] = row[i];
            for (int j = r[i]; j != i; j = r[j]) remove(col[j]);
            if (dance(deep + 1)) return 1;
            for (int j = l[i]; j != i; j = l[j]) resume(col[j]);
        }
        resume(c);
        return 0;
    }	
}dlx;

精确覆盖的应用

  求解实际问题时，应考虑行与列的意义，即行表示决策，列表示状态。

N皇后问题

SPOJ 1771

在一个N×N的棋盘上放置N个皇后(N <= 50)，使得任何两个皇后之间不相互攻击（即同一行、同一列、同一对角线不能有大于1个皇后）。求一种摆放方案。

  每个皇后能放置的位置共有\(N^2\)种，即有\(N^2\)行。列有\(4\)种约束条件：

  1. \([1,N]\)表示棋盘N行的占据情况
  2. \([N+1,2N]\)表示棋盘N列的占据情况
  3. \([2N+1,4N-1]\)表示棋盘2N-1条主对角线的占据情况
  4. \([4N,6N-2]\)表示棋盘2N-1条副对角线的占据情况

故共有\(6N-2\)列。

  对于\((i,j)\)的位置，占据的行为\(i\)；占据的列为\(j\)；主对角线可以通过\(i\)和\(j\)的相对情况来判断，所有\(i-j\)相同的占据的主对角线为\(N+i-j\)；副对角线类似，所有\(i+j\)相同的位置占据的副对角线为\(i+j-1\)；

  然而，N皇后问题不能直接求精确覆盖，这是因为行和列必须完全覆盖到，但是主和副对角线没有要求一定要全部覆盖，所以算法走到N步停止, 每次消除代表着行或者列的那些列的1, 而不是优先考虑对角线。

代码

数独问题

  1. POJ3074 Sudoku
  • \(DFS\)

  现实生活中，我们玩数独的策略是先填能唯一确定的位置，然后从选项少的位置突破。从而有我们的搜索策略：在每个状态下，从所有未填位置里选择能填合法数字最少的位置，考虑该位置填什么数，作为搜索的分支。考虑以下优化：(1)每行、列、宫用一个9位二进制数保存，当一个位置填上数后，将对应行、列、宫变为0更新状态，回溯时改为1；(2)对每个位置，将所在行、列、宫的数进行与运算得到还能填哪些数，并用\(lowbit\)取出；

代码

  • \(DLX\)

  每一个决策可由三元组\((r,c,w)\)表示，这是因为每个宫可由\((r,c)\)确定，故共有\(9*9*9\)行。其次，每个决策有四个影响(1)\((r,c)\)填了一个数字；(2)第\(r\)行用了一个\(w\)；(3)第\(c\)列用了一个\(w\)；(4)第\(a\)宫用了一个\(w\)。共\(9*9*4\)列。

  1. \([1, 81]\)列，分别对应了81个格子是否被放置了数字。
  2. \([82, 2*81]\)列，分别对应了9行，每行[1, 9]个数字的放置情况。
  3. \([2*81+1, 3*81]\)列，分别对应了9列，每列[1, 9]个数字的放置情况。
  4. \([3*81+1, 4*81]\)列，分别对应了9个“宫”，每“宫”[1, 9]个数字的放置情况。

代码

  1. noip2009-靶形数独

  与上题类似，只需添加一个权值数组，并更新答案，此时将bool dance(int deep)中改为void型，否则会返回搜到的第一组解而无法更新答案。

代码

重复覆盖

  定义:给定一个\(R\times C\)的\(0,1\)矩阵，问是否存在一个行集合，使得集合每一列至少有一个\(1\)。

  精确覆盖是重复覆盖的特殊情况，参照精确覆盖的算法构建跳舞链，对行进行枚举，不同的是，我们仅删除该行上有“1”的列，但不再删除列对应的行。为了满足搜索的行数最小，我们引入迭代加深(IDA*)。

  • 迭代加深：枚举一个最大深度，然后对问题进行搜索，搜索过程记录当前深度，如果当前深度大于最大深度则无条件返回。

  • 启发式函数：设计一个估价函数\(f(\ )\)，函数返回的是至少还需要多少行才能完成重复覆盖。实际值 > 估计值\(f(\ )>K\)

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
struct DLX {
    int n, m, cnt;
    int l[mx], r[mx], u[mx], d[mx], row[mx], col[mx];
    int h[maxn], s[maxm];
    int ans;
    void init(int _n, int _m) {
        n = _n, m = _m;
        for (int i = 0; i <= m; ++i) {
            l[i] = i - 1;
            r[i] = i + 1;
            u[i] = d[i] = i;
        }
        l[0] = m, r[m] = 0;
        memset(h, -1, sizeof(h));
        memset(s, 0, sizeof(s));
        cnt = m + 1;
    }
    void link(int R, int C) {
        s[C]++;
        row[cnt] = cnt, col[cnt] = C;
        u[cnt] = C;
        d[cnt] = d[C];
        u[d[C]] = cnt;
        d[C] = cnt;
        if (h[R] == -1) h[R] = l[cnt] = r[cnt] = cnt;
        else {
            l[cnt] = l[h[R]];
            r[cnt] = h[R];
            r[l[h[R]]] = cnt;
            l[h[R]] = cnt;
            
        }
        cnt++;
    }
    void remove(int C) {
        for (int i = d[C]; i != C; i = d[i])
            l[r[i]] = l[i], r[l[i]] = r[i];
    }
    void resume(int C) {
        for (int i = u[C]; i != C; i = u[i])
            l[r[i]] = r[l[i]] = i;
    }
    bool v[maxm];
    int f() {
        int ret = 0;
        for (int c = r[0]; c != 0; c = r[c]) v[c] = 1;
        for (int c = r[0]; c != 0; c = r[c])
            if (v[c]) {
                ret++;
                v[c] = 0;
                for (int i = d[c]; i != c; i = d[i])
                    for (int j = r[i]; j != i; j = r[j])
                        v[col[j]] = 0;
            }
        return ret;
    }
    void dance(int deep) {
        if (deep + f() >= ans) return;
        if (!r[0]) {
            if (deep < ans) ans = deep;
            return;
        }
        int c = r[0];
        for (int i = r[0]; i != 0; i = r[i]) if (s[i] < s[c]) c = i;
        for (int i = d[c]; i != c; i = d[i]) {
            remove(i);
            for (int j = r[i]; j != i; j = r[j]) remove(j);
            dance(deep + 1);
            for (int j = l[i]; j != i; j = l[j]) resume(j);
            resume(i);
        }
    }
}dlx;

重复覆盖的应用

fzu1686-神龙的难题

  每一个1看成列，每个位置作为左上角的矩阵看成行

代码

hdu2295-Radar

  扫描半径越大，雷达覆盖城市越容易，我们可以二分枚举半径R，然后根据这个半径来建立雷达和城市之间的关系矩阵\(A\)。\(A[i][j]=1\)当且仅当第i个雷达到第j个城市的距离小于等于R，问题z转化为看能不能选择K行（每行代表每个雷达）满足每行上的列都至少有一个“1”（每个列代表每个城市）。

代码

参考资料

Donald E. Knuth的原稿