Dylan 收录于 OI

2017-12-27 2023-04-05 约 4000 字预计阅读 8 分钟 - 次阅读 - 条评论

DancingLinksX|精确覆盖&重复覆盖

本文介绍DLX及其在精确覆盖和重复覆盖问题中的应用。

在DLX之前先了解精确覆盖和重复覆盖。

精确覆盖

给出一个仅有0、1的矩阵，选择其中的一些行使得这些行组成的集合中每一列都有且仅有一个1，求方案的存在性及具体方案。

重复覆盖

给出一个仅有0、1的矩阵，选择其中的一些行使得这些行组成的集合中每一列都至少有一个1，求方案的存在性及具体方案。

Algorithm X & DLX

精确覆盖和重复覆盖都是NP完全问题，所以目前解决方法只有搜索。

在精确覆盖和重复覆盖的问题中，如果尝试选择某一行包括至解集中，那么其他的一些行就不能再选择，一些列可以删去。这样就得到了一个更简单的矩阵，于是可以用递归的搜索算法解决。

Algorithm X就是直接通过回溯解决精确覆盖和重复覆盖问题。

解决精确覆盖的伪代码如下：

如果A是空的，问题解决；成功终止。
否则选取一列c，
枚举当前列中的1，位置设为(r,c)
取r尝试作为解集的一部分。
对于r行中每个1对应的列（包括c），它们已经在解集中有1了，
它们可以不用再考虑了；而且每列有且仅有一个1，必须删除它们防止造成冲突。
而在这些列中有1的行会与r冲突，所以还有删除在这些列及c中有1的行。
递归。
回溯。

实际代码中，由于每次都会删除当前列c，所以一般在枚举之前先删除c。

需要指出的是，上面选择列c的操作中，选择哪一列并不会对答案的存在性产生影响，因为只有在所有列都被删除的时候算法才会终止。

重复覆盖：

由于重复覆盖并不要求每列有且仅有一个1，所以要对X算法做一些小改动。

如果A是空的，问题解决；成功终止。
否则选取一列c，
枚举当前列中的1，位置设为(r,c)
取r尝试作为解集的一部分。
对于r行中每个1对应的列（包括c），它们已经在解集中有1了；
所以可以删除它们以简化问题。
递归。
回溯。

但是，在一般的写法中，X算法在运行过程中需要不断地更改并重新生成新的矩阵，耗费了大量时间。这时将要介绍的DancingLinks就发挥用处了，因为它在删除和恢复行列上消耗的时间很少。

DLX，就是用DancingLinks实现的X算法。

优化

考虑到上面选择列时，无论选择哪一列最终都能得出解，那么选择哪一列就是一个值得思考的问题。下面介绍一种推荐的策略：选取元素个数列最少的一个。这种策略基于这样的考虑：在元素少的列枚举行的次数更少。

~~其实我也不知道有没有快~~

DancingLinks

DancingLinks是 Donald E.Knuth（Stanford University）提出的一种数据结构，也可以称为双向循环交叉十字链表（双向循环二维链表）。

普通的链表支持O(1)删除/恢复节点（添加操作暂不提），而类比之DancingLinks可以O(n)删除/恢复行/列。其中n为二维链表的边长。由于在执行这些操作时节点间指针的修改等好像节点手拉手跳舞，DancingLinks的这个别名才流行起来。

那么接下来介绍DancingLinks。

结构

先上图

为了更好地组织节点，一般在数据节点（图中用阿拉伯数字标出的节点）之外定义一些辅助节点，包括：

总头节点（head）：用以判断链表是否为空。当链表为空时，有r[head]=head。

列首节点（col[]）：连接在总头节点的右边，并垂直连接每一列的节点。

通过辅助节点和数据节点，可以访问结构中的所有数据。

每个节点包括四个指针：l,r,u,d。分别指向左右上下四个方向相邻的节点。

注意由于DancingLinks是循环链表，所以最左边的节点的左指针应该指向这一列最右边的节点，其他边缘的节点同理。u[head]和d[head]一般不使用。

有了这样的结构，就可以通过head->col[y]->x的方式访问每一个数据节点。

在结构的基础上，就可以实现一些操作以满足算法的需求了。

下面是代码实现定义，还有一些细节的地方会写在注释里。

有一些上面没有提到的辅助变量或者数组，后面的操作会用得到。

！！！注意！！！ 需要指出的是，代码中的col[i]是第i列的列首节点id，而row[i]是第i行第一个数据节点的id，注意区别！

1
2
3
4
5
6
7
8
struct DancingLinks
{
    int k;//元素的数量
    int l[maxn*maxm],r[maxn*maxm],u[maxn*maxm],d[maxn*maxm];//指针 
    int idx[maxn*maxm],idy[maxn*maxm];//原来的位置 
    int head,col[maxm],row[maxn];//总头指针，列首指针元素（超首），行首元素（不是指针） 
    int size[maxm];//列的元素个数 
} dl;

操作

初始化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
void clear()//初始化
{
    k=0;
    head=0;
    r[head]=1;
    for(int i=1; i<=m; ++i)
    {
        col[i]=++k;
        l[k]=k-1,r[k-1]=k;
        u[k]=d[k]=k;
    }
    r[k]=head,l[head]=k;
    memset(row+1,0,n*sizeof(int));
    memset(size+1,0,m*sizeof(int));
}

不废话。大概就是新建总头结点，列首节点，同时将他们连起来。

注意：如果一个节点在某个方向上没有相邻的节点，则它这个方向的指针要指向自己。

节点

插入

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
inline void insert(int x,int y)//插入位置在(x,y)的数据节点
{
    ++k;
    idx[k]=x,idy[k]=y;//记录下原位置
    if(row[x]==0)//如果这一行还没有节点
        row[x]=k,l[k]=r[k]=k;
    int ll=l[row[x]],uu=u[col[y]];
    /*ll为左边相邻的节点，uu为上面相邻的节点
    由于是循环链表，所以l[row[x]]指向的其实是当前这一行最右边的节点*/
    l[k]=ll,u[k]=uu;
    r[k]=row[x],d[k]=col[y];
    
    l[row[x]]=u[col[y]]=r[ll]=d[uu]=k;
    ++size[y];//将所在列元素个数+1
}

删除/恢复

如果想要真正删除一个点，可以将上下左右的点的指针互相连起来（类似缝补）。但是在DLX里，这样的操作没有多大意义。而且这样删除后这个节点就无法访问到了。为了实现节点的删除后恢复操作，一般只使用左右删除和上下删除。

注意：在删除和恢复时节点本身的指针不需要更改，只需要更改周围节点的指针。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
inline void delr(int x)
{
    int ll=l[x],rr=r[x];
    r[ll]=rr,l[rr]=ll;
}
inline void deud(int x)
{
    int uu=u[x],dd=d[x];
    u[dd]=uu,d[uu]=dd;
    --size[idy[x]];
}
inline void relr(int x)
{
    int ll=l[x],rr=r[x];
    r[ll]=l[rr]=x;
}
inline void reud(int x)
{
    int uu=u[x],dd=d[x];
    u[dd]=d[uu]=x;
    ++size[idy[x]];
}

行&列

删除/恢复

对于一行或列的删除操作，只要选取一个起始点，然后像下面一样操作（以行为例）：

1
2
3
4
5
void deRow(int x)
{
    for(int i=r[x]; i!=x; i=r[i])
        deud(i);
}

但是需要注意的是，这个操作之后节点x并没有被删除。同之前提到的原因一样，这是为了在以后需要的时候能够通过节点x恢复这一行。

1
2
3
4
5
void reRow(int x)
{
    for(int i=r[x]; i!=x; i=r[i])
        reud(i);
}

另外，对于列的删除操作，由于列拥有列首节点，所以在删除时一般选择列首节点作为x。而列首节点可以通过col[y]来访问到，又由于判断表空用的是r[head]=head，所以在删除列的时候需要delr(列首节点)。

应用

一个说明

首先说明一点：一个已经被删除的节点不能在相同方向上再被删除一次。

证明（以左右删除为例）：设x为已删除节点，在第二次删除x时，所执行的操作是：

int ll=l[x],rr=r[x]; r[ll]=rr,l[rr]=ll;

问题的根源在于，由于x已经被删除，l[x]和r[x]存放的是x上一次被删除时它相邻的节点。在第二次删除时，可能相邻的节点已经发生变动，这样再进行“r[ll]=rr,l[rr]=ll;”就可能错误地修改指针使结构混乱。

DLX在精确覆盖中的应用

在精确覆盖中，只要将X算法用DancingLinks实现即可。下面要讲的是一些代码中的细节。

代码如下：

 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
void deCol(int coll)//x为列首指针
{
    delr(coll);
    for(int i=d[coll]; i!=coll; i=d[i])
        for(int j=r[i]; j!=i; j=r[j])
            deud(j);
}
void reCol(int coll)
{
    relr(coll);
    for(int i=d[coll]; i!=coll; i=d[i])
        for(int j=r[i]; j!=i; j=r[j])
            reud(j);
}
void deRow(int x)
{
    for(int i=r[x]; i!=x; i=r[i])
        deCol(col[idy[i]]);
}
void reRow(int x)
{
    for(int i=r[x]; i!=x; i=r[i])
        reCol(col[idy[i]]);
}
bool X()
{
    if(r[head]==head)
        return true;
    int mincol=r[head];
    for(int i=r[head]; i!=head; i=r[i]) //选择一个元素最少的列
    {
        if(size[i]<size[mincol])
            mincol=i;
    }
    deCol(mincol);
    for(int i=d[mincol]; i!=mincol; i=d[i])
    {
        deRow(i);            
        if(X())return true;
        reRow(i);
    }
    reCol(mincol);
    return false;
}

代码中的deCol(c)表示删除c所在的列，同时将在c列中有1的行删除。

而deRow(r)则表示选择并删除r所在行，同时删除r行中所有1对应的列。

注意：DeCol中只需要delr(列首节点)，而不能delr(其他该列的节点)，否则下面删除行的时候无处开始。

实例

数独、N皇后

DLX在重复覆盖中的应用

在精确覆盖中，由于要删除的每一列中有1的行都已经被删除了，所以只要delr(列首节点)也不会造成问题，而且因为要枚举行，所以不能delr(其他节点)。

但是在重复覆盖中，形式发生了一些变化。由于删除列的时候不需要删除对应的行，所以在删除列时如果不delr(节点)，在选取其他行时可能会遍历到这一列，根据前面的说明，会导致这个节点被重复删除而出现问题。

于是改变策略，先枚举后删除。为了防止出现上面的问题，在删除时从当前节点开始枚举，即不删除当前节点。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
void deCol(int x)//x为列中元素
{
    for(int i=d[x]; i!=x; i=d[i])
            delr(i);
}    
void reCol(int x)
{
    for(int i=d[x]; i!=x; i=d[i])
            relr(i);
}
void deRow(int x)
{
    for(int i=r[x]; i!=x; i=r[i])
        deCol(i);
}
void reRow(int x)
{
    for(int i=r[x]; i!=x; i=r[i])
        reCol(i);
}

然而由于重复覆盖在每一次选择后能够减小的问题规模有限，其速度比相同输入规模的精确覆盖慢很多。我们需要一些优化。

剪枝

一次递归至少可以删除一列，所以可以估计还要删除多少列来剪枝。

一个想法是通过精确覆盖+贪心剪枝。

大概如下：

初始化当前每列为未删除。
枚举每一列：
如果标记为未删除：
    cnt++；
    标记该列为删除；
    同时将这一列中每一行对应的列都标记为删除。

cnt就是估计值。

代码：

 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
bool vis[maxm];
int h()//精确覆盖估算剪枝:估价函数，最小添加几行
{
    int cnt=0;
    memset(vis+1,0,n*sizeof(bool));
    for(int i=r[head];i!=head;i=r[i])
    {
        if(!vis[i])
        {
            ++cnt;
            vis[i]=true;
            for(int j=d[i];j!=i;j=d[j])
                for(int o=r[j];o!=j;o=r[o])
                    vis[idy[o]]=true;
        }
    }
    return cnt;
}
int ans;
void X(int dep)
{
    if(r[head]==head)
    {
        if(dep<ans)
            ans=dep;
        return;
    }
    int th=h();
    if(dep+th>=ans)return;
   
    int mincol=r[head];
    for(int i=r[head]; i!=head; i=r[i])
        if(size[i]<size[mincol])
            mincol=i;

    for(int i=d[mincol]; i!=mincol; i=d[i])
    {
        deCol(i),deRow(i);
        X(dep+1);
        reRow(i),reCol(i);
    }
}