[关闭]
@xzyxzy 2018-07-17T11:39:03.000000Z 字数 4288 阅读 586

舞蹈链(DLX)

搜索

作业部落

评论地址


一、概述

特别特别感谢这位童鞋His blog
舞蹈链是一种优美的搜索,就像下面这样跳舞~
cnblogs不给图片cnblogs不给图片cnblogs不给图片
舞蹈链用于解决精确覆盖或者重复覆盖的问题
你可以想象成贪吃蛇的一个上下左右联通的地图
就是通过链表这样实现的
网上有图的博客

二、实现

更详细的讲解在课件中

精确覆盖

精确覆盖大概指的就是数独和八皇后那样的问题
矩阵中选择一个行的集合,使得每列有且只有一个1
那么就是说每个格子上的点都有若干限制条件(行、列、对角线),每个条件都只允许一个元素
在舞蹈链中(可以把它看作一个表格),每个元素看作一行,限制条件转化为列,选一行删去也同时要删去这一行中所有点所在的列
然后舞蹈链兹瓷快速删除这些东西和快速回溯(复杂度未知)
大概有五个函数
实现的话看代码吧,有详细的注释

Code - [luogu1219]八皇后

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<algorithm>
  4. #include<cstring>
  5. using namespace std;
  6. const int N=100100;
  7. int ans,nn,o;
  8. struct out{int a[14];}Ans[N];
  9. namespace DLX
  10. {
  11. int n,m,cnt;//长宽,点的数量
  12. int l[N],r[N],u[N],d[N];//上下左右的情况
  13. int row[N],col[N];//每个点所处的行列
  14. int h[N],s[N];//头节点和每列节点数
  15. int ansk[20];//答案
  16. void init(int nn,int mm)
  17. {
  18. //这个表格被循环套了起来,就像贪吃蛇的地图,左右和上下相通
  19. //预先给第0行的每一列弄一个点
  20. n=nn,m=mm;
  21. for(int i=0;i<=m;i++)
  22. r[i]=i+1,l[i]=i-1,u[i]=d[i]=i;
  23. r[m]=0;l[0]=cnt=m;
  24. memset(h,-1,sizeof(h));
  25. }
  26. void link(int R,int C)//在R行C列插入点
  27. {
  28. s[C]++;cnt++;//先记录这个点的各种信息
  29. row[cnt]=R; col[cnt]=C;
  30. //把列的链表改动
  31. u[cnt]=C;
  32. d[cnt]=d[C];
  33. u[d[C]]=cnt;
  34. d[C]=cnt;
  35. //把行的链表改动
  36. if(h[R]<0) h[R]=l[cnt]=r[cnt]=cnt;
  37. else
  38. {
  39. r[cnt]=h[R];
  40. l[cnt]=l[h[R]];
  41. r[l[h[R]]]=cnt;
  42. l[h[R]]=cnt;
  43. }
  44. }
  45. void remove(int C)//删除C列以及C列上有点的行
  46. {
  47. r[l[C]]=r[C]; l[r[C]]=l[C];
  48. for(int i=d[C];i!=C;i=d[i])
  49. for(int j=r[i];j!=i;j=r[j])
  50. {
  51. u[d[j]]=u[j];
  52. d[u[j]]=d[j];
  53. s[col[j]]--;//是减得只剩下1吗(dei)
  54. }
  55. }
  56. void resume(int C)//恢复C列以及C列上有点的行
  57. {
  58. r[l[C]]=C; l[r[C]]=C;
  59. for(int i=d[C];i!=C;i=d[i])
  60. for(int j=r[i];j!=i;j=r[j])
  61. {
  62. u[d[j]]=j;
  63. d[u[j]]=j;
  64. s[col[j]]++;
  65. }
  66. }
  67. void dance(int deep)
  68. {
  69. int C=r[0];//找第一个限制条件
  70. if(C>2*nn)//如果所有的行已经被删完就统计答案(能不能>2n)
  71. {
  72. ans++;
  73. for(int i=0,x,y;i<deep;i++)
  74. {
  75. //记录下来选的点的编号,用编号还原行列
  76. x=ansk[i]%nn;
  77. y=(ansk[i]-1)/nn+1;
  78. if(x==0) x=nn;
  79. Ans[ans].a[y]=x;//x和y是等价的,可以交换
  80. }
  81. return;
  82. }
  83. for(int i=C;i<=nn;i=r[i])//找到点最少的列
  84. /*
  85. 这是一处剪枝,因为删掉点最少的列,就是为了满足这个限制条件
  86. 需要枚举删掉的点就少一些,从而使得之后的剪枝更高效
  87. 相当于把搜索树繁茂的地方留给叶子,而深度越深越容易被剪枝
  88. 不加会T
  89. */
  90. if(s[i]<s[C]) C=i;
  91. remove(C);//删掉这一列
  92. for(int i=d[C];i!=C;i=d[i])//枚举答案是这一列的哪个点,因为每一列只能选一个点,所以枚举选哪个
  93. {
  94. ansk[deep]=row[i];//记录答案,这个点编号是row[i]
  95. for(int j=r[i];j!=i;j=r[j]) remove(col[j]);//这个点的行也得删了,把这行有点的列也删掉
  96. dance(deep+1);
  97. for(int j=r[i];j!=i;j=r[j]) resume(col[j]);//回溯
  98. }
  99. resume(C);//回溯过程
  100. }
  101. }
  102. int cmp(const out&A,const out&B)
  103. {
  104. int p=0;while(A.a[p]==B.a[p]) p++;
  105. return A.a[p]<B.a[p];
  106. }
  107. int main()
  108. {
  109. /// freopen("a.out","w",stdout);
  110. scanf("%d",&nn);
  111. /*
  112. nn*nn个格子,每个格子看作舞蹈链的一行
  113. 总共有nn行nn列nn×2-1左对角nn×2-1右对角 共6×nn-2个限制
  114. 把每个限制看作一列,进行精准覆盖
  115. */
  116. DLX::init(nn*nn,6*nn-2);
  117. for(int i=1;i<=nn;i++)
  118. for(int j=1;j<=nn;j++)
  119. {
  120. o++;
  121. DLX::link(o,i);//占据第i行
  122. DLX::link(o,j+nn);//占据第j列(能不能不写这一句)
  123. DLX::link(o,i-j+3*nn);//占据第i-j+nn个左上到右下的对角线
  124. DLX::link(o,i+j+4*nn-2);//占据第i+j-1个右上到左下的对角线
  125. }
  126. DLX::dance(0);//跳舞啦
  127. sort(Ans+1,Ans+ans+1,cmp);
  128. for(int i=1;i<=3;i++,puts(""))
  129. for(int j=1;j<=nn;j++) printf("%d ",Ans[i].a[j]);
  130. printf("%d\n",ans);return 0;
  131. }

Code - Easy Finding戳我

重复覆盖

矩阵中选择一个行的集合,使得每列至少有一个1
所以选了一列之后不能把列中有1的所有的行删掉,复杂度会提高,加一个估价函数的剪枝

Code - [FZU1686]神龙的难题

  1. #include<iostream>
  2. #include<cstdio>
  3. #include<cstdlib>
  4. #include<cstring>
  5. using namespace std;
  6. const int N=70000;
  7. int A[20][20],n,m,n1,m1;
  8. int o,ans,tt;
  9. namespace DLX
  10. {
  11. int n,m,p,u[N],d[N],l[N],r[N];
  12. int col[N],row[N],h[300],s[300],vis[300];
  13. void init(int nn,int mm)
  14. {
  15. n=nn,m=mm;
  16. for(int i=0;i<=m;i++)
  17. l[i]=i-1,r[i]=i+1,d[i]=u[i]=i,s[i]=0;
  18. p=m;l[0]=m;r[m]=0;
  19. memset(h,-1,sizeof(h));
  20. }
  21. void link(int R,int C)
  22. {
  23. p++;row[p]=R;col[p]=C;s[C]++;
  24. d[p]=C;u[p]=u[C];
  25. d[u[C]]=p;u[C]=p;
  26. if(h[R]<0) h[R]=l[p]=r[p]=p;
  27. else r[p]=h[R],l[p]=l[h[R]],r[l[h[R]]]=p,l[h[R]]=p;
  28. }
  29. void remove(int C)
  30. {
  31. for(int i=d[C];i!=C;i=d[i])
  32. l[r[i]]=l[i],r[l[i]]=r[i];
  33. }
  34. void resume(int C)
  35. {
  36. for(int i=u[C];i!=C;i=u[i])
  37. l[r[i]]=i,r[l[i]]=i;
  38. }
  39. int H()
  40. {
  41. int res=0;
  42. memset(vis,0,sizeof(vis));
  43. for(int i=r[0];i;i=r[i])
  44. {
  45. if(vis[i]) continue;
  46. vis[i]=1; res++;
  47. for(int j=d[i];j!=i;j=d[j])
  48. for(int k=r[j];k!=j;k=r[k])
  49. vis[col[k]]=1;
  50. }
  51. return res;
  52. }
  53. void dance(int step)
  54. {
  55. if(step+H()>=ans) return;
  56. if(r[0]==0) {ans=min(ans,step);return;}
  57. int C=r[0];
  58. for(int i=r[C];i;i=r[i]) if(s[i]<s[C]) C=i;
  59. for(int i=d[C];i!=C;i=d[i])
  60. {
  61. remove(i);
  62. for(int j=r[i];j!=i;j=r[j]) remove(j);
  63. dance(step+1);
  64. for(int j=l[i];j!=i;j=l[j]) resume(j);
  65. resume(i);
  66. }
  67. }
  68. }
  69. int main()
  70. {
  71. while(~scanf("%d%d",&n,&m))
  72. {
  73. o=1;ans=1e9;tt=0;
  74. for(int i=1;i<=n;i++)
  75. for(int j=1,x;j<=m;j++)
  76. {
  77. scanf("%d",&x);
  78. if(x) A[i][j]=++tt;
  79. else A[i][j]=0;
  80. }
  81. scanf("%d%d",&n1,&m1);
  82. DLX::init((n-n1+1)*(m-m1+1),tt);
  83. for(int i=1;i<=n-n1+1;i++)
  84. for(int j=1;j<=m-m1+1;j++,o++)
  85. for(int x=i;x<=i+n1-1;x++)
  86. for(int y=j;y<=j+m1-1;y++)
  87. if(A[x][y]) DLX::link(o,A[x][y]);
  88. DLX::dance(0);printf("%d\n",ans);
  89. }
  90. }

三、尾声

舞蹈链的复杂度是指数级别的,但是由于有非常强大的剪枝所以可以有玄学复杂度

在一般竞赛中舞蹈链并没有很广泛的应用和考察
但是这种思想需要大家了解,体会其中舞蹈的优美

弄个题单

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注