首页 > 代码库 > DacningLinks实现
DacningLinks实现
本文简单分析DancingLinks实现中的数据结构设计，给出了精确覆盖问题及其扩展问题的代码，并应用于数独问题。
先简单描述一下精确覆盖问题：
给定一个N*M的01矩阵，从中选中若干行，这些行向量相加后每个分量的值都是1，这样的行向量集合称为对列的一个精确覆盖。问题可能是找到一个解，或者找到解使得行向量的个数最少。
如果这些行向量相加后每个分量的值都大于或等于1，我们称这个行向量集为列的一个覆盖。问题是如何找到最小覆盖。
更准确的请参考：
http://zh.wikipedia.org/wiki/%E8%88%9E%E8%B9%88%E9%93%BE
http://zh.wikipedia.org/wiki/%E7%B2%BE%E7%A1%AE%E8%A6%86%E7%9B%96%E9%97%AE%E9%A2%98
数据结构定义：
其中Cell表示一个值为1的元素，成员x，y表示了所在的行和列，而其它成员表明了在其上下右右的结点id。因为是静态分配的cell，所以只需要一个整数表明对应元素在cell中的id即可。这样的表示和直接用Cell* u;之类的表示没有本质区别。
top表示cell中下一个可用的结点的id，每次需要一个新的结点时，只需要return top++;由于是静态分配的cell数组，所以不会考虑结点的回收。
cols[i]和rowss[j]分别指出了第一列和每一行的头结点。而header指出了整个矩阵的头结点。这样做的好处是我们知道行号或列号的时候，可以随机访问对应的行，列。
Cell中的x和y成员以及上述描述的行列表的头结点，不是都需要的，在一些富有技巧的实现中，使得不用这些存储。
再来看初始化：
初始化提供两个函数init和add_element。init表示初始化一个n*m的矩阵，而add_element表示添加一个1元素。要求添加顺序是先按x从小到大，x相同的情况下y从小到大。由外界保证不重复添加。
其中先为整个表分配了头结点，cell[header]和所有的列的头结点组成双向链表，其链接通过l和r成员来表示。同样的，cell[header]和所有的行的头结点组成双向链表，其链接通过u和d成员来表示。
其中的两个for循环分配了列的头结点和行的头结点。以列的头结点初始化为例，在初始情况下cell[header].l = cell[header].r = header; 构成一个只有一个结点的双向链表。我们有cell[header].l是该链表的最后一个结点的不变量。每当添加一个结点的时候，通过cell[header].l找到最后一个元素，然后新加结点和这个最后元素，以及用header标明的最开始的元素建立链接。需要注意的是每个列的头结点的u和d成员需要初始化。
考虑cols[i-1]是上一个分配的元素，也可以不利用cell[header].h。
对行的头结点而言，算法是一样的。
在add_element调用前，我们也有一个不变量，rows[x].h表示x行最后一个结点，cols[y].u表示y列最后一个结点。所以在添加时，只需要分配一结点，和对应的行的头结点，行的最后一个元素，列的头结点，列的最后一个元素建立链接关系。
紧接着看在精确覆盖问题中如何选择一行：
入口是select_row，id表示对应的行。
当一行被选择的时候，这一行覆盖的所有列从需要覆盖的列的双向链表中删除。不妨设当前删除了第j列。但是可能存在其它行x，也覆盖了第j列，这样的x不应该再次被select。所以，对于这样的j考虑所有可能的x，x行可能覆盖的所有列k，x行的元素从k列中删除（k=j的时候不必再删除，因为j列已经被覆盖了）。可以看出在select过程中，id行构成的双向链表没有发生变化。
对于recover方法，其实现刚好和select相反。
另外再看一下一般覆盖中如何选择一行：
同样的，选择id行的时候，将其覆盖的列吕需要覆盖的列从双向链接中删除。对于被删除的列j，可以找到对应的可以覆盖该列的所有行，如果行不是当前正在覆盖j列的行id，那么把第j列从该行所能覆盖的列中删除，下次选择这个行的时候，就不会出现其覆盖了某列，但是该列已经被覆盖过的情况。
在此基础上就得到精确覆盖（找到一个解），一般（多重）覆盖的算法：
最后通过解数独来看看精确覆盖的应用：
一共有81*4列：
第一个81列中每一列表示数独的每一个位置，该列被覆盖的含义是该位置上填了一个元素。
第二个81列被分为9部分，每一部分9列。每一部分表示一行，一个部分中的9个分量表示这一行需要填的9个数。
第三个81列和第二个81列类似，表示9列。
第四个81列和第二个81列也类似，表示9个3*3的块。
矩阵一共有81*9行：
第i行j列填上数字val后（val从0到8），对应于选择了第(i*9+j)*9+val行。
在建立模型后还需要对精确覆盖算法进行优化：
用av[y]表示当前可以覆盖第y列的行的个数。在覆盖时，如果存在某列只有一个覆盖行，则优先选择使得这列先被覆盖。如果某列不存在覆盖行，则可以直接返回无解。
数独问题的一个实例：
http://cstest.scu.edu.cn/soj/problem.action?id=2982
多重覆盖问题的一个实例：
http://cstest.scu.edu.cn/soj/problem.action?id=3778
先简单描述一下精确覆盖问题：
给定一个N*M的01矩阵，从中选中若干行，这些行向量相加后每个分量的值都是1，这样的行向量集合称为对列的一个精确覆盖。问题可能是找到一个解，或者找到解使得行向量的个数最少。
如果这些行向量相加后每个分量的值都大于或等于1，我们称这个行向量集为列的一个覆盖。问题是如何找到最小覆盖。
更准确的请参考：
http://zh.wikipedia.org/wiki/%E8%88%9E%E8%B9%88%E9%93%BE
http://zh.wikipedia.org/wiki/%E7%B2%BE%E7%A1%AE%E8%A6%86%E7%9B%96%E9%97%AE%E9%A2%98
数据结构定义：
const int maxn = 505;
struct Cell
{
int u, d, l, r;
int x, y;
};
Cell cell[maxn*(maxn+6)];
int top;
int cols[maxn], rows[maxn];
int header;其中Cell表示一个值为1的元素，成员x，y表示了所在的行和列，而其它成员表明了在其上下右右的结点id。因为是静态分配的cell，所以只需要一个整数表明对应元素在cell中的id即可。这样的表示和直接用Cell* u;之类的表示没有本质区别。
top表示cell中下一个可用的结点的id，每次需要一个新的结点时，只需要return top++;由于是静态分配的cell数组，所以不会考虑结点的回收。
cols[i]和rowss[j]分别指出了第一列和每一行的头结点。而header指出了整个矩阵的头结点。这样做的好处是我们知道行号或列号的时候，可以随机访问对应的行，列。
Cell中的x和y成员以及上述描述的行列表的头结点，不是都需要的，在一些富有技巧的实现中，使得不用这些存储。
再来看初始化：
初始化提供两个函数init和add_element。init表示初始化一个n*m的矩阵，而add_element表示添加一个1元素。要求添加顺序是先按x从小到大，x相同的情况下y从小到大。由外界保证不重复添加。
void init(int n, int m)
{
top = 0;
header = top++;
memset(cell, 0, sizeof (cell[0]));
for (int i = 0; i < m; ++i)
{
const int me = top++;
int last = cell[header].l; cols[i] = me;
cell[last].r = me, cell[me].l = last;
cell[me].r = header, cell[header].l = me;
cell[me].y = i;cell[me].u = cell[me].d = me;
}
for (int i = 0; i < n; ++i)
{
const int me = top++; rows[i] = me;
int last = cell[header].u;
cell[last].d = me, cell[me].u = last;
cell[me].d = header, cell[header].u = me;
cell[me].x = i;cell[me].l = cell[me].r = me;
}
}其中先为整个表分配了头结点，cell[header]和所有的列的头结点组成双向链表，其链接通过l和r成员来表示。同样的，cell[header]和所有的行的头结点组成双向链表，其链接通过u和d成员来表示。
其中的两个for循环分配了列的头结点和行的头结点。以列的头结点初始化为例，在初始情况下cell[header].l = cell[header].r = header; 构成一个只有一个结点的双向链表。我们有cell[header].l是该链表的最后一个结点的不变量。每当添加一个结点的时候，通过cell[header].l找到最后一个元素，然后新加结点和这个最后元素，以及用header标明的最开始的元素建立链接。需要注意的是每个列的头结点的u和d成员需要初始化。
考虑cols[i-1]是上一个分配的元素，也可以不利用cell[header].h。
对行的头结点而言，算法是一样的。
void add_element(int x, int y)
{
const int me = top++;
cell[me].x = x, cell[me].y = y;
{
const int row_header = rows[x];
const int last = cell[row_header].l;
cell[last].r = me, cell[me].l = last;
cell[me].r = row_header, cell[row_header].l = me;
}
{
const int col_header = cols[y];
const int last = cell[col_header].u;
cell[last].d = me, cell[me].u = last;
cell[me].d = col_header, cell[col_header].u = me;
}
}
在add_element调用前，我们也有一个不变量，rows[x].h表示x行最后一个结点，cols[y].u表示y列最后一个结点。所以在添加时，只需要分配一结点，和对应的行的头结点，行的最后一个元素，列的头结点，列的最后一个元素建立链接关系。
紧接着看在精确覆盖问题中如何选择一行：
void disable_row(int id, int y)
{
for (int i = cell[rows[id]].r; i != rows[id]; i = cell[i].r)
{
if (cell[i].y != y)
{
cell[cell[i].u].d = cell[i].d;
cell[cell[i].d].u = cell[i].u;
}
}
}
void select_row(int id)
{
int p = rows[id];
for (int q = cell[p].r; q != p; q = cell[q].r)
{
const int col = cols[cell[q].y];
cell[cell[col].l].r = cell[col].r;
cell[cell[col].r].l = cell[col].l;
for (int i = cell[col].d; i != col; i = cell[i].d)
{
disable_row(cell[i].x, cell[q].y);
}
}
}入口是select_row，id表示对应的行。
当一行被选择的时候，这一行覆盖的所有列从需要覆盖的列的双向链表中删除。不妨设当前删除了第j列。但是可能存在其它行x，也覆盖了第j列，这样的x不应该再次被select。所以，对于这样的j考虑所有可能的x，x行可能覆盖的所有列k，x行的元素从k列中删除（k=j的时候不必再删除，因为j列已经被覆盖了）。可以看出在select过程中，id行构成的双向链表没有发生变化。
对于recover方法，其实现刚好和select相反。
另外再看一下一般覆盖中如何选择一行：
void multi_select_row(int id)
{
int p = rows[id];
for (int q = cell[p].r; q != p; q = cell[q].r)
{
const int col = cols[cell[q].y];
cell[cell[col].l].r = cell[col].r;
cell[cell[col].r].l = cell[col].l;
for (int i = cell[col].d; i != col; i = cell[i].d)
if (i != q)
{
cell[cell[i].l].r = cell[i].r;
cell[cell[i].r].l = cell[i].l;
}
}
}同样的，选择id行的时候，将其覆盖的列吕需要覆盖的列从双向链接中删除。对于被删除的列j，可以找到对应的可以覆盖该列的所有行，如果行不是当前正在覆盖j列的行id，那么把第j列从该行所能覆盖的列中删除，下次选择这个行的时候，就不会出现其覆盖了某列，但是该列已经被覆盖过的情况。
在此基础上就得到精确覆盖（找到一个解），一般（多重）覆盖的算法：
int answers[maxn];
bool exact_cover(int now)
{
int who = cell[header].r;
if (who == header)
{
// 找到一个解
return false; // 需要遍历所有解时返回false，只需要一个解时返回true
}
for (int i = cell[who].d; i != who; i = cell[i].d)
{
select_row(cell[i].x);
answers[now] = cell[i].x;
if (exact_cover(now+1))
{
return true;
}
recover_row(cell[i].x);
}
return false;
}
bool multi_cover(int now)
{
int who = cell[header].r;
if (who == header)
{
// 找到一个解
return false; // 需要遍历所有解时返回false，只需要一个解时返回true
}
for (int i = cell[who].d; i != who; i = cell[i].d)
{
multi_select_row(cell[i].x);
answers[now] = cell[i].x;
if (multi_cover(now+1))
{
return true;
}
multi_recover_row(cell[i].x);
}
return false;
}最后通过解数独来看看精确覆盖的应用：
一共有81*4列：
第一个81列中每一列表示数独的每一个位置，该列被覆盖的含义是该位置上填了一个元素。
第二个81列被分为9部分，每一部分9列。每一部分表示一行，一个部分中的9个分量表示这一行需要填的9个数。
第三个81列和第二个81列类似，表示9列。
第四个81列和第二个81列也类似，表示9个3*3的块。
矩阵一共有81*9行：
第i行j列填上数字val后（val从0到8），对应于选择了第(i*9+j)*9+val行。
在建立模型后还需要对精确覆盖算法进行优化：
用av[y]表示当前可以覆盖第y列的行的个数。在覆盖时，如果存在某列只有一个覆盖行，则优先选择使得这列先被覆盖。如果某列不存在覆盖行，则可以直接返回无解。
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <numeric>
#include <iostream>
using namespace std;
const int maxn = 1005;
struct Cell
{
int u, d, l, r;
int x, y;
};
Cell cell[maxn*(maxn+6)];
int top;
int cols[maxn], rows[maxn];
int header;
int av[maxn];
static inline void init(int n, int m)
{
top = 0;
header = top++;
memset(cell, 0, sizeof (cell[0]));
fill(av, av+m, 0);
for (int i = 0; i < m; ++i)
{
const int me = top++;
int last = cell[header].l; cols[i] = me;
cell[last].r = me, cell[me].l = last;
cell[me].r = header, cell[header].l = me;
cell[me].y = i;cell[me].u = cell[me].d = me;
}
for (int i = 0; i < n; ++i)
{
const int me = top++; rows[i] = me;
int last = cell[header].u;
cell[last].d = me, cell[me].u = last;
cell[me].d = header, cell[header].u = me;
cell[me].x = i;cell[me].l = cell[me].r = me;
}
}
static inline void add_element(int x, int y)
{
const int me = top++;
cell[me].x = x, cell[me].y = y;
{
const int row_header = rows[x];
const int last = cell[row_header].l;
cell[last].r = me, cell[me].l = last;
cell[me].r = row_header, cell[row_header].l = me;
}
{
const int col_header = cols[y];
const int last = cell[col_header].u;
cell[last].d = me, cell[me].u = last;
cell[me].d = col_header, cell[col_header].u = me;
}
++av[y];
}
static inline void disable_row(int id, int y)
{
const int row_header = rows[id];
for (int i = cell[row_header].r; i != row_header; i = cell[i].r)
if (cell[i].y != y)
{
cell[cell[i].u].d = cell[i].d;
cell[cell[i].d].u = cell[i].u;
--av[cell[i].y];
}
}
static inline void enable_row(int id, int y)
{
const int row_header = rows[id];
for (int i = cell[row_header].l; i != row_header; i = cell[i].l)
if (cell[i].y != y)
{
cell[cell[i].u].d = i;
cell[cell[i].d].u = i;
++av[cell[i].y];
}
}
static inline void select_row(int id)
{
const int p = rows[id];
for (int q = cell[p].r; q != p; q = cell[q].r)
{
const int col = cols[cell[q].y];
cell[cell[col].l].r = cell[col].r;
cell[cell[col].r].l = cell[col].l;
--av[cell[q].y];
for (int i = cell[col].d; i != col; i = cell[i].d)
{
disable_row(cell[i].x, cell[q].y);
}
}
}
static inline void recover_row(int id)
{
const int p = rows[id];
for (int q = cell[p].l; q != p; q = cell[q].l)
{
const int col = cols[cell[q].y];
cell[cell[col].l].r = col;
cell[cell[col].r].l = col;
++av[cell[q].y];
for (int i = cell[col].u; i != col; i = cell[i].u)
{
enable_row(cell[i].x, cell[q].y);
}
}
}
int answers[maxn];
int orz;
bool exact_cover(int now)
{
int who = cell[header].r;
if (who == header)
{
orz = now;
return true;
}
int best = 1000000;
for (int i = cell[header].r; i != header; i = cell[i].r)
if (av[cell[i].y] < best)
{
who = i;
best = av[cell[i].y];
if (best <= 1) break;
}
if (best == 0) return false;
for (int i = cell[who].d; i != who; i = cell[i].d)
{
select_row(cell[i].x);
answers[now] = cell[i].x;
if (exact_cover(now+1))
{
return true;
}
recover_row(cell[i].x);
}
return false;
}
// puzzle为输入，其元素是0到9，0表示该位置元素待定
int puzzle[9][9];
void solve()
{
init(81*9, 81*4);
for (int i = 0; i < 9; ++i)
for (int j = 0; j < 9; ++j)
for (int val = 0; val < 9; ++val)
if (puzzle[i][j] == 0 || puzzle[i][j] == val + 1)
{
const int id = (i*9+j)*9+val;
const int t = i / 3 * 3 + j / 3;
add_element(id, i*9+j);
add_element(id, 81+i*9+val);
add_element(id, 81+81+j*9+val);
add_element(id, 81+81+81+t*9+val);
}
exact_cover(0);
// 假定exact_cover返回true
for (int i = 0; i < orz; ++i)
{
int id = answers[i] / 9;
int row = id / 9;
int col = id % 9;
int val = answers[i] % 9;
puzzle[row][col] = val+1;
}
}数独问题的一个实例：
http://cstest.scu.edu.cn/soj/problem.action?id=2982
多重覆盖问题的一个实例：
http://cstest.scu.edu.cn/soj/problem.action?id=3778
DacningLinks实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。