浅谈神仙算法——DLX

看完题目之后，你产生的第一个疑问一定是DLX是什么。 ~~除非您是吊打集训队的dalao那还来看我这篇烂文干什么赶紧切题去吧~~ 为了引入，我们先来看一道题。 已知目前有$r$个集合，请选出其中的一些集合使它们的并集为$1,2,3,...,n$，并且你要让这些选出的集合的交集为空集。 这种问题有一个名字，叫做精确覆盖问题（Exact Cover Problem） 那么我们先来想想这题该怎么做吧。 我们先用一个$r$行$n$列的矩阵来表示一个精确覆盖问题 第$i$行第$j$个元素代表第$i$个集合是否存在元素$j$ 例如对于数据$n=7,r=6$ $S_1$ = {1,4,7} $S_2$ = {1,4} $S_3$ = {4,5,7} $S_4$ = {3,5,6} $S_5$ = {2,3,6,7} $S_6$ = {2,7} 它所对应一个6行7列的矩阵 ``` 6 7 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 0 0 1 1 0 0 1 1 0 1 0 0 0 0 1 ``` 我们考虑采用回溯法解决这个问题。 每一次选择一个没有被覆盖的元素，也就是一列。然后选择包含着个元素的集合进行覆盖，也就是一行。那么在矩阵中，我们每选择一个没有被删除的，接着看一下这一列中还有哪些行是1，尝试删除该行，回溯时恢复改行。当然，如果我们选了一行，那么就把这一行其它的1所在的列也应当删除。恢复同理。 这种思路又被称为算法X（Algorithm X），可惜的是删除与恢复序列并不是一个简单的操作，这个时候就应当召唤出数据结构来帮我们优化啦。那么这个数据结构支持什么呢？它应当支持删除和恢复一列。所以我们就要把目光转向著名的程序设计大师Knuth所发明的一种数据结构——舞蹈链（Dancing Links） 舞蹈链（Dancing Links）是什么？我们可以简单的将它理解为一个**双向循环交叉链表**（请大家牢记这个定义） 使用舞蹈链的算法X又被称为DLX （不会链表的同学可以自行百度哦） 把上面那句话对应到程序中是怎么样的呢，首先处理**双向** 对于每一个节点，我们都给它两个指针L与R。分别表示这个节点的左边节点编号和右边节点编号。 接着处理**交叉** 什么叫交叉？横纵即为交叉。横的链表我们已经设计了。那么考虑下纵链表，再给每个节点两个指针U与D。分别表示这个节点上方节点编号与下方节点编号。 最后处理**循环** 我们让最右边的所有节点的R指向最左边的节点，最左边节点的L指向最右边的节点，上下也是如此。 那矩阵如何对应到舞蹈链里呢？ _我们把矩阵的每一个1节点对应到舞蹈链的一个节点_ 那么问题来了，如何删除一列呢？ 我们可以在每个纵链表的顶端添加一个节点——**虚拟节点** 该节点的U指向其所在列的最后一个节点，D指向其所在列的第一个节点。L与R分别指向旁边两列的虚拟节点。 那么删除一列只需要将该列虚拟节点左边的节点的R指向该列虚拟节点右边的虚拟节点，将该列所对虚拟节点的右边虚拟节点的L指向该列所对虚拟节点的左边的虚拟节点。（好好理解下） 问题是删完了吗？没有，这一列里还有节点跟其他节点连着呢。 所以我们应当将该列所有节点找到，然后再把这列所有节点所在的所有行的其它节点的上下节点互指。这样就删完一列了。 那么恢复一列不就是逆操作嘛？ 所以一个Dancing Links大概就是这样的。 什么？有点晕？不如上上代码看看？不懂的地方可以看一下注释哦。 ```cpp //顺着链表a，遍历除s以外的所有元素 #define FOR(i,a,s) for(int i = a[s]; i != s ; i = a[i]) struct DLX { int n,sz; int head; int l[maxnode],r[maxnode],u[maxnode],d[maxnode]; int s[MAXN];//s[i]代表第i列节点的个数 int col[maxnode],row[maxnode]; //row[i] 代表节点i在第几行，col[i]代表节点i在第几列 int ans[MAXN];//答案栈 int ansd; void init() { head = 0; for(int i=0;i<=m;i++)//有m列,处理m个虚拟节点 //从0开始是因为还有一个head节点 { u[i] = i; d[i] = i; l[i] = i - 1; r[i] = i + 1; //这里没必要维护row与col因为维护了也没卵用 } r[m] = head; l[head] = m; //链表循环 sz = m + 1; memset(s,0,sizeof(s)); } void addRow(int R,vector <int> columns)//添加第r行,cloumns[i]代表第r行存在哪些数 //例如colums = {1,2,9}，代表01矩阵中第r行第2个是1，如此类推 { int first = sz; for(int i=0;i<columns.size();i++) { int c = columns[i]; //维护当前节点 l[sz] = sz - 1; r[sz] = sz + 1; //当前节点的左边是上一节点，右边是下一节点 d[sz] = c; u[sz] = u[c]; //由于c是当前列的编号，也就是该列虚拟节点的编号，那么u[c]其实是目前节点上方的节点编号 //为了使链表循环，每一个链表的最后一个节点的下方应当指向head节点,head节点的上方应当指向下方节点 d[u[c]] = sz; //上一个节点的下方此时不应当是head了而应当是当前节点 u[c] = sz; //重新使链表循环 col[sz] = c; row[sz] = R; //维护col和row ++s[c]; ++sz; } r[sz-1] = first ;l[first] = sz - 1; //使链表循环 } void remove(int c)//删除第c列 { r[l[c]] = r[c]; l[r[c]] = l[c]; //先删虚拟节点 FOR(i,d,c)//遍历第c列的down列表 FOR(j,r,i)//遍历第c列每个节点 {d[u[j]] = d[j] , u[d[j]] = u[j] , --s[col[j]] ;}//删除上述遍历的所有节点 } void restore(int c)//恢复 = 删除逆操作，不解释 { FOR(i,u,c) FOR(j,l,i) {++s[col[j]] , d[u[j]] = j,u[d[j]] = j;} r[l[c]] = c; l[r[c]] = c; } //前方高能！！！！！！！！！ 该算法最美丽的地方！ bool dance(int step)//step为递归深度 { if(r[head] == head)//找到解 { ansd = step; return true; } int c = r[head];//第一个没被删除的列 FOR(i,r,head) if(s[i] < s[c]) c = i; //贪心找节点最少的一列，这样可以让枚举情况最少 remove(c);//删除 FOR(i,d,c)//c列表下的每一个节点 { //目前选取第row[i]行来覆盖 //那么就应当把第row[i]行所覆盖的其他列也给删除 ans[step] = row[i]; FOR(j,r,i) remove(col[j]); if(dance(step + 1)) return true;//如果找到解了，直接返回 //要不然还要恢复并且尝试下一个i FOR(j,l,i) restore(col[j]); } restore(c); //恢复 return false; } void print()//输出解 { for(int i = 0;i<ansd;i++) cout<<ans[i]<<' '; } }; ``` 有没有看到一个舞者在你的链表上跳舞呢？主部分又被称作dance。 你认为舞蹈链就这么点用处？那可就大错特错了！ 你听说过八皇后问题吗？你听说过数独问题吗？ 没错DLX算法还是一种用来处理数独的方法！ 它是目前跑的最快的处理数独的算法！ 怎么用它来处理数独呢？那么我们就要把数独问题转换成精确覆盖问题了。 这也谈到了一个精确覆盖问题的建模。不过也非常简单，每列代表一个限制条件，每行代表一种方案，若方案i满足限制j，则矩阵mat[i][j]=1，因此矩阵的构造既要满足所有限制条件，又不能漏掉可能的方案。 对于数独，我们先看限制 ``` 每行中每个数只能出现一遍，ROW(x,v)表示第x行有数字v。 每列中每个数只能出现一遍，COL(x,v)表示第x列有数字v。 每宫中每个数只能出现一遍，BLOCK(i,v)表示编号为i的九宫格块内有数字v 每格中只能填一个数，EXIST(x,y)表示第x行y列有数字。 ``` 那么应当会有324行 再看决策，定义三元组(r,c,v)代表第r行第c个填v 那么决策(r,c,v)所能满足的限制就是 ``` ROW(r,v) COL(c,v) BLOCK(zu(r,c),v) EXIST(r,c,v) ``` （其中zu(r,c)代表点(r,c)所在的九宫格的编号） 列应当有729列。 那么这样，我们不就把数独转换成了精确覆盖问题了嘛？ ------------ 2018.10.19更新：我发现LG多了一个DLX模板，泥萌可以做做 ~~虽然已经没有人看我这篇烂东西了~~ 作业：LG P1074 P1784 然后自己找题去吧（逃） ------------ 参考文献： [1] 刘汝佳 《算法竞赛入门经典训练指南》 [2] 图片出处 ：hihocoder