文中提及的一些观点和理论,并非全部个人原创,而是自己的总结和心得, 仅供个人学习编程使用!
Dancing Links(DLX),又 被直译为“神奇的舞蹈链”,本质是一个“双向十字循环链表”!是由斯坦福大学的康纳德 E.Knuth在2000年左右提出的一个解决一种NPC问题的算法!对我们acm的竞赛来说,在处理一类搜索问题时,十分有用。
先分享一下学习这种算法比较好的几份资料:
1. 《Dancing Links》 (Donald E. Knuth)本人的论文。英文版的,也有中文的,而且翻译的也很到位: http://sqybi.com/works/dlxcn/#p11#p11
2.《Dancing Links在搜索中的应用》 (momodi)momodi的这篇文章比较系统的讲述了dlx的原理及处理Exact Cover Problem 和 重复覆盖的方法。
依据做过的题目的特点,在简单描述过dlx的插入和删除的方法之后,结合相应的题目,讲一下自己对“完美覆盖(棋盘问题,数独(sudoku)问题,N皇后问题)” 和 “重复覆盖”的理解。
dlx的节点的存储结构:用结构体来表示:
struct node { int S, C; // size->列链表中节点的总数; column-> 列链表头指针; int L, R; // left->左向指针, right-> 右向指针; 左右方向 int U, D; // up-> 上向指针, down-> 下向指针;上下方向 };
dlx的节点的删除
void remove(const int&c) { // column's deleted d[d[c].L].R = d[c].R; d[d[c].R].L = d[c].L; // row's deleted d[d[c].U].D = d[c].D; d[d[c].D].U = d[c].U; }
dlx的节点的恢复
void resume(const int &c) { // column's resume, d指向的节点要保留原有的信息, d[d[c].L].R = c; d[d[c].R].L = c; // row's resume, d指向的节点要保留原有的信息 d[d[c].U].D = c; d[d[c].D].U = c; }
除此之外,为了遍历的方便,要设置一个总的头节点的head!
完美覆盖(精确覆盖)模型
给定一个0-1矩阵,现在要选择一些行,使得一列有且仅有一个 1,如下左:
取行集合{1, 4, 5}便可以使得每一列仅有一个1。如果我们把行集合{2, 3, 6}删掉,并用不同的染色将剩余的行中列为1的标记出来,那么就会得到一个一个完全覆盖的board。这也是这个题目的算法的大体思路:任意选择一列(这里我们先选择任意一列,待会再说如何优化),选择为1的一行,然后将该从该行中找出所有的节点值为1的节点,将这些节点所在的列中节点为值为1的行删除掉,这样我们就可以保证选择了改行之后,保证每列中只有一个1。 这样将所有的行试探之后,如果最后存在一种可以使得原矩阵为空的方案,那么就找到一组解。下面简单说一下对优化(即,每次选择剩余列中元素个数最少的来删除)的理解,
我们优化的出发点是选择尽量少的行找到一组可行解,按照我们上面的思路就是选择一行的同时尽量多的删除其它的行。由此,列的值(多少代表着影响的行数)大的删掉的行数也就越多,那么就更大的可能接近可行解。(只是论述,缺乏严密的数学证明)(更为具体的分析,参见momodi的论文P4,下面附上一段伪代码,帮助理解)
A is the matrix of the 0-1. if (A is empty) { \\A is the 0 - 1 matrix. the problem is solved; return; } choose a column, c,that is unremoved and has fewest elements. ..(1) remove c and each row i that A[i][c] == 1 from matrix A;...(2) for (all row, r, that A[r][c] == 1) { include r in the partial solution.; for each j that A[r][j] == 1 { remove column j and each row i that A[i][j] == 1 from matrix A. ...(3) } repeat this algorithm recursively on the reduced matrix A. resume all column j and row i that was just removed;...(4) } resume c and i we removed at step(2) ...(5);
完美覆盖的cpp实现。
// resumecolumn c and all row i that a[i][c] = 1; void resume(const int &c) { for (int i = d[c].U; i != c; i = d[i].U) { for (int j = d[i].L; j != i; j = d[j].L) { d[d[j].C].S++; d[d[j].U].D = j; d[d[j].D].U = j; } } d[d[c].R].L = c; d[d[c].L].R = c; } // the k'th step of the deepth first search; bool dfs(const int &k) { if (d[head] == head) { return true; } int s = inf, c; for (int t = d[head].R; t != head; t = d[t].R) { if (s > d[t].S) { s = d[t].S; c = t; } } remove(c); for (int i = d[c].D; i != c; i = d[i].D) { for (int j = d[i].R; j != i; j = d[j].R) { remove(d[j].C); } if (dfs(k + 1)) { return true; } for (int j = d[i].L; j != i; j = d[j].L) { resume(d[j].C); } } resume(c); return false; }
重复覆盖模型:在0-1矩阵中选择最少的行,是的每一列至少有一个1.
该问题可以想象成二分图的支配集问题的模型:从X集合选择最少的点,是的能否覆盖住Y集合所有的点。(当然X与Y集合是有边(映射)关系的)。
把这个问题和上面的完美覆盖结合起来看,我们就会发现不同的地方就是,上面红色标出的那句话,实际上也是如此。能够想到的一个中直观的搜索方法是:我们每次选择任意选一列,然后从该列选择任意一行,同时将列值为1的节点所在的列删掉(这里不再是将列上值为1的节点所在的行删掉,因为不再要求列值为1)。如果,最后的所有的列都删掉了,那么就可以说找到一组可行解。
这个题目的做法是用迭代加深的启发式搜索(ID_A*)。那么,我们来说一下启发函数的设计。
int h() { int ret = 0; memset(use, 0, sizeof(use)); for (int t = d[head].R; t != head; t = d[t].R) { if (use[t] == false) { use[t] = true; ret ++; for (int i = d[t].D; i != t; i = d[i].D) { for (int j = d[i].R; j != i; j = d[j].R) { use[d[j].C] = true; } } } } return ret; }
启发函数的值 = 按一定的规则选择列,是的所有的列都被选择需要的最少的行数。(这里的按一定的规则是说,每次开始选择列的时候都遵守一个规则)。说明估价函数(f() = g() + h())发函数的正确性,我们只需要说明两点:1. f()满足单调不减的特性; 2. h()是相容的,也就是说,设pres, curs 为前一个状态和当前状态,weight为状态转移代价,那么h(pres) <= curs + weight。 按通常的dfs的估价函数设计的方法,去实际代价函数g() = depth of the search. 那么 g()函数值每只增加一个单位“1”。对于h()函数,按照f的不递减的特性,需要满足每次减少的最大值为“1"才可。 如果按照我们我们上面启发函数的设计原则,每次计算的时候记录下计算估价函数值时用到的列,那么,对于当前的此次计算挂架函数值,会出现两种情况,一是,原来记录下的列有被删除的(每次只能删除一个原来记录的列,因为,记录的列之间是没有关系的),这样h()的函数值减小一;二是,原来记录的列没有被删除的,这样h()的函数值保持不变。由此,weight = 0 或 1,h() 函数是相容的,f() = g() + h() 满足单调不递减的特性。
简单的来说,对于重复覆盖,我们只删除列,不删除行。由此得到以下的cpp重复覆盖的代码(供参考)
void remove(const int &c) { for (int i = d[c].D; i != c; i = d[i].D) { d[d[i].R].L = d[i].L; d[d[i].L].R = d[i].R; } } void resume(const int &c) { for (int i = d[c].U; i != c; i = d[i].U) { d[d[i].R].L = i; d[d[i].L].R = i; } } bool dfs(const int &k) { if (k + h() >= limit) { return false; } if (d[head].R == head) { if (k < limit) limit = k; return true; } int s = inf, c; for (int t = d[head].R; t != head; t = d[t].R) { if (s > d[t].S) { s = d[t].S; c = t; } } for (int i = d[c].D; i != c; i = d[i].D) { remove(i); for (int j = d[i].R; j != i; j = d[j].R) { remove(j); } if (dfs(k + 1)) { return true; } for (int j = d[i].L; j != i; j = d[j].L) { resume(j); } resume(i); } return false; } int astar() { limit = h(); while(dfs(0) == false) limit++; return limit; }
对于ID_A*,我个人比较喜欢下面的这种实现方法:
int dfs(const int &k) { if (k + h() > limit) { return k + h(); } if (d[head].R == head) { flg = true; //if (k < limit) limit = k; return k; } // printf("k = %d\n", k); int s = inf, c; for (int t = d[head].R; t != head; t = d[t].R) { if (s > d[t].S) { s = d[t].S; c = t; } } int nxt = inf, tmp; for (int i = d[c].D; i != c; i = d[i].D) { remove(i); for (int j = d[i].R; j != i; j = d[j].R) { remove(j); } tmp = dfs(k + 1); if (flg == true) { return tmp; } nxt = min(nxt, tmp); for (int j = d[i].L; j != i; j = d[j].L) { resume(j); } resume(i); } return nxt; }
Copyright © 2007
2011年8月23日 18:26
请问为什么精确覆盖和重复覆盖的remove和resume用法不一样呢,理论上感觉只要把精确覆盖的remove和resume修改了可以保证主体不动来适应重复覆盖,可是实际上却行不通,这个问题很困扰我
2013年12月26日 01:56
@icek: 我是来膜拜的
2013年12月26日 15:15
@rpk74m: 囧了,好多年前的回复了
2023年4月23日 15:23
crediblebh