高级暴力算法

发表于 | 分类于 | 阅读次数:
搜索是算法学习中最基础的，但是搜索也有很多高级应用，本文简单介绍了一些搜索算法在 OI 中的应用。

###概念

精确覆盖问题 Exact Cover Problem

在一个全集 $X$ 中若干子集的集合为 $S$ ，精确覆盖是指，$S$ 的子集 $S$ ，满足 $X$ 中的每一个元素在 $S$ 中恰好出现一次。在计算机科学中，精确覆盖问题指找出这样的一种覆盖，或证明其不存在。

算法X Algorithm X

可用于解决精确覆盖问题的一种算法，我们每次选择一个没有被覆盖的元素，然后选择一个包含它的集合进行覆盖。不断回溯，知道所有元素被覆盖。

这里我们可以把每个元素当做一列，每个集合当做一行，也就是每次在矩阵中选择一个没有被删除的列，然后枚举删除该列为一的哪一行，不断回溯，直到矩阵变成一个全零矩阵。

但是如果暴力回溯的话时间复杂度不够优秀，所以可以使用 Dancing Links 优化，所谓 Dancing Links 就是一个循环十字链表，那么这种用 Dancing Links 优化的算法 X 就简称为 $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
71
72
73
74
75
76
77
78
class DLX
{
	int n,sz;
	int ncnt[MAXC];
	int row[MAXNODE],col[MAXNODE];
	int L[MAXNODE],R[MAXNODE],U[MAXNODE],D[MAXNODE];
	int ans[MAXR],acnt;
	void rm(int c)//remove
	{
		L[R[c]]=L[c];
		R[L[c]]=R[c];
		int i,j;
		for(i=D[c];i!=c;i=D[i])
			for(j=R[i];j!=i;j=R[j])
				U[D[j]]=U[j],D[U[j]]=D[j],ncnt[col[j]]--;
	}

	void rstr(int c)//restore
	{
		int i,j;
		for(i=U[c];i!=c;i=U[i])
			for(j=L[i];j!=i;j=L[j])
				U[D[j]]=j,D[U[j]]=j,ncnt[col[j]]++;
		L[R[c]]=c;
		R[L[c]]=c;
	}

	bool dfs(int lv)
	{
		if(!R[0])
		{acnt=lv;return true;}
		int i,j;
		int c=R[0];
		for(i=R[0];i;i=R[i])
			if(ncnt[i]<ncnt[c]) c=i;
		rm(c);
		for(i=D[c];i!=c;i=D[i])
		{
			ans[lv]=row[i];
			for(j=R[i];j!=i;j=R[j]) rm(col[j]);
			if(dfs(lv+1)) return true;
			for(j=L[i];j!=i;j=L[j]) rstr(col[j]);
		}
		rstr(c);
		return false;
	}
public:
	DLX(int n=0):n(n)
	{
		for(int i=0;i<=n;i++)
			U[i]=D[i]=i,L[i]=i-1,R[i]=i+1;
		R[n]=0,L[0]=n;
		sz=n+1;
		memset(ncnt,0,sizeof(ncnt));
	}

	void addRow(int r,std::vector<int> cv)
	{
		int fir=sz;
		for(int i=0;i<cv.size();i++)
		{
			int c=cv[i];
			L[sz]=sz-1,R[sz]=sz+1,D[sz]=c,U[sz]=U[c];
			D[U[c]]=sz;U[c]=sz;
			row[sz]=r,col[sz]=c;
			ncnt[c]++,sz++;
		}
		R[sz-1]=fir,L[fir]=sz-1;
	}

	bool solve(std::vector<int> &v)
	{
		v.clear();
		if(!dfs(0)) return false;
		for(int i=0;i<acnt;i++) v.push_back(ans[i]);
		return true;
	}
};

应用：解决数独问题

我们有了 DLX 算法之后，就可以将数独问题转化为精确覆盖问题然后快速解决了，事实上， DLX 在解决数独问题上的表现十分出色。

虽然标准数独是 $9\times9$ 的，但是对计算机来说范围太小了，所有我们以 $16\times16$ 的数独为例：

  • 列代表这需要满足的条件，分析一下数独的游戏规则有如下四种条件：

    • SLOT a b : 第 $a$ 行第 $b$ 列要有字母;
    • ROW a b : 第 $a$ 行要有字母 $b$ ;
    • COL a b : 第 $a$ 列要有字母 $b$ ;
    • SUB a b : 第 $a$ 个子方阵要有字母 $b$ ;

    共有 $16\times16\times4=1024$ 列

  • 行代表着待选的集合，需要注意的是，这里的集合中只有一个元素（这里的元素也就是需要满足的条件），表示的是对于一个格子的状态，也就是某一个格子填什么。

    共有 $16\times16\times16=4096$ 行

  • 由于每行满足四个条件，故每行有 $4$ 个 $1$ ，加起来就是 $4096\times4=16384$ 个节点，用十字链表储存占有空间很小。

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
#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>

const int MAXC=1300,MAXR=4100,MAXNODE=17000;

class DLX
{
	int n,sz;
	int ncnt[MAXC];
	int row[MAXNODE],col[MAXNODE];
	int L[MAXNODE],R[MAXNODE],U[MAXNODE],D[MAXNODE];
	int ans[MAXR],acnt;
	void rm(int c)
	{
		L[R[c]]=L[c];
		R[L[c]]=R[c];
		int i,j;
		for(i=D[c];i!=c;i=D[i])
			for(j=R[i];j!=i;j=R[j])
				U[D[j]]=U[j],D[U[j]]=D[j],ncnt[col[j]]--;
	}

	void rstr(int c)
	{
		int i,j;
		for(i=U[c];i!=c;i=U[i])
			for(j=L[i];j!=i;j=L[j])
				U[D[j]]=j,D[U[j]]=j,ncnt[col[j]]++;
		L[R[c]]=c;
		R[L[c]]=c;
	}

	bool dfs(int lv)
	{
		if(!R[0])
		{acnt=lv;return true;}
		int i,j;
		int c=R[0];
		for(i=R[0];i;i=R[i])
			if(ncnt[i]<ncnt[c]) c=i;
		rm(c);
		for(i=D[c];i!=c;i=D[i])
		{
			ans[lv]=row[i];
			for(j=R[i];j!=i;j=R[j]) rm(col[j]);
			if(dfs(lv+1)) return true;
			for(j=L[i];j!=i;j=L[j]) rstr(col[j]);
		}
		rstr(c);
		return false;
	}
public:
	DLX(int n=0):n(n)
	{
		for(int i=0;i<=n;i++)
			U[i]=D[i]=i,L[i]=i-1,R[i]=i+1;
		R[n]=0,L[0]=n;
		sz=n+1;
		memset(ncnt,0,sizeof(ncnt));
	}

	void addRow(int r,std::vector<int> cv)
	{
		int fir=sz;
		for(int i=0;i<cv.size();i++)
		{
			int c=cv[i];
			L[sz]=sz-1,R[sz]=sz+1,D[sz]=c,U[sz]=U[c];
			D[U[c]]=sz;U[c]=sz;
			row[sz]=r,col[sz]=c;
			ncnt[c]++,sz++;
		}
		R[sz-1]=fir,L[fir]=sz-1;
	}

	bool solve(std::vector<int> &v)
	{
		v.clear();
		if(!dfs(0)) return false;
		for(int i=0;i<acnt;i++) v.push_back(ans[i]);
		return true;
	}
};

DLX solver(1024);

const int SLOT=0,ROW=1,COL=2,SUB=3;

int encode(int a,int b,int c){return a*256+b*16+c+1;}

void decode(int code,int &a,int &b,int &c)
{code--;c=code%16;code/=16;b=code%16;code/=16;a=code;}

char mp[16][20];
bool read()
{
	for(int i=0;i<16;i++)
		if(scanf("%s",mp[i])!=1)
			return false;
	return true;
}

int main()
{
	bool isFir=true;
	while(read())
	{
		int i;
		if(isFir) isFir=false;
		else putchar('\n');
		solver=DLX(1024);
		for(int r=0;r<16;r++)
			for(int c=0;c<16;c++)
				for(int v=0;v<16;v++)
					if(mp[r][c]=='-'||mp[r][c]=='A'+v)
					{
						std::vector<int> cv;
						cv.push_back(encode(SLOT,r,c));
						cv.push_back(encode(COL,r,v));
						cv.push_back(encode(ROW,c,v));
						cv.push_back(encode(SUB,(r/4)*4+c/4,v));
						solver.addRow(encode(r,c,v),cv);
					}
		static std::vector<int> ans;
		solver.solve(ans);
		for(i=0;i<ans.size();i++)
		{
			int r,c,v;
			decode(ans[i],r,c,v);
			mp[r][c]='A'+v;
		}
		for(i=0;i<16;i++) printf("%s\n",mp[i]);
	}
}