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
分享到：
相关推荐
报告还对数据结构DancingLinks进行了解释，这是一种双向循环十字链表，其中定义了数据对象、数据关系和基本操作等。 在详细设计部分，报告给出了求解骑士遍历问题的具体代码。通过遍历棋盘的每个位置，并根据...
标题中的"DLX_Links_DLX_"暗示了我们讨论的主题是关于一种名为"Dancing Links"（跳舞链）的算法，通常简称为DLX。这个算法是由Donald Knuth提出的一种高效解决完全背包问题、数独问题和其他一系列组合优化问题的方法...
1. 算法背景与原理：Dancing Links算法也称为DLX算法，它的核心思想是通过双向链表结构来管理零元素，这样在搜索过程中能够快速删除和恢复整个候选解。算法对选择矩阵进行动态调整，每解决一行，就利用双向链表跳过...
标题中提到的“算法参考资料DLXcn-DancingLinks中文版”指向了一个特定的算法资料，该资料是关于“Dancing Links”算法的中文版本。Dancing Links算法，也称为DLX算法，是Donald Knuth所发明的一种回溯算法，用于...
Dancing Links算法的核心思想是利用链表数据结构来表示问题的约束矩阵，并通过一种特殊的链接方式——“舞蹈链接”来高效地进行回溯搜索。在Rust编程语言中，我们可以利用其强大的类型系统和内存管理特性来实现这一...
描述中提到的"Donald Knuth的Dancing Links与算法X（DLX）JavaScript实现"，暗示了这个项目是将Dancing Links算法用JavaScript语言进行了编码。Donald Knuth是一位著名的计算机科学家，他在《计算机程序设计艺术》...
标题中的"dlx.rar_dlx.m"和描述中提到的内容暗示了这是一个关于解决特定问题的编程实例，使用了“ Dancing Links（舞蹈链） ”算法，由Donald Knuth提出，主要用于解决0-1背包、全排列等问题。在这个实例中，目标是...
使用Dancing Links（DLX）的Sudoku求解器 数独可以简化为精确的掩护问题，该问题被认为是NP完全的。 NP-complete的分类仅适用于广义nxn数独，而不适用于9x9数独，因为它是有限实例。 确切的掩护问题是一个决策问题...
DLX（ Dancing Links ）算法，由计算机科学家Donald Knuth提出，是一种在图论中用于解决完全多对一匹配问题的高效算法。它在回溯搜索中展现出优秀的性能，尤其适用于解决0-1背包、 Exact Cover 和其他组合优化问题。...
在这个案例中，我们关注的是一个名为“sudoku-solver”的项目，它使用了DLX（Dancing Links）算法来高效地求解数独难题。DLX算法是由日本数学家和程序员Hakuo Okada发明的，它是基于一种称为"Exact Cover"问题的解决...
Java 数独求解器这是使用 Dancing Links 解决数独谜题的 Donald Knuth 算法 X 的实现。 这开始是为了调查您是否可以在不完全理解问题的情况下解决问题（例如数独解谜器）（在这种情况下，不知道数独谜题是数学问题的...
DLX，全称为 Dancing Links（跳舞链），是由日本数学家和计算机科学家Hideo Kojima提出的。这个算法在解决完全背包问题、0-1背包问题、数独等覆盖问题上表现出色，它巧妙地利用了数据结构，特别是双向链表的特性，来...
DLX（Dancing Links）算法是一种用于解决精确覆盖问题的高效算法。精确覆盖问题通常指的是在一组元素中选取一些子集，使得这些子集恰好覆盖了所有元素，并且每个元素只被覆盖一次。DLX算法基于回溯思想，通过链表...
1. `DancingLinks`类的定义，用于构建和操作舞蹈链接矩阵。 2. `n_queens`函数，用于设置初始状态并开始回溯搜索。 3. 回溯过程的实现，包括选择下一步、检查冲突、放置皇后和回溯等步骤。 4. 解的打印和计数，用于...
Dancing Links 算法的 Java 实现，这是他的算法的快速实现，用于解决精确矩阵覆盖问题。 参见 Knuth 对算法和一些有趣应用的描述。 支持 跳舞链接按原样提供。 如果它坏了，你可以保留两块。 示例用法 一些示例作为...
Dancing Links（简称DLX）是一种处理双向链表元素的高效方法。当一个元素从链表中移除时，通过更新其前驱（L[x]）和后继（R[x]）节点的指针，使其不再指向当前节点，从而实现了元素的删除。具体操作为： \[L[R[x]] \...
DLX是一种32位精简指令集计算机（RISC）架构，其特点是可以仅用三种指令格式来管理。DLX的核心是一个固定的定点单元（FXU），并且它还包括一个浮点数扩展。DLX指令集架构主要由以下几个知识点组成： 1. DLX架构基础...