NanoApe's Blog

既是咸鱼又是辣鸡

【搜索】DancingLink+Algorithm X

NanoApe posted @ 2016年5月25日 10:02 in 蒟蒻不撕烤智熵何来 , 330 阅读

 

这种东西解决的是精确覆盖问题

将决策看成是行,要求看成是列,然后每次找可能决策最小的列进行扩展

然而这种思路也是暴力搜索的思路,但是DLX快就快在其删除列和恢复列操作上

每个节点都是四向指针,还有行列标号

删除一般都是删除列,然后说是删除,实质上就是把这一列和与这一列有关联的行给提出来单独成块

删除时是什么顺序,恢复时要倒过来操作

 

int sz; //节点个数
int m; //决策数
int U[maxc], D[maxc], L[maxc], R[maxc]; //四方向的指针
int S[maxc]; //当前列的决策数
int col[maxc], row[maxc]; //行列标号

inline void Init() //初始第0行
{
	sz=9*9*4; m=0; 
	rep(i, 0, sz) U[i]=D[i]=i, L[i]=i-1, R[i]=i+1, S[i]=0;
	R[sz]=0, L[0]=sz;
}

int q[4]; //决策满足哪些要求
inline void Add() //添加决策
{
	.....//求出决策满足哪些要求
	m++;
	int fir=sz+1;
	rep(i, 0, 3) sz++, L[sz]=sz-1, R[sz]=sz+1, U[sz]=U[q[i]], D[sz]=q[i], U[D[sz]]=sz, D[U[sz]]=sz, row[sz]=m, col[sz]=q[i], S[q[i]]++;
	L[fir]=sz, R[sz]=fir;
	//新加入决策行
}

#define REP(i,A,x) for(int i=A[x]; i!=x; i=A[i]) //指针循环

inline void remove(int x) //移除某列
{
	S[x]*=-1, S[x]--, L[R[x]]=L[x], R[L[x]]=R[x];
	REP(i,D,x) REP(j,R,i) U[D[j]]=U[j], D[U[j]]=D[j], S[col[j]]--;
}

inline void restore(int x) //恢复某列
{
	REP(i,U,x) REP(j,L,i) S[col[j]]++, U[D[j]]=D[U[j]]=j;
	L[R[x]]=R[L[x]]=x, S[x]++, S[x]*=-1; 
}

bool dfs()
{
	if (!R[0]) return true; //没有要求需要满足了,找到解
	int c=R[0]; REP(i,R,0) if (S[i]<S[c]) c=i; //找可行决策数最小的列
	
	remove(c);
	REP(i,D,c) //枚举可行决策
	{
		.....//加入答案
		REP(j,R,i) remove(col[j]);
		if (dfs()) return true;
		REP(j,L,i) restore(col[j]);
	}
	restore(c);
	
	return false;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter