【数据结构】用Dancing Links解决精确覆盖问题

DancingLinks

一、基本结构

　　十字链表通常可以用来表示稀疏矩阵的结构，而双向的十字链表就是DancingLinks的基本结构。DancingLinks主要用于解决精确覆盖（ExactCover）问题。

　　先考虑双向链表，我们用L[]，R[]来记录双向链表一个节点的左右相邻的节点，如果想删除一个元素c，方法为：

　　L[R[c]] =R[c];

　　R[L[c]] =L[c];

　　如果想恢复这个元素c，方法为：

　　L[R[c]] =c;

　　R[L[c]] =c;

　　可以看出，双向链表的删除和恢复都是优美而简洁的。接着将链表扩展到二维，用U[]，D[]记录上下相邻的节点，C[]和O[]分别记录其所在的列和行，S[]记录每一列元素的个数，就构成了DancingLinks的基本结构。由于双向链表删除和恢复的简洁，很容易联想到在深搜上的使用。

二、精确覆盖问题

　　精确覆盖问题是一个NP完全问题。给出一个01矩阵，选出一些行，使得在这些行中，每一列有且仅有一个1。

　　对于这个问题，一般的搜索过程是：找到列中1的数目最少的那一列，选择这一列有1的行进行进一步的搜索。

　　朴素的算法无论搜到多少层，矩阵的大小都是不变的，但这个矩阵变得越来越稀疏，使得很多的查找都是无意义的，这时候DancingLinks便派上了用场。随着搜索的深入，DancingLinks里面的内容也是越来越少的，也就是说，搜索的层数越深，搜索的速度就越快。

　　DLX的解法也是由朴素的深搜得来的，只是用DancingLinks进行了优化。每一层搜索，选择元素最少的那一列，将这一列中有1的行全部删除。接下来枚举这些被删除的行（选择这行作为临时解），对于被删除的这一行，找出这一行中有1的列，将这些列中有1的行全部删除，这样就完成了选择一行并删除所有冲突的过程，然后进行下一层搜索，搜索之后进行恢复。如果到某一层DLX为空，说明已经找到答案。

实际中使用的时候要建立一个列的表头，方便深搜和元素插入的工作。0号节点是整个表的表头。

void init()
{
　　for(int i=0;i<=m;++i)
　　{
　　　　L[i] = i - 1;
　　　　R[i] = i + 1;
　　　　U[i] = i;
　　　　D[i] = i;
　　　　C[i] = i;
　　　　O[i] = 0;
　　　　S[i] = 0;
　　}
　　L[0] = m;
　　R[m] = 0;
　　nodeNumber = m + 1;
　　memset(H, 0, sizeof(H));
}

插入一个节点依赖于表头。H[]记录的是每一行第一个元素的位置。

void insert(int i, int j)
{
　　if(H[i])
　　{
　　　　L[nodeNumber] = L[H[i]];
　　　　R[nodeNumber] = H[i];
　　　　L[R[nodeNumber]] = nodeNumber;
　　　　R[L[nodeNumber]] = nodeNumber;
　　}
　　else
　　{
　　　　L[nodeNumber] = nodeNumber;
　　　　R[nodeNumber] = nodeNumber;
　　　　H[i] = nodeNumber;
　　}
　　U[nodeNumber] = U[j];
　　D[nodeNumber] = j;
　　U[D[nodeNumber]] = nodeNumber;
　　D[U[nodeNumber]] = nodeNumber;
　　C[nodeNumber] = j;
　　O[nodeNumber] = i;
　　++ S[j];
　　++ nodeNumber;
}

删除操作删除的是这一列和这一列中有1的行。

void remove(int c)
{
　　L[R[c]] = L[c];
　　R[L[c]] = R[c];
　　for(int i=D[c];i!=c;i=D[i])
　　{
　　　　for(int j=R[i];j!=i;j=R[j])
　　　　{
　　　　　　U[D[j]] = U[j];
　　　　　　D[U[j]] = D[j];
　　　　　　-- S[C[j]];
　　　　}
　　}
}

恢复操作和删除操作相反。

void resume(int c)
{
　　for(int i=U[c];i!=c;i=U[i])
　　{
　　　　for(int j=L[i];j!=i;j=L[j])
　　　　{
　　　　　　++ S[C[j]];
　　　　　　D[U[j]] = j;
　　　　　　U[D[j]] = j;
　　　　}
　　}
　　R[L[c]] = c;
　　L[R[c]] = c;
}

搜索过程按照上面的思路即可，判断表中是否为空只要看0号表头左右是否有列。

bool dfs(int k)
{
　　if(!R[0])
　　{
　　　　return true;
　　}
　　int count = INF, c;
　　for(int i=R[0];i;i=R[i])
　　{
　　　　if(S[i] < count)
　　　　{
　　　　　　count = S[i];
　　　　　　c = i;
　　　　　　if(1 == count)
　　　　　　{
　　　　　　　　break;
　　　　　　}
　　　　}
　　}
　　remove(c);
　　for(int i=D[c];i!=c;i=D[i])
　　{
　　　　for(int j=R[i];j!=i;j=R[j])
　　　　{
　　　　　　remove(C[j]);
　　　　}
　　　　if(dfs(k+1))
　　　　{
　　　　　　return true;
　　　　}
　　　　for(int j=L[i];j!=i;j=L[j])
　　　　{
　　　　　　resume(C[j]);
　　　　}
　　}
　　resume(c);
　　return false;
}

　　精确覆盖问题本身比较抽象，一般不会出现裸的情况。但精确覆盖问题有实际的意义，行是提供的选择的所有的可能性，列是限制与约束条件，只要能将其它问题转换为这种形式，就可以套用DLX解决精确覆盖问题的模式了。

例：POJ3740 Easy Finding

裸的精确覆盖

代码：http://blog.csdn.net/cyberzhg/article/details/7750412

三、数独

　　数独可以说是转化为精确覆盖问题的最经典的例子了。行作为选择的可能性，9×9数独一共81个方格，每个方格有9中填法，所以矩阵一共729行。每一行、每一列、每一个3×3方格数字不能重复，每一个方格必须填一个数字，所以矩阵一共(9+9+9)×9+81列。为了构造矩阵，如果当前位置的数字已经给出，则把对应行的相应位置置1即可，如果数字没给出，就把1~9所有数字加入。

例：

9×9的数独：

POJ2676 Sudoku

代码：http://blog.csdn.net/cyberzhg/article/details/7750426

POJ3074 Sudoku

代码：http://blog.csdn.net/cyberzhg/article/details/7750432

16×16的数独：

POJ3076 Sudoku

代码：http://blog.csdn.net/cyberzhg/article/details/7750434