浅谈DLX

2018-07-06 13:08:21


DLX又称dancing links X 是一种

解决重复覆盖和精确覆盖的高效算法

精确覆盖的定义:

一个全集S有若干个子集S1,S2,……Sn,选取其中若干个子集,使得这些集合中出现了S中每个元素各一次。

这么说可能有点抽象(我知道我语文不好),举个例子:

全集S={1,2,3,4,5,6,7}, 用子集S1={1,2,3},S2={3,4,5,7},S3={4,5,6,7},S4={1,5,6,7},S5={4,5}精确覆盖,结果显然是选取S1和S3。

主要思想:

把全集中的每个元素对应成一个矩阵中的列,把每个子集对应成一个行 对于矩阵中一点(i,j)若集合Si包含元素j则改点为1,否则为0。

我表达能力确实不行,将就看吧,实在不行就看图吧。(蒟蒻不会绘图软件,只好手敲了)

还是刚才的例子,矩阵表示为:

 S | 1  |2  |3  |4  |5  |6  |7
S1 | 1  |1  |1  |0  |0  |0  |0
S2 | 0  |0  |1  |1  |1  |0  |1
S3 | 0  |0  |0  |1  |1  |1  |1
S4 | 1  |0  |0  |0  |1  |1  |1
S5 | 0  |0  |0  |1  |1  |0  |0

接下来是核心操作: 先选取一个集合(一行),把该行和该行上有点的列和包含这些列的行删除(还是看图吧……),比如说我们选了第1行:

 S | 4  |5  |6  |7
S3 | 1  |1  |1  |1
S5 | 1  |1  |0  |0

为什么是这样呢?首先我们要知道当我们把矩阵删完后就完成了精确覆盖,我们选了第一行所以第一行中的元素对应的列就删完了,而包含了这些元素的行肯定是不能选的,所以我们把它们也删了。

接下来如果我们选择了S3,显然矩阵为空,我们找到了一组解,但若我们选择了S5则矩阵变为:

 S | 6  |7

矩阵未覆盖完但已经无集合可用,覆盖失败,于是要回溯,于是矩阵又为:

 S | 4  |5  |6  |7
S3 | 1  |1  |1  |1
S5 | 1  |1  |0  |0

大致是这样一个过程,具体怎么操作就看代码:

代码实现:

首先要知道我们需要的数组和对应的含义:

int n,m,cnt;//矩阵的长,宽,点的数量
    int l[mx],r[mx],u[mx],d[mx],row[mx],col[mx];//每个点的左,右,上下,行,列信息
    int h[mx];//每行的头结点
    int s[mx];//每列的结点数
    int ans,ansk[mx];//需要ans个子集,分别为ansk[]

dancing links 的原理是十字链表的删除和恢复很方便,利用十字链表来储存我们需要的信息。

  1. 第一步 :建立空的矩阵:

    void init(int _n,int _m) {
        n=_n,m=_m;
        int i;
        for(i=0; i<=m; i++) {
            r[i]=i+1;
            l[i]=i-1;
            u[i]=d[i]=i;
        }
        r[m]=0;//m右边是0
        l[0]=m;//0左边是m
        memset(h,-1,sizeof(h));
        memset(s,0,sizeof(s));
        cnt=m+1;//开始时有m个结点(0结点和各列头结点)
    }//初始化,生成每列的头
  2. 第二步:在r行c列插入点

inline void link(int R,int C) {
        s[C]++;
        row[cnt]=R;
        col[cnt]=C;
        u[cnt]=C;
        d[cnt]=d[C];
        u[d[C]]=cnt;
        d[C]=cnt;//十字链表原理
        if(h[R]<0)h[R]=r[cnt]=l[cnt]=cnt;//该行没有别的点,把第一个加入的点作为该行的行头结点
        else {
            r[cnt]=h[R];
            l[cnt]=l[h[R]];
            r[l[h[R]]]=cnt;
            l[h[R]]=cnt;
        }
        cnt++;
    }
  1. 第三步:删除与恢复:
    inline void remove(int c) {
        r[l[c]]=r[c],l[r[c]]=l[c];
        for(int i=d[c]; i!=c; i=d[i]) {
            for(int j=r[i]; j!=i; j=r[j]) {
                u[d[j]]=u[j];
                d[u[j]]=d[j];
                s[col[j]]--;
            }
        }
    }//删除c列和c列上有点的行
    inline void resume(int c) {
        for(int i=u[c]; i!=c; i=u[i]) {
            for(int j=l[i]; j!=i; j=l[j]) {
                u[d[j]]=j;
                d[u[j]]=j;//十字链表的恢复原理,可以自己画图验证。
                s[col[j]]++;
            }
        }
        r[l[c]]=c;
        l[r[c]]=c;
    }//恢复c列和c列上有点的行,恢复与删除很像
  2. 第四步:核心dance:
    bool dance(int deep) {
        if(r[0]==0) { //矩阵已经删除完
        ans=deep;
        //如果要求输出具体的解,可在此处操作(把ansk转换换回对应的集合信息)
        return 1;//多解问题去掉这行
        }
        int c=r[0];
        for(int i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;//找到点最少的列
        remove(c);
        for(int i=d[c];i!=c;i=d[i]){
            ansk[deep]=row[i];
            for(int j=r[i];j!=i;j=r[j]) remove(col[j]);
            if(dance(deep+1)==1)return 1;
            for(int j=l[i];j!=i;j=l[j]) resume(col[j]);
        }
        resume(c); 
        return 0;
    }

推荐几道精确覆盖的题: 八皇后 靶形数独

注意没有精确覆盖的模版题,要自己转换,把一些条件转换成对应的集合。

没有思路的看看题解八皇后题解中文不好看完别吐) 。靶形数独已经有大佬写的题解了,我就不再献丑了,有需要可以看一下我的代码靶形数独代码

差点忘了,还有重复覆盖。

重复覆盖定义:

顾名思意,与精确覆盖差不多,只是可以有元素重复

主要思想:同上(精确覆盖)

代码实现:

删除和恢复略有不同

inline void del(int c){
    for(int i=d[c];i!=c;i=d[i]){
    l[r[i]]=l[i],r[l[i]]=r[i];  
    }
    }//删除c列 
    inline void res(int c){
        for(int i=u[c];i!=c;i=u[i]){
            l[r[i]]=i,r[l[i]]=i;
        }
    }//恢复c列 

dance 部分多了一个剪枝,因为重复覆盖比精确覆盖慢。

inline int leave(){
        int ans=0;
        bool vis[m];
        register int i,j,k;
        memset(vis,0,sizeof(vis));
        for(i=r[0];i!=0;i=r[i]){
            if(vis[i]==0){
                vis[i]=1;
                ans++;
                for(j=d[i];j!=i;j=d[j]){
                    for(k=r[j];k!=j;k=r[k])
                    vis[col[k]]=1;
                }
            }
        }
        return ans;
    }//最优情况还要多少个集合
    void dance(int deep){
    //注意:这个剪枝只有在多解情况求最优解时下才用
        if(deep+leave()>=out)return;//剪枝 
        if(r[0]==0){
            out=deep;
            return;
        }
        int c=r[0];
        register int i,j;
        for(i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;//找到点最少的列
        for(i=d[c];i!=c;i=d[i]){
            del(i);
            for(j=r[i];j!=i;j=r[j])del(j);
            dance(deep+1);
            for(j=l[i];j!=i;j=l[j])res(j);
            res(i);
        }
        return;
    }//可以看出重复覆盖的效率并不算太高,与深搜差不多,甚至如果深搜剪枝剪得好比dancing links快,谨慎使用

洛谷上没找到重复覆盖的题,推荐一道:神龙的难题。

想做的自己去百度

万分感谢你们忍着看完了这么烂的语文水平写的文章

祝各位NOIP满分

行行好给个赞吧

再附上次模板题的代码:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int mx=250501;//n*m+m<=250500
inline int Read(){
    int x=0;
    char c=getchar();
    while(c>'9'||c<'0')c=getchar();
    while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
    return x;
}
int n,m;
int cnt;
int l[mx],r[mx],u[mx],d[mx],col[mx],row[mx];//每个点的左右上下指针,所在行列 
int h[mx];//每行的头结点 
int s[mx];//每列的节点数 
int ansk[mx];//选了那些集合 
void init(int m){//m个元素 
    for(register int i=0;i<=m;i++){
        r[i]=i+1;
        l[i]=i-1;
        u[i]=d[i]=i;
    }
    r[m]=0;
    l[0]=m;
    memset(h,-1,sizeof(h));
    memset(s,0,sizeof(s));
    cnt=m+1;
}//初始化 
inline void link(int R,int C){//R行C列插入点 
    s[C]++;
    row[cnt]=R;
    col[cnt]=C;
    u[cnt]=C;
    d[cnt]=d[C];
    u[d[C]]=cnt;
    d[C]=cnt;
    if(h[R]==-1)h[R]=r[cnt]=l[cnt]=cnt;//该行没有点,直接加入 
    else{
        r[cnt]=h[R];
        l[cnt]=l[h[R]];
        r[l[h[R]]]=cnt;
        l[h[R]]=cnt;
    }
    cnt++;
    return;
}
inline void remove(int C){//删除涉及C列的集合 
    r[l[C]]=r[C],l[r[C]]=l[C];
    for(int i=d[C];i!=C;i=d[i]){
        for(int j=r[i];j!=i;j=r[j]){
            u[d[j]]=u[j];
            d[u[j]]=d[j];
            s[col[j]]--;
        }
    }
}
inline void resume(int C){//恢复涉及C列的集合 
    for(int i=u[C];i!=C;i=u[i]){
        for(int j=l[i];j!=i;j=l[j]){
            u[d[j]]=j;
            d[u[j]]=j;
            s[col[j]]++;
        }
    }
    r[l[C]]=C;
    l[r[C]]=C;
}
bool dance(int deep){
    if(r[0]==0){
        register int i=0;
        for(i=0;i<deep;i++)printf("%d ",ansk[i]);
        return 1;
    }
    int c=r[0];
    int i,j;
    for(i=r[0];i!=0;i=r[i])if(s[i]<s[c])c=i;
    remove(c);
    for(i=d[c];i!=c;i=d[i]){
        ansk[deep]=row[i];
        for(j=r[i];j!=i;j=r[j])remove(col[j]);
        if(dance(deep+1))return 1;
        for(j=l[i];j!=i;j=l[j])resume(col[j]);
    }
    resume(c);
    return 0;
}
int main(){
//  freopen("cin.txt","r",stdin);
    n=Read(),m=Read();
    register int i,j;
    int f;
    init(m);
    for(i=1;i<=n;i++){
        for(j=1;j<=m;j++){
            f=Read();
            if(f)link(i,j);
        }
    }
    if(!dance(0))printf("No Solution!");
    return 0;
}