初次学习舞蹈链Dancing Links

介绍几个讲的比较好的博客：
这篇博客容易理解，可以先看：
http://www.cnblogs.com/grenet/p/3145800.html
这篇博客阐述的也好，而且有实例分析（也是转载自此文）：
https://blog.****.net/WhereIsHeroFrom/article/details/79220897?utm_source=copy

Dancing Links正是十字交叉双向循环链表。
一、十字交叉双向循环链表
这种链表结构的每个结点有两类数据，分别为指针域和数据域。指针域为left、right、up、down，分别指向左、右、上、下四个其它结点；数据域则存储一些信息，比如这个结点对应于原始矩阵的行编号rowIdx，列编号colIdx等等。
原始矩阵中值为“1”的位置对应了一个Dancing Links结点，“0”的位置不是我们需要关心的。
那么接下来我们来看下，如何将一个矩阵转变为一个十字交叉双向循环链表。我们把Dancing Links结点分成以下四类：总表头head、列首结点col[]、行首结点row[]、元素结点node。
1) 总表头head：将列首结点col[]在水平方向串联起来，head->right指向矩阵的第一列的列首结点，head->left指向矩阵的最后一列的列首结点。特别的，当这个矩阵为空矩阵，也就是没有任何列时，head->right和head->left指向head本身，这也正是X算法的终止条件。
2) 列首结点col[]：令初始矩阵的列数为colCount，那么col[i]->right指向col[i+1]，特殊的，col[colCount-1]->right指向head；同理，col[0]->left指向head，其它的col[i]->left指向col[i-1]。col[i]->down和col[i]->up分别指向第i列的第一个“1”和最后一个“1”对应的结点，当col[i]的up和down都指向本身说明这列全是0；
3) 行首结点row[]：令初始矩阵的行数为rowCount，那么row[i]->up和row[i]->down都是无用指针，直接指向自己即可；row[i]->right和row[i]->left分别指向第i行的第一个“1”和最后一个“1”对应的结点。
4) 元素结点node：矩阵中“1”对应的结点，up、down指向其它node或列首结点；left、right指向其它node或行首结点。
如图三-5-1表示了之前的那个矩阵的十字交叉双向循环链表的数据结构表示。所有箭头的左右边界循环相连（上下边界亦循环相连）。每个元素结点代表了原矩阵中的那个“1”，即图中的蓝色方块，其中的数字代表对应内存池中的编号。初始化时，所有的行首结点的左右指针和列首结点的上下指针都指向自己，然后对矩阵进行行、列分别递增的顺序进行读取，读到“1”就执行结点插入操作，这正对应了图中蓝色结点的递增序。别以为这是飞行棋…
初次学习舞蹈链Dancing Links

二、额外结点的意义
我们发现，图三-5-1中，除了蓝色结点，其它三种结点都是额外的，那么为什么要引入额外结点呢？
列首结点、行首结点都是存在既有数组中的，所以进行插入操作的时候可以达到O(1)，试想如果只有列首结点没有行首结点，那么插入一个处于(r, c)位置的结点时，c可以定位到列首结点col[c]，在进行对应行的插入时只能遍历竖向链表，插入的时间复杂度就变成O®了；同样，如果只有行首结点没有列首结点，那么插入复杂度就是O©的。
列首结点还有一个作用是区分不存在的列和全“0”的列。如果列c在搜索过程中被删除，那么列c的列首结点不会出现在链表结构中；而一个全“0”的列c，列首结点会在链表结构中，并且它的上下指针都指向自己。
总表头head主要还是为了空矩阵而存在的，试想如果一个矩阵为空，那么势必它的所有列首结点都没有了，那用什么来表示空矩阵呢？引入总表头后，只要总表头的左右指针都指向自己，就代表这是一个空矩阵。

三、Dancing Links X算法的具体实现
1、结点定义DLXNode
四类结点都定义为DLXNode，并且除了left、right、up、down四个指针数据外，还需要一些额外信息记录：
1）对于总表头，不需要额外记录信息；
2）对于列首结点，需要记录列编号colIdx，该列的结点个数colSum；
3）对于行首结点，需要记录行编号rowIdx；
4）对于元素结点，需要记录行编号rowIdx，列首指针colhead；

/*
DLXNode
 left, right        十字交叉双向循环链表的左右指针
 up, down           十字交叉双向循环链表的上下指针
 <用于列首结点>
 colSum             列的结点总数
 colIdx             列的编号
  
 <用于行首结点/元素结点>
 colHead            指向列首结点的指针
 rowIdx             DLXNode结点在原矩阵中的行标号
*/
class DLXNode {
public:
     DLXNode *left, *right, *up, *down;
    union {
         struct {
              DLXNode *colHead;   
             int rowIdx;
         }node;
        struct {
             int colIdx;
             int colSum;
        }col;
    }data;
};

2、链表定义DLX
十字交叉双向循环链表对于整个搜索来说，只有一个对象，所以这里采用单例实现。因为结点个数可能很多，所以可以将结点内存放在堆上避免栈溢出，row和col分别代表行首和列首结点，dlx_pool则为元素结点的对象池。可以在构造函数中利用new生成这些动态结点，在析构函数中delete。

/*
DLX （单例）
 head               head 只有左右（left、right）两个指针有效，指向列首
 rowCount, colCount 本次样例矩阵的规模（行列数）
 row[]              行首结点列表
 col[]              列首结点列表
 
 dlx_pool           结点对象池（配合dlx_pool_idx取对象）
*/
class DLX {
	 DLXNode *head;             // 总表头
 	int rowCount, colCount;    // 本次样例矩阵的规模（行列数） 
	 DLXNode *row, *col;        // 行首结点列表 / 列首结点列表
 
	 DLXNode *dlx_pool;         // 结点对象池
	 int dlx_pool_idx;              // 结点对象池下标
};
 dlx_pool = new DLXNode[MAXR*MAXC];
 col = new DLXNode[MAXC+1];
 row = new DLXNode[MAXR];

3、初始化
1)设置本次问题的规模总行数rowCount，总列数colCount，结点对象池下标dlx_pool_idx置零；
2)初始化列首结点，将总表头head和col[i]在水平方向用left和right指针串联起来，col[i]的up和down指针指向自己，代表这列在矩阵中均为“0”；对于每个列首结点col[i]，将其列编号置为i，列结点总数colSum置零；
3)初始化行首结点，将行首结点row[i]的四个指针都指向自己，将其行编号rowIdx置为i，对应列首结点的指针置NULL；
4、结点插入
按行递增、列递增的方式枚举R×C的矩阵A，如果第r行第c列的值A[r][c] = 1，则插入一个(r, c)的结点：
1)取出结点对象池中的一个结点Node（注意需要返回指针或者引用）；
2)取列首结点col[c]，将它设置为Node的列首结点，并且将Node插入到col[c]和col[c]->up之间，将col[c]的结点总数colSum自增1；
3)取行首结点row[r]，将Node的行编号rowIdx设置为r，并且将Node插入到row[r]和row[r]->left之间；
5、删列
删除列c包含两步：
1)移除列首结点col[c]，这里的移除指只移除水平方向，竖直方向不作任何修改；
2)从列首结点col[c]往下枚举，将每个元素结点对应的行进行移除（即删行）；
6、删行
删除行r的操作只需要修改row[r]上所有元素结点的up和down指针，只移除竖直方向，水平方向不作任何修改；
7、开始跳舞
X算法的主体，具体步骤之前已经描述过，现直接给出深度优先搜索的实现如下：

bool DLX::dance(int depth) {
 	// 当前矩阵为空，说明找到一个可行解，算法终止 
 	if(isEmpty()) {
  		resultCount = depth;
 	 	return true;
	 }
 	DLXNode *minPtr = get_min_col();
	 // 删除minPtr指向的列 
	 cover(minPtr);
	 // minPtr为结点数最少的列，枚举这列上所有的行
	 for(DLXNode *p = minPtr->down; p != minPtr; p = p->down) {
 		 // 令r = p->getRowIdx()，行r放入当前解 
  		result[depth] = p->getRowIdx();
  		// 行r上的结点对应的列进行删除 
  		for(DLXNode *q = p->right; q != p; q = q->right) {
  			 cover(q->getColHead());
  		}
 		 // 进入搜索树的下一层 
  		if(dance(depth+1, maxDepth)) {
 		  	return true;
  		}
 		 // 行r上的结点对应的列进行恢复 
 		 for(DLXNode *q = p->left; q != p; q = q->left) {
 		  	uncover(q->getColHead());
	  	}
 	}
 	// 恢复minPtr指向的列
	 uncover(minPtr); 
	 return false;
}

上面是转载的博客里对Dancing Links算法的介绍

初次学习舞蹈链Dancing Links

相关推荐