学习笔记 - 跳舞链DLX | Lucky_Glass's Blog
0%

学习笔记 - 跳舞链DLX


颠覆了自己对于搜索的认知……


Part1. 引入

有一个 $n\times m$ 的方格图,其中有一些格子上有棋子。你可以选择一些行(整行),使得在选择的部分中,每一列上都恰好有 $1$ 个棋子。输出任意一种解决方案。

$n,m\leq50$,时限:1秒

来源:

对于这种问题,没有特别有效的解决方法,只能暴力搜索(需要回溯)。但是由于 $n$ 较大,我们没有办法暴力判断选择哪些行,也没有特别好的剪枝方法。

但是我们注意到问题只要求任意一种解决方案,只要我们搜索的 更新可选方案(当我们选择一行后,一些之前可能选择的行,现在不能选择,就需要删掉)、回溯 的速度比较快,就能够相对较快地解决这个问题。

其实这个问题就是:精确覆盖问题,解决方法就是 Dancing Links。


Part2. 十字循环链表

既然是 “跳舞”,这里的链就是“十字循环链表”。这种链表的元素有 $4$ 个指针 L[],R[],U[],D[],分别表示左、右、上、下的元素;并且这样的元素是“循环的”。

Part2/1. 建表

链表是建立在方格图上的(既然是循环链表,最左、最右 和 最上、最下 是相邻的,且是双向的):

记方格图有 $n$ 行、$m$ 列。

整个链表有一个表头 head=0,然后我们再用 $m$ 个元素分别表示一列head 与这 $m$ 个元素排成一行,左右相连(第 $m$ 个元素的右边是 head)。记表示第 $i$ 列的元素是 C[i]
对于第 $i$ 列,最上方和最下方的格点与 C[i] 上下相连;同列上下相连,同行的格点左右相连。

这样就构造出了一个十字循环链表。

不难发现如果我们把 Part1 中的“棋子”看作方格图中的格点(也就是上图蓝色的格子),也可以建出一个十字循环矩阵。

Part2/2. 删除元素

有两种删除的方式——左右删除和上下删除。左右删除即 “删除前元素 x 的左右元素在删除后与 x 不相连” ,上下删除则是 “删除前元素 x 的上下元素在删除后与 x 不相连”。

由于是双向链表,我们可以方便地找到一个元素在方格图中上下左右的元素。那么我们可以这样实现删除:

1
2
3
4
5
//x 是要删除的元素
//左右删除
L[R[x]]=L[x];R[L[x]]=R[x];
//上下删除
U[D[x]]=U[x];D[U[x]]=D[x];

注意到这里只是修改了 x 的上下左右元素的指针,而对于 x 本身的指针并没有修改,这样保证了链表能够在删除元素后“撤销删除”。

Part2/3. 撤销删除元素

既然是撤销,就只能按删除的顺序倒序撤销。

比如我们上一步删除了 x ,现在我们要撤销这一次删除。利用删除时并没有修改的 x 的指针,我们还能够找到 x 在删除之前的上下左右的元素。

和删除相似,撤销也包括左右撤销和上下撤销。

1
2
3
4
5
//x 是要撤销删除的元素
//左右撤销
L[R[x]]=R[L[x]]=x;
//上下撤销
U[D[x]]=D[U[x]]=x;

下面进入正题,但是上面不是废话。

首先 Dancing Links ,我理解的话,就是一个链表优化剪枝、回溯的搜索……

我们改变一下思路 —— 不考虑当前要选择哪一行,而是考虑当前要满足哪一列上恰好有一个棋子被选

假设我们选择的列是第 Vc 列,我们选择的方式是从 0(表头)开始枚举同行的元素(因为是循环的,只需要向右就可以了)。然后再启发式搜索一下,也就是选择元素最少的列(这就意味着必须要维护一列的个数)。

1
2
3
4
5
6
int mn=INF,Vc;
for(int i=Er[0];i!=0;i=Er[i])
if(Sc[i]<mn && i<=n*m){ //Sc[i] 是第 i 行的元素个数
mn=Sc[i];
Vc=i;
}

选择了 Vc 后,我们就要删除 Vc 以确保之后不会再选择到 Vc

然后为了满足第 Vc 列上有一个棋子,就要枚举选择第 i 行,满足第 i 行第 Vc 列上有棋子,这个可以通过链表方便的找到(因为链表上的元素除了代表某一列的元素 C[] 以及表头,其他的元素都代表的是一个棋子)。

选择了第 i 行后,如果第 i 行第 j 列有棋子,那么第 j 列也会同时被满足,那么第 j 列也要被删掉。然后再DFS。结束后回溯要倒序撤销删除操作。整个DFS结束时也要撤销删除第 Vc 列。

1
2
3
4
5
6
7
8
9
Remove(Vc);
for(int i=D[Vc];i!=Vc;i=D[i]){ //选择第 i 行,通过链表能快速找到(其实找到的第 Vc 列上的一个棋子)
for(int j=R[i];i!=j;j=R[j])
Remove(col[j]); //col[x] 表示 x 元素所在的列,这个在建表时得到;Remove() 即删除列
DFS();
for(int j=L[i];i!=j;j=L[j]) //注意要逆序
Resume(col[j]); //Resume() 是撤销删除
}
Resume(Vc);

Part3/1. Remove(int Vc)

如果我们要删除第 Vc 列,就表示“第 Vc 列上已经有一个被选中的棋子”,那么我们就不能再在选择 Vc 时选择到该元素 ,也不能再选择第 Vc 列的一个棋子。

根据我们选择 Vc 的方式——从表头开始向右枚举元素。只要我们从表头开始向右枚举不到第 Vc 列就可以了!也就是删除元素 C[Vc](代表第 Vc 列的元素)—— L[R[C[Vc]]]=L[C[Vc]];R[L[C[Vc]]]=C[Vc]

但是不止删除 C[Vc],为了防止之后选择到第 Vc 列的棋子:如果第 i 行第 j 列有棋子,那么第 i 行就不能选,否则第 j 列就有多个棋子了。那么我们要删除第 i 行的所有元素,也可以通过链表迅速找到这些元素。

1
2
3
4
5
6
7
8
9
10
11
void Remove(int Vc){
//只要左右找不到C[Vc]就可以了
L[R[C[Vc]]]=L[C[Vc]];R[L[C[Vc]]]=C[Vc];
for(int i=D[Vc];i!=Vc;i=D[i]) //这样就能找到第Vc列哪些位置有棋子
for(int j=R[i];j!=i;j=R[j]){ //通过棋子i就可以找到同行的所有棋子
//(这里棋子i本身不需要删除,因为在删除第Vc列时已经把它删除了)
//只要上下找不到j就可以了
U[D[j]]=U[j];D[U[j]]=D[j];
Sc[col[j]]--; //时刻维护某一列的棋子个数
}
}

注意到这里并不会更改删除的元素本身的信息,目的是方便接下来的“撤销删除”操作。

Part3/2. Resume(int Vc)

在回溯的时候会用到“撤销删除”,但是只能按删除顺序的倒序撤销。

其实倒过来就可以了……

1
2
3
4
5
6
7
8
void Resume(int Vc){
for(int i=U[Vc];i!=Vc;i=U[i])
for(int j=L[i];j!=i;j=L[j]){
U[D[j]]=D[U[j]]=j; //这个时候之前删除j时,j本身的信息就有用了
Sc[col[j]]++;
}
L[R[C[Vc]]]=R[L[C[Vc]]]=C[Vc];
}

Part3/3. DLX

终于到整个的 跳舞链 部分了

之前都把该写的部分都写了,现在组合起来就可以了—— 不过有一个不一样的地方,为了方便,我们并没有定义 C[i] 是代表第 i 列的元素,而是直接让元素 i 是代表第 i 列的元素(也可以理解为 C[i]=i

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
struct DANCINGLINKS{
int El[LM],Er[LM],Eu[LM],Ed[LM],Ec[LM],Sc[LM];
//为了防止重名……带了 'E' 的前缀
//El,Er,Eu,Ed分别是左右上下指针; Ec[x]表示x所在的列; Sc[x]表示第x列的元素个数
int Vcol,ncnt;
//Vcol 表示总的列数
void Build(){
//根据题目不同,这里会不一样
}
void Remove(int Vc){
El[Er[Vc]]=El[Vc];Er[El[Vc]]=Er[Vc];
for(int i=Ed[Vc];i!=Vc;i=Ed[i]){
for(int j=Er[i];j!=i;j=Er[j]){
Ed[Eu[j]]=Ed[j];Eu[Ed[j]]=Eu[j];
Sc[Ec[j]]--;
}
}
}
void Resume(int Vc){
for(int i=Eu[Vc];i!=Vc;i=Eu[i]){
for(int j=El[i];j!=i;j=El[j]){
Eu[Ed[j]]=j;Ed[Eu[j]]=j;
Sc[Ec[j]]++;
}
}
El[Er[Vc]]=Vc;Er[El[Vc]]=Vc;
}
void DFS(int Vk){
if(R[0]==0){
ans++;
return;
}
int mn=(1<<29),Vc=-1;
for(int i=Er[0];i!=0;i=Er[i])
if(Sc[i]<mn && i<=n*m){
mn=Sc[i];
Vc=i;
}
if(Vc==-1) return;
Remove(Vc);
for(int i=Ed[Vc];i!=Vc;i=Ed[i]){
for(int j=Er[i];j!=i;j=Er[j])
Remove(Ec[j]);
DFS(Vk+1);
for(int j=El[i];j!=i;j=El[j])
Resume(Ec[j]);
}
Resume(Vc);
}
}

Part4. 模板题 & 其他题

首先就是一开始的 引入 了。

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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=100,LN=N*N+N+10;

int n,m;
int Cc[N+3][N+3];

struct DANCINGLINKS{
int El[LN],Er[LN],Eu[LN],Ed[LN],Ec[LN],Sc[LN];
int Vh,ncnt;
void Build(){
Vh=0;
for(int i=0;i<=m;i++){
if(i==0) El[i]=m,Er[i]=1;
else if(i==m) El[i]=m-1,Er[i]=0;
else El[i]=i-1,Er[i]=i+1;
Eu[i]=Ed[i]=i;
Sc[i]=0;Ec[i]=i;
}
ncnt=m;
for(int i=1;i<=n;i++){
int Vbg=ncnt+1,Ved=Vbg;
for(int j=1;j<=m;j++){
if(!Cc[i][j]) continue;
int Vu=Eu[j],Vd=j,it=++ncnt;
Eu[it]=Vu;Ed[it]=Vd;
Eu[Vd]=it;Ed[Vu]=it;
El[it]=Ved;Er[it]=Vbg;
Er[El[it]]=it;El[Er[it]]=it;
Ved=it;
Sc[j]++;Ec[it]=j;
}
}
}
void Remove(int Vc){
El[Er[Vc]]=El[Vc];Er[El[Vc]]=Er[Vc];
for(int i=Ed[Vc];i!=Vc;i=Ed[i]){
for(int j=Er[i];j!=i;j=Er[j]){
Ed[Eu[j]]=Ed[j];Eu[Ed[j]]=Eu[j];
Sc[Ec[j]]--;
}
}
}
void Resume(int Vc){
for(int i=Eu[Vc];i!=Vc;i=Eu[i]){
for(int j=El[i];j!=i;j=El[j]){
Eu[Ed[j]]=j;Ed[Eu[j]]=j;
Sc[Ec[j]]++;
}
}
El[Er[Vc]]=Vc;Er[El[Vc]]=Vc;
}
bool DFS(int Vk){
if(Er[Vh]==Vh) return true;
int mn=(1<<29),Vc;
for(int i=Er[Vh];i!=Vh;i=Er[i])
if(Sc[i]<mn){
mn=Sc[i];
Vc=i;
}
Remove(Vc);
for(int i=Ed[Vc];i!=Vc;i=Ed[i]){
for(int j=Er[i];j!=i;j=Er[j])
Remove(Ec[j]);
if(DFS(Vk+1)) return true;
for(int j=El[i];j!=i;j=El[j])
Resume(Ec[j]);
}
Resume(Vc);
return false;
}
}DLX;

int main(){
int cas;scanf("%d",&cas);
while(cas--){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&Cc[i][j]);
DLX.Build();
printf("%s\n",DLX.DFS(1)? "Yes":"No");
}
return 0;
}

Part4/1. n皇后问题

每行、每列都要有恰好 1 个皇后……也就是精确覆盖问题。但是也有一点不一样,就是对于斜线的限制——每条斜线上最多有一个皇后。

那么我们把棋盘的行、列、斜线都作为精确覆盖问题的“列”,每个位置作为“行”。表示斜线的“列”不一定要覆盖完,于是就不能通过判断链表是否为空来判断是否找到答案了,我们发现我们每次会确定一个皇后的位置,如果已经放下了 n 个皇后,就找到答案了。(即搜索深度=n+1)

链接:

Part4/2. 数独

每行、每列、$3\times3$ 的方格内恰好要有一个 $1$ ~ $9$,这就是精确覆盖问题的限制条件。然后就成为一道板子了。


The End

Thanks for reading!

Email: lucky_glass@foxmail.com ,欢迎提问~