Dancing Links算法

Dancing Links略述

 Dancing Links算法主要用于解决精确覆盖问题,精确覆盖问题就的定义:给定一个由0-1组成的矩阵,是否能找到一个行的集合,使得每个集合中每一列恰好只包含一个1。例如下面的矩阵,我们将改矩阵命名为矩阵1

 如何利用给定的矩阵求出相应行的集合呢,采用回溯法。假定选择第一行,如下所示

 如上图所示,红色那一行是选中的行,这一行有3个1,分别是第3,5,6列。由于这三列已经包含了1,所以把这三列往下标,图中懒得部分包含了3个1,这3个1分别在两行中,把这两行用紫色标出来,根据要求,同一列的1只能有一个,故紫色的两行和红色一行相冲突。那么在接下来的求解中,红色部分、蓝色的部分、紫色的部分都不能用了,把这些部分都删除,得到一个新的矩阵

 行分别对应矩阵1中的第2,4,5行,列分别对应1,2,4,7列,于是问题就转化为一个规模更小的精确覆盖问题。我们将该矩阵命名为矩阵2,在矩阵2中选择第一行,如下图所示

 按照之前的步骤,进行标示,然后将红色,蓝色,紫色交叉的部分全部删除,这时发现矩阵空了,而红色的一行有0(有0说明这一列没有1覆盖),说明,第1行选择是错误的。  那么回到之前,选择第2行,如下图所示

 按照之前的步骤把红色,蓝色,紫色部分删除后,得到新的矩阵

 行对应矩阵2中的第3行,矩阵1中的第5行,列对应矩阵2中的第2,4列,矩阵1中的2,7列。由于剩下的矩阵只有1行,且都是1,所以直接选择这一行,问题就解决,于是该问题的解就是矩阵1中的第一行、矩阵2中的第2行、矩阵3中的第1行。也就是矩阵1中的第1、4、5行。  在求解这个问题的过程中,我们第1步选择第1行是正确的,但是不是每个题目第1步选择都是正确的,如果选择第1行无法求解出结果出来,那么就要推倒之前的选择,从选择第2行开始,以此类推。从上面的求解过程来看,实际算法流程如下:

  1. 从矩阵中选择一行
  2. 根据定义,标示矩阵中其他行的元素
  3. 删除相关行和列的元素,得到新矩阵
  4. 如果新矩阵是空矩阵,并且之前的一行都是1,那么求解结束,跳转到6;新矩阵不是空矩阵,继续求解,跳转到1;新矩阵是空矩阵,之前的一行中有0,跳转到5
  5. 说明之前的选择有误,回溯到之前的一个矩阵,跳转到1;如果没有矩阵可以回溯,说明该问题无解,跳转到7
  6. 求解结束,把结果输出
  7. 求解结束,输出无解消息

 从如上的求解流程来看,在求解的过程中有大量的缓存矩阵和回溯矩阵的过程。而如何缓存矩阵以及相关的数据(保证后面的回溯能正确恢复数据),也是一个比较头疼的问题(并不是无法解决)。以及在输出结果的时候,如何输出正确的结果(把每一步的选择转换为初始矩阵相应的行)。

Dancing Links详述

 Dancing Links的核心是基于双向链表的方便操作(移除、恢复加入),我们用例子来说明:假设双向链表的三个连续的元素,A1、A2、A3,每个元素有两个指针Left和Right,分别指向左边和右边的元素。由定义可知A1.Right=A2,A2.Right=A3,A2.Left=A1,A3.Left=A2。现在把A2这个元素从双向链表中移除(不是删除)出去,那么执行下面的操作就可以了A1.Right=A3,A3.Left=A1,如果要将A2恢复,也只需要修改A1的Right指针和A3的Left指针,也就是A1.Right=A2,A3.Left=A2,但是在很多实际应用中,把双向链表的首尾相连,构成循环双向链表。  Dancing Links中的每个元素不仅是横向循环双向链表中的一份子,又是纵向循环双向链表的一份子,因为准确覆盖问题的矩阵往往是稀疏矩阵(矩阵中,0的个数多于1的个数),Dancing Links仅记录矩阵中值是1的元素。  Dacing Link中的每个元素有6个分量,分别是Left(指向左边的元素)、Right(指向右边的元素)、Up(指向上边的元素)、Down(指向下边的元素)、Col(指向列标的元素)、Row(指向行标的元素)  Dancing Links还要准备一些辅助元素

  • Ans:Ans数组,在求解的过程中保留当前的答案,以供最后输出答案用
  • Head元素:求解的辅助元素,在求解过程中,当判断出Head.Right=Head(也可以是Head.Left=Head)时,求解结束,输出答案。Head元素只有两个分量有用。
  • C元素:辅助元素,称为列标元素,每列有一个列标元素。在初始的状态下,Head.Right=C1,C1.Right=C2,....Cn.Right=Head等等。列标元素分量

 下图就是根据题目构建好的交叉十字循环双向链表

 接下来,利用图来解释Dancing Links是如何求解精确覆盖问题。

  1. 首先判断Head.Right==Head?若是,求解结束,输出解;若不是,求解还没结束,到步骤2(也可以判断Head.Left==Head)
  2. 获取Head.Right元素,即元素C1,并标示元素C1(标示元素C1,指的是标示C1、和C1所在列的所有元素、以及该元素所在行的元素,并从双向链表中移除这些元素)。如下图中的紫色部分。

 如上图可知,行2和行4中的一个必是答案的一部分(其他行中没有元素能覆盖列C1),先假设选择的是行2.

  1. 选择行2(在答案栈中压入2),标示该行中的其他元素(元素5和元素6)所在的列元素,即标示元素C4元素C7,,下图中的橙色部分。

 把上图中的紫色部分和橙色部分移除,剩下的绿色部分如下图所示:

  1. 获取Head.Right元素,即元素C2,并且标示元素C2,如下图紫色部分

 如图,列C2只有元素7覆盖,故答案只能选行3。

  1. (在答案栈中压入3),标示该行中的其他元素(元素8和元素9)所在的列首元素,即标示元素C3和标示元素C6,下图中的橙色部分。

 把上图中的紫色部分和橙色部分移除的话,剩下的绿色部分就如下图所示:

  1. 获取Head.Right元素,即元素C5,元素C5中的垂直双向链中没有其他元素,也就是没有元素覆盖列C5。说明当前求解失败。要回溯到之前的分叉选择步骤(步骤2)。那要回标列首元素(把列首元素、所在列的元素,以及对应行其余的元素。并恢复这些元素到双向链中),回标列首元素的顺序是标示元素的顺序的反过来。从前文可知,顺序是回标列首C6、回标列首C3、回标列首C2、回标列首C7、回标列首C4。表面上看起来比较复杂,实际上利用递归,是一件很简单的事。并把答案栈恢复到步骤2(清空的状态)的时候。又回到下图所示:
  1. 由于之前选择行2导致无解,因此这次选择行4(再无解就整个问题就无解了)。选择行4(在答案栈中压入4),标示该行中的其他元素(元素11)所在的列首元素,即标示元素C4,下图中的橙色部分。

 把上图中的紫色部分和橙色部分移除的话,剩下的绿色部分就如下图所示:

  1. 获取Head.Right元素,即元素C2,并标示元素C2。如下图中的紫色部分。

 如图,行3和行5都可以选择

  1. 选择行3(在答案栈中压入3),标示该行中的其他元素(元素8和元素9)所在的列首元素,即标示元素C3和标示元素C6,下图中的橙色部分。

 把上图中的紫色部分和橙色部分移除的话,剩下的绿色部分就如下图所示:

  1. 获取Head.Right元素,即元素C5,元素C5中的垂直双向链中没有其他元素,也就是没有元素覆盖列C5。说明当前求解失败。要回溯到之前的分叉选择步骤(步骤8)。从前文可知,回标列首C6、回标列首C3。并把答案栈恢复到步骤8(答案栈中只有4)的时候。又回到下图所示:
  1. 由于之前选择行3导致无解,因此这次选择行5(在答案栈中压入5),标示该行中的其他元素(元素13)所在的列首元素,即标示元素C7,下图中的橙色部分。

 把上图中的紫色部分和橙色部分移除的话,剩下的绿色部分就如下图所示:

  1. 获取Head.Right元素,即元素C3,并标示元素C3。如下图中的紫色部分。
  1. 如上图,列C3只有元素1覆盖,故答案只能选择行3(在答案栈压入1)。标示该行中的其他元素(元素2和元素3)所在的列首元素,即标示元素C5和标示元素C6,下图中的橙色部分。

 把上图中的紫色部分和橙色部分移除的话,剩下的绿色部分就如下图所示:

  1. 因为Head.Right=Head。故,整个过程求解结束。输出答案,答案栈中的答案分别是4、5、1。表示该问题的解是第4、5、1行覆盖所有的列。如下图所示(蓝色的部分):

 从以上的14步来看,可以把Dancing Links的求解过程表述如下:

  1. Dancing函数的入口
  2. 判断Head.Right=Head?,若是,输出答案,返回True,退出函数。
  3. 获得Head.Right的元素C
  4. 标示元素C
  5. 获得元素C所在列的一个元素
  6. 标示该元素同行的其余元素所在的列首元素
  7. 获得一个简化的问题,递归调用Daning函数,若返回的True,则返回True,退出函数。
  8. 若返回的是False,则回标该元素同行的其余元素所在的列首元素,回标的顺序和之前标示的顺序相反
  9. 获得元素C所在列的下一个元素,若有,跳转到步骤6
  10. 若没有,回标元素C,返回False,退出函数。

Dancing Links模板

#include<cstdio>
#include<iostream>
#include<cstring>
#define maxnode 1001010
#define maxn    1010
using namespace std;
struct DLX {
    int n,m; 
     int U[maxnode],D[maxnode],L[maxnode],R[maxnode],col[maxnode],row[maxnode];
     int H[maxn];
     int ansed,ans[maxn],size;
     void init(int n,int m) {
         this->n = n;
        this->m = m;
        for(int i = 0;i <= m;i++) {
            U[i] = i;
            D[i] = i;
            L[i] = i - 1;
            R[i] = i + 1;
            col[i] = i;
            row[i] = 0;
        }
        L[0] = m;
        R[m] = 0;
        size = m;
        memset(H,-1,sizeof(H));
        memset(ans,0,sizeof(ans));
        ansed = 0;
        return;
    }
    void push(int r,int c) {
        size++;
        D[size] = D[c];
        U[size] = c;
        U[D[c]] = size;
        D[c] = size;
        row[size] = r;
        col[size] = c;
        if(H[r]<0) {
            H[r] = size;
            R[size] = L[size] = size;
        } else {
            L[size] = H[r];
            R[size] = R[H[r]];
            L[R[H[r]]] = size;
            R[H[r]] = size;
        }
    }
    void del(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]) {
                D[U[j]] = D[j];
                U[D[j]] = U[j];
            }
        return;
    }
    void reback(int c) {
        for(int i = U[c];i != c;i = U[i])
            for(int j = L[i];j != i;j = L[j]) {
                D[U[j]] = j;
                U[D[j]] = j;
            } 
        R[L[c]] = c;
        L[R[c]] = c;
        return ;
    }
    bool dancing(int dep) {
        if(R[0] == 0) {
            ansed = dep;
            return true;
        }
        int c = R[0];
        del(c);
        for(int i = D[c];i != c;i = D[i]) {
            ans[dep] = row[i];
            for(int j = R[i];j != i;j = R[j])
                del(col[j]);
             if(dancing(dep + 1))
                return true;
             for(int j = L[i];j != i;j = L[j])
                 reback(col[j]);
        }
        return false;
    }
}dlx;

int main() {
    int n,m,p,k;
    while(scanf("%d%d",&n,&m) == 2) {
        dlx.init(n,m);
        for(int i = 1;i <= n;i++) {
            scanf("%d",&p);
            for(int j = 1;j <= p;j++) {
                scanf("%d",&k);
                dlx.push(i,k);
            }    
        }
        if(!dlx.dancing(0))
            printf("NO\n");
        else {
            printf("%d",dlx.ansed);
            for(int i = 0;i < dlx.ansed;i++)
                printf(" %d",dlx.ans[i]);
            printf("\n");
        }
    }
    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏chenjx85的技术专栏

leetcode-476-Number Complement

1755
来自专栏進无尽的文章

基础篇- iOS开发中常用的数学函数

1692
来自专栏木子昭的博客

机器学习三剑客之NumpyNumpy计算(重要)

NumPy是Python语言的一个扩充程序库。支持高级大量的维度数组与矩阵运算,此外也针对数组运算提供大量的数学函数库。Numpy内部解除了Python的PI...

3696
来自专栏计算机视觉与深度学习基础

POJ2253 && ZOJ1942

两种写法 用floyd算法,求所有点之间的最大跳的最小值,最后输出a[0][1],即起始与终止位置的最小值,采用传递闭包的思路,时间复杂度较高,但代码简单。 或...

2099
来自专栏mathor

matlab—回归与内插(完结)

5564
来自专栏iOSDevLog

day1-numpy练习

这是在numpy邮件列表,stackoverflow和numpy文档中收集的练习集合。 该系列的目标是为新老用户提供快速参考,同时为教学人员提供一系列练习。

3211
来自专栏小狼的世界

利用JS实现的根据经纬度计算地球上两点之间的距离

第一种是默认地球是一个光滑的球面,然后计算任意两点间的距离,这个距离叫做大圆距离(The Great Circle Distance)。

1332
来自专栏Jack-Cui

Day7、Python

题目打印出如下图案(菱形) ? 1、程序分析     先把图形分成两部分来看待,前四行一个规律,后三行一个规律,利用双重for循环,第一层控制行...

2130
来自专栏王肖的UT

GLSL-内置函数

5313
来自专栏数据结构与算法

P2216 [HAOI2007]理想的正方形(二维RMQ)

题目描述 有一个a*b的整数组成的矩阵,现请你从中找出一个n*n的正方形区域,使得该区域所有数中的最大值和最小值的差最小。 输入输出格式 输入格式: 第一行为3...

2916

扫码关注云+社区

领取腾讯云代金券