首页 > 其他 > 详细

DacningLinks实现

时间：2014-08-23 15:24:51      阅读：289      评论：0      收藏：0      [点我收藏+]
本文简单分析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

数据结构定义：
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实现

原文：http://blog.csdn.net/baihacker/article/details/38778427
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！