【搜索】DancingLink+Algorithm X
NanoApe
posted @ 2016年5月25日 10:02
in 蒟蒻不撕烤智熵何来
, 1190 阅读
这种东西解决的是精确覆盖问题
将决策看成是行,要求看成是列,然后每次找可能决策最小的列进行扩展
然而这种思路也是暴力搜索的思路,但是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; }