Dancing Links是Knuth教授在近几年来写的一篇文章,是一类搜索问题的通用优化。它主要利用双向十字链表来存储稀疏矩阵,来达到搜索中的优化。在搜索问题中,矩阵会随着递归的加深会变得越来越稀疏,这种情况下用dancelinks来存储矩阵,往往会达到很好的效果。
核心代码:
对于熟悉双向链表的人,一定不会陌生:
L[R[x]] = L[x]
R[L[x]] = R[x]
这两句话时将x从链表中删除。
但很少有人知道下面两句:
L[R[x]] = x
R[L[x]] = x
这两句会将已经删除的节点x重新添加回双向链表中。是不是非常神奇。我们在链表中删除,只是进行一个标记,并不真正进行清空内存的操作。可能这不是好的编程习惯,你可能会认为内存泄露,但在这里,我们就是要这种效果。
给一个0、1矩阵,现在要选择一些(最少)行,使得每列有且仅有一个1,即精确覆盖。
或者,选择一些(最少)行,使得每列至少有一个1,即重复覆盖。
这两个问题都是NP问题,可以用搜索解决,DLX可以大大加快搜索速度。
精确覆盖:
首先选择当前要覆盖的列(含1最少的列),将该列和能够覆盖到该列的行全部去掉,再枚举添加的方法。枚举某一行r,假设它是解集中的一个,那么该行所能覆盖到的所有列都不必再搜,所以删除该行覆盖到的所有列,又由于去掉的列相当于有解,所以能够覆盖到这些列的行也不用再搜,删之。
重复覆盖:
首先选择当前要覆盖的列(同上),将该列删除,枚举覆盖到该列的所有行:对于某一行r,假设它是解集中的一个,那么该行所能覆盖到的列都不必再搜,所以删除该行覆盖到的所有列。注意此时不用删去覆盖到这些列的行,因为一列中允许有多个1。这里有一个A*的优化:估价函数h意义为从当前状态最好情况下需要添加几条边才能覆盖。
例:HDU3111 Sudoku
/*
DLX解决9*9的数独问题,转化为729*324的精确覆盖问题
行:
一共9 * 9 * 9 == 729行。一共9 * 9小格,每一格有9种可能性(1 - 9),每一种可能都对应着一行。
列:
一共(9 + 9 + 9) * 9 + 81 == 324 种前面三个9分别代表着9行9列和9小块,乘以9的意思是9种可能(1 - 9),因为每种可能只可以选择一个。
81代表着81个小格,限制着每一个小格只放一个数字。
读入数据后,如果为'.',则建9行,即有1-9种可能,否则建一行,表示某小格只能放确定的某个数字。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7fffffff;
const int NN = 350;
const int MM = 750;
int n,m; //列,行
int cntc[NN];
int L[NN*MM],R[NN*MM],U[NN*MM],D[NN*MM];
int C[NN*MM];
int head;
int mx[MM][NN];
int O[MM],idx;
int ans[10][10];
//删除列及其相应的行
void remove(int c)
{
int i,j;
L[R[c]] = L[c];
R[L[c]] = R[c];
for(i = D[c]; i != c; i = D[i])
{
for(j = R[i]; j != i; j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
cntc[C[j]]--;
}
}
}
//恢复列及其相应的行
void resume(int c)
{
int i,j;
R[L[c]] = c;
L[R[c]] = c;
for(i = D[c]; i != c; i = D[i])
{
for(j = R[i]; j != i; j = R[j])
{
U[D[j]] = j;
D[U[j]] = j;
cntc[C[j]]++;
}
}
}
bool dfs()
{
int i,j,c;
if(R[head] == head)
return true;
int min = INF;
for(i = R[head]; i != head; i = R[i])
{
if(cntc[i] < min)
{
min = cntc[i];
c = i;
}
}
remove(c);
for(i = D[c]; i != c; i = D[i])
{
//i是某点的序号,将该点所在行的行号保存
O[idx++] = (i-1)/n;
for(j = R[i]; j != i; j = R[j])
remove(C[j]);
if(dfs())
return true;
for(j = L[i]; j != i; j = L[j])
resume(C[j]);
idx--;
}
resume(c);
return false;
}
bool build()
{
int i,j,now,pre,first;
idx = head = 0;
for(i = 0; i < n; i++)
{
R[i] = i+1;
L[i+1] = i;
}
R[n] = 0;
L[0] = n;
//列双向链表
for(j = 1; j <= n; j++)
{
pre = j;
cntc[j] = 0;
for(i = 1; i <= m; i++)
{
if(mx[i][j])
{
cntc[j]++;
now = i*n+j;
C[now] = j;
D[pre] = now;
U[now] = pre;
pre = now;
}
}
U[j] = pre;
D[pre] = j;
if(cntc[j] == 0)
return false;
}
//行双向链表
for(i = 1; i <= m; i++)
{
pre = first = -1;
for(j = 1; j <= n; j++)
{
if(mx[i][j])
{
now = i*n+j;
if(pre == -1)
first = now;
else
{
R[pre] = now;
L[now] = pre;
}
pre = now;
}
}
if(first != -1)
{
R[pre] = first;
L[first] = pre;
}
}
return true;
}
int T;
void print()
{
int i,j;
int x,y,k;
for(i = 0; i < idx; i++)
{
int r = O[i];
k = r%9;
if(k==0) k = 9;
int num = (r - k)/9 + 1;
y = num%9;
if(y == 0) y = 9;
x = (num-y)/9 + 1;
ans[x][y] = k;
}
if(idx == 0)
printf("impossible\n");
else
{
for(i = 1; i <= 9; i++)
{
for(j = 1; j <= 9; j++)
printf("%d",ans[i][j]);
printf("\n");
}
}
if(T!=0)
printf("---\n");
}
int main()
{
int i,j,k;
int cases;
char cao[12];
char s[12][12];
scanf("%d",&cases);
T = cases;
while(T--)
{
if(T < cases-1)
scanf("%s",cao);
for(i = 1; i <= 9; i++)
scanf("%s",&s[i][1]);
memset(mx,0,sizeof(mx));
for(i = 1; i <= 9; i++)
{
for(j = 1; j <= 9; j++)
{
int t = (i-1)*9 + j;
if(s[i][j] == '?')
{
for(k = 1; k <= 9; k++)
{
mx[9*(t-1)+k][t] = 1; //81grid 每个小格只能放一个数字
mx[9*(t-1)+k][81+(i-1)*9+k] = 1; //9row 每行数字k只能出现一次
mx[9*(t-1)+k][162+(j-1)*9+k] = 1; //9col 每列数字k只能出现一次
mx[9*(t-1)+k][243+((i-1)/3*3+(j+2)/3-1)*9+k] = 1; //subgrid 每个3*3格子数字k只能出现一次
}
}
else
{
k = s[i][j] - '0';
mx[9*(t-1)+k][t] = 1; //81grid
mx[9*(t-1)+k][81+(i-1)*9+k] = 1; //9row
mx[9*(t-1)+k][162+(j-1)*9+k] = 1; //9col
mx[9*(t-1)+k][243+((i-1)/3*3+(j+2)/3-1)*9+k] = 1; //subgrid
}
}
}
n = 324;
m = 729;
build();
dfs();
print();
}
return 0;
}
例:ZOJ3209 Treasure Map
/*
题意:在坐标系中,有一个大矩形(长宽不超过30)和一些坐标大小都固定的小矩形(500个),问有没有一种方案使得找出最少的小矩形来覆盖大
矩形。注意,小矩形之间不能重叠。
分析:
完全覆盖,不能重叠,不禁想到了dance links的精确覆盖问题。将小矩形(500)做行,大矩形的每个小格子(30*30个)做列。
意思很明显了。。。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int INF = 0x7ffffff;
const int NN = 30*30+10; //900列
const int MM = 500+10; //500行
int n,m; //列和行
int L[NN*MM],R[NN*MM],U[NN*MM],D[NN*MM];
int C[NN*MM];
int head;
int cntc[NN];
int mx[MM][NN];
int x,y;
int result;
void change(int p, int x1, int y1, int x2, int y2) //矩形能够覆盖到的格子,行覆盖到的列
{
int i,j;
for(j = y1+1; j <= y2; j++)
{
for(i = x1+1; i <= x2; i++)
{
mx[p][(j-1)*x+i] = 1;
}
}
}
void remove(int c)
{
int i,j;
L[R[c]] = L[c];
R[L[c]] = R[c];
for(i = D[c]; i != c; i = D[i])
{
for(j = R[i]; j != i; j = R[j])
{
U[D[j]] = U[j];
D[U[j]] = D[j];
cntc[C[j]]--;
}
}
}
void resume(int c)
{
int i,j;
R[L[c]] = c;
L[R[c]] = c;
for(i = D[c]; i != c; i = D[i])
{
for(j = R[i]; j != i; j = R[j])
{
U[D[j]] = j;
D[U[j]] = j;
cntc[C[j]]++;
}
}
}
void dfs(int k)
{
int i,j,c;
if(R[head] == head)
{
if(result > k)
result = k;
return;
}
if(k >= result)
return;
int min = INF;
for(i = R[head]; i != head; i = R[i])
{
if(cntc[i] < min)
{
min = cntc[i];
c = i;
}
}
remove(c);
for(i = D[c]; i != c; i = D[i])
{
for(j = R[i]; j != i; j = R[j])
remove(C[j]);
dfs(k+1);
for(j = L[i]; j != i; j = L[j])
resume(C[j]);
}
resume(c);
return;
}
bool build()
{
int i,j;
int now,pre,first;
head = 0;
memset(cntc,0,sizeof(cntc));
for(i = 0; i < n; i++)
{
R[i] = i+1;
L[i+1] = i;
}
R[n] = 0;
L[0] = n;
//列链表
for(j = 1; j <= n; j++)
{
pre = j;
for(i = 1; i <= m; i++)
{
if(mx[i][j])
{
now = i*n+j;
cntc[j]++;
C[now] = j;
D[pre] = now;
U[now] = pre;
pre = now;
}
}
D[pre] = j;
U[j] = pre;
if(cntc[j] == 0)
return false;
}
//行链表
for(i = 1; i <= m; i++)
{
pre = first = -1;
for(j = 1; j <= n; j++)
{
if(mx[i][j])
{
now = i*n+j;
if(pre == -1)
first = now;
else
{
R[pre] = now;
L[now] = pre;
}
pre = now;
}
}
if(first != -1)
{
R[pre] = first;
L[first] = pre;
}
}
return true;
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
int i;
int t;
int p;
int x1,y1,x2,y2;
scanf("%d",&t);
while(t--)
{
scanf("%d %d %d",&x,&y,&p);
m = p; //行
n = x*y; //列
result = INF;
memset(mx,0,sizeof(mx));
for(i = 1; i <= p; i++)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
change(i,x1,y1,x2,y2);
}
if(build())
{
dfs(0);
if(result != INF)
printf("%d\n",result);
else
printf("-1\n");
}
else
printf("-1\n");
}
return 0;
}
例:HDU2295 Radar
/*
最小支配集问题:
二分枚举最小距离,判断可行性。可行性即重复覆盖模型,DLX解之。
A*的启发函数:
对当前矩阵来说,选择一个未被控制的列,很明显该列最少需要1个行来控制,所以ans++。
该列被控制后,把它所对应的行,全部设为已经选择,并把这些行对应的列也设为被控制。继续选择未被控制的列,直到没有这样的列。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int INF = 0x7fffffff;
const int MAX = 55;
const double EPS = 1e-8;
int n,m,k;
double city[MAX][2];
double radar[MAX][2];
double dis[MAX][MAX]; //dis[i][j]表示雷达i到cityj的距离
int L[MAX*MAX],R[MAX*MAX],U[MAX*MAX],D[MAX*MAX];
int C[MAX*MAX];
int cntc[MAX];
int head;
int mx[MAX][MAX];
bool vis[MAX];
//删除元素c所在的列
void remove(int c)
{
int i;
for(i = D[c]; i != c; i = D[i])
{
R[L[i]] = R[i];
L[R[i]] = L[i];
}
}
//恢复元素c所在的列
void resume(int c)
{
int i;
for(i = D[c]; i != c; i = D[i])
{
R[L[i]] = i;
L[R[i]] = i;
}
}
int h()
{
int i,j,c;
memset(vis,0,sizeof(vis));
int ans = 0;
for(c = R[head]; c != head; c = R[c])
{
if(!vis[c])
{
ans++;
for(i = D[c]; i != c; i = D[i])
for(j = R[i]; j != i; j = R[j])
vis[C[j]] = true;
}
}
return ans;
}
bool dfs(int dep)
{
int i,j;
if(R[head] == head)
return true;
if(dep + h() > k) //A_Star剪枝
return false;
int Min=INF,c;
for(i = R[head]; i != head; i = R[i])
{
if(cntc[i] < Min)
{
Min = cntc[i];
c = i;
}
}
for(i = D[c]; i != c; i = D[i])
{
remove(i);
for(j = R[i]; j != i; j = R[j])
{
remove(j);
cntc[C[j]]--;
}
if(dfs(dep+1))
return true;
for(j = L[i]; j != i; j = L[j])
{
resume(j);
cntc[C[j]]++;
}
resume(i);
}
return false;
}
bool build(double mid)
{
int i,j;
memset(cntc,0,sizeof(cntc));
memset(mx,0,sizeof(mx));
for(i = 1; i <= m; i++)
{
for(j = 1; j <= n; j++)
{
if(dis[i][j] - mid < EPS)
mx[i][j] = 1;
}
}
head = 0;
for(i = 0; i < n; i++)
{
R[i] = i+1;
L[i+1] = i;
}
R[n] = 0;
L[0] = n;
int first,pre,now;
//列链表
for(j = 1; j <= n; j++)
{
pre = j;
for(i = 1; i <= m; i++)
{
if(mx[i][j])
{
cntc[j]++;
now = i*n+j;
C[now] = j;
U[now] = pre;
D[pre] = now;
pre = now;
}
}
D[pre] = j;
U[j] = pre;
if(cntc[j] == 0)
return false;
}
for(i = 1; i <= m; i++)
{
pre = first = -1;
for(j = 1; j <= n; j++)
{
if(mx[i][j])
{
now = i*n+j;
if(pre == -1)
first = now;
else
{
R[pre] = now;
L[now] = pre;
}
pre = now;
}
}
if(first != -1)
{
R[pre] = first;
L[first] = pre;
}
}
return true;
}
bool OK(double mid)
{
if(build(mid))
return dfs(0);
else
return false;
}
double solve()
{
double low = 0;
double high = 1500;
double ans = -1;
while(low+EPS<high)
{
double mid = (low+high)/2.0;
if(OK(mid))
{
ans = mid;
high = mid;
}
else
low = mid;
}
return ans;
}
double Dis(int i, int j)
{
return sqrt((double)(radar[i][0]-city[j][0])*(radar[i][0]-city[j][0])+(radar[i][1]-city[j][1])*(radar[i][1]-city[j][1]));
}
void Init()
{
int i,j;
for(i = 1; i <= m; i++)
for(j = 1; j <= n; j++)
dis[i][j] = Dis(i,j);
}
int main()
{
int i;
int t;
scanf("%d",&t);
while(t--)
{
scanf("%d %d %d",&n,&m,&k);
for(i = 1; i <= n; i++)
scanf("%lf %lf",&city[i][0],&city[i][1]);
for(i = 1; i <= m; i++)
scanf("%lf %lf",&radar[i][0],&radar[i][1]);
Init();
printf("%.6lf\n",solve());
}
return 0;
}
other: poj3074 hdu3663 2828
分享到:
相关推荐
dancing links 解决骑士遍历问题,实验报告,含源代码
dancing links X算法python实现demo程序
使用Dancing Links(DLX)的Sudoku求解器 数独可以简化为精确的掩护问题,该问题被认为是NP完全的。 NP-complete的分类仅适用于广义nxn数独,而不适用于9x9数独,因为它是有限实例。 确切的掩护问题是一个决策问题...
dlx.js Donald Knuth的Dancing Links与算法X(DLX)JavaScript实现,用于解决确切的封面问题。
Java 数独求解器这是使用 Dancing Links 解决数独谜题的 Donald Knuth 算法 X 的实现。 这开始是为了调查您是否可以在不完全理解问题的情况下解决问题(例如数独解谜器)(在这种情况下,不知道数独谜题是数学问题的...
高级数据结构,舞蹈链,用于搜索,可以达到非常大的剪枝,一些令人发指的复杂度也可以在瞬间搜出结果
Dancing Links 算法的 Java 实现,这是他的算法的快速实现,用于解决精确矩阵覆盖问题。 参见 Knuth 对算法和一些有趣应用的描述。 支持 跳舞链接按原样提供。 如果它坏了,你可以保留两块。 示例用法 一些示例作为...
DLX Instruction Set Architecture
一款很好用的DLX汇编器,链接器,模拟dlx环境,win7下可视
这是一个用java写得dlx模拟器,实现了流水线和解决相关
DLX CPU VHDL CODE UNIVERSITY
这是北京邮电大学研究生高级系统结构实验大作业,里面包含一到五全部实验,拿去改了学院、名字、学号即可用
学习使用 DLX 汇编语言编程,进一步分析相关现象。 二、实验设备环境 DLX 汇编语言环境 三、实验内容和要求 自编一段汇编代码,完成一维向量加法运算,并输出结果。观察程序中出现的数据/控 制/结构相关。(注:使用...
dlx语言写的求和运算,计算机系统结构试验
LordPE DLX增强豪华版 (1) 为LordPE查看输入表部分加上搜索功能 (2) 为LordPE查看输入表部分加右键菜单(仅复制ThunkRVA/FirstThunk列). (3) 当点击LordPE查看输入表部分中"View always FirstThunk",保持光条在原来...
DLX指令集实现程序,将汇编代码转换成二进制代码写入文件中。
DLX算法,是由Knuth提出的一种在图论中图遍历的一种高效算法。
用于修改H1、H2步步高学习机内部DLX文件内的图片,从而达到修改学习机内部程序图片显示的效果
DLX流水线指令调度,测试指令调度对系统性能的影响。包括实验过程,截图,实验原理和改进方法等,供同学们参考。蔡老师的学生你们懂的。
DLX用于高效率搜索,是一种覆盖问题模型的算法。DLX利用了双向链表,体现了数据结构的美。