DancingLinks精确覆盖问题

【转】DancingLinks精确覆盖问题

阅读31次 2013/10/9 16:27:30

原文链接：http://sqybi.com/works/dlxcn/ （只转载过来一部分，全文请看原文，感觉讲得很好~） 正文

精确覆盖问题 解决精确覆盖问题 舞蹈步骤 效率分析 应用于六形组 一个失败的试验 应用于四形条 应用于皇后问题 结语 致谢 历史注记 程序 正文

我写这篇论文的目的，是觉得这个简单的程序技巧理应得到广泛认可。假设x指向双向链的一个节点；L[x]和R[x]分别表示x的前驱节点和后继节点。每个程序员都知道如下操作：

L[R[x]] ← L[x], R[L[x]] ← R[x]

是将x从链表删除的操作；但是只有少数程序员意识到如下操作：

L[R[x]] ← x, R[L[x]] ← x 是把x重新链接到双向链中。

当然，指出这种操作以后，这个结果是显然的。但是，当我真正认识到操作（2）的作用以后，我突然感到了定义“啊哈”这个词语时候的感觉，因为，L[x]和 R[x]的值在x从链表中删除以后早已没有了它原来的语义。确实，一个精心设计的程序在x被删除后会通过把L[x],R[x]赋值为x 或者赋值为空值（null）来清理掉这

（1）2）

（

些不用的数据结构。而让一个链外的对象指向链本身有时具有潜在的危险性。例如，指针就可以干扰垃圾回收机制的运作。

那么是什么关于操作（2）的研究促使我写一整篇论文来讨论这个问题呢？当x从链表删除以后；为什么还要把它放回链表中？嗯，我承认，数据结构的更新通常来 说是永久性的。但是非永久性的更新也时常发生。例如，在一个交互性的程序中，用户很可能想撤销他所做的一个或一系列操作，恢复到先前的状态。另一个典型的 应用是在回溯程序（backtrack programs） [16]里,回溯程序枚举约束集合里的所有解。回溯，也叫深度优先搜索（depth-first search），在之前的论文中曾经讨论到。

操作（2）的观点是Hitotumatu和Noshita [22]于1979年提出的。他们提出Dijkstra提出的著名的解决N皇后问题 [6，第72-82页]的算法在使用了这个技巧后，程序的速度比不使用几乎快了2倍。

Floyd关于回溯和非确定性算法 [11]之 间关联的优雅论述中包含详细的数据结构更新与恢复的算法（谁能够提供这句话的准确翻译？——译者）。通常来说，回溯程序可以被认为是一种搜索，所要做的就 是缩小这个任务需要搜索的范围，同时组织好用于控制搜索流程和决策的数据。对于多步的问题,解决问题的每一步操作，都将改变剩余需要解决的问题。

简单情况下，我们可以考虑维护一个栈，用来保存当前搜索树节点之前的所有相关状态信息，但是这个任务的拷贝动作需要耗时太多。因此，我们通常选用全局数据结构。这样无论搜索进行到何种程度，它都会保留相关状态信息，并且当搜索回溯的时候它都能恢复先前状态。

例如，Dijkstra解决n皇后问题的递归算法将当前状态保存在三个全局布尔（Boolean）数组中，他们分别表示棋盘上的列和2条对角 线；Hitotumatu和Noshita的程序中使用双向链表来记录所有列和对角线上的可能性。当Dijkstra算法暂时放置一个皇后在棋盘上的时 候，会把每个布尔数组里的一个数据从真改为假；回溯后又将这个数据改回真。Hitotumatu和Noshita使用（1）去删除一列，使用（2）去恢复 删除操作；这意味着他们可以不通过搜索便找到一个空列。程序通过这种方法记录下每个状态信息，这样替换和恢复节点使得N皇后问题的计算更加高效。

算法（2）的优雅之处就在于我们仅仅知道x的值就可以恢复（1）的操作。通常来说要恢复操作，需要我们记录下节点的左指针和它先前的值（请参阅 [11]或 [25]，268-284页）。但是在这个实例中，我们只需要知道x的值，而回溯程序在做通常的操作时恰恰又很容易得到节点的值。

我们可以把（1）、（2）这对操作应用于涉及到大量操作的复杂数据结构的双向链上。这个删除元素的操作可以随时进行逆操作，因此它可以用来决定哪些元素需 要被恢复（即用来恢复已经删除的元素——译者）。重建链表的恢复操作使得我们可以一直向后回溯到下一次向前递归为止。这个过程使得指针在数据结构内部被灵 活运用，仿佛设计精巧的舞蹈动作。因此，我很愿意把（1）、（2）的这个技巧叫做舞蹈链（Dancing Links）。

精确覆盖问题。阐明Dancing Links威力的一种方法就是考虑一个能大致描述如下的一般问题：给定一个由0和1组成的矩阵，是否能找到一个行的集合，使得集合中每一列都恰好包含一个1？例如，下面这个矩阵

就包含了这样一个集合（第1，4，5行）。我们把列想象成全集的一些元素，而行看作全集的一些子集；或者我们可以把行想象成全集的一些元素，而把列看作全 集的一些子集；那么这个问题就是要求寻找一批元素，它们与每个子集恰好有一个交点。不管怎么说，这都是一个很难的问题，众所周知，当每行恰包含3个1时， 这是个一个NP-完全问题 [13，第221页]。自然，作为首选的算法就是回溯了。

Dana Scott完成了第一个关于回溯算法的实验。1958年，当他作为Princeton University普林斯顿大学 [34]的 一名研究生时，在Hale F. Trotter的帮助下,他在IAS \机器上首次实现12片5格骨牌拼图问题（12片5格骨牌拼图问题要求把12片骨牌放入正方形棋盘，并且中间留有2x2的空格）的回溯解法。他的程序首次产 生了所摆放的可能性。例如，65种解中的一种如图1所示（5格骨牌是n格骨牌在n=5时的特例；见 [15]。Scott或许从Golomb的论文 [14]和Martin Gardner的一些深入报告 [12]中得到了灵感。）

图1 Scott的12片5格骨牌拼图问题

这个问题是精确覆盖问题的一个特例。我们想象一个有72列的矩阵，其中12列是12个骨牌，剩下60列是六十个非中心部分的格子，构造出所有可能的 行来代表在一块骨牌在棋盘上的放置方案；每行有一些?1?，用来标识被覆盖的格子，5个1标识一个骨牌放置的位置（恰有1568个这样的行）。依据 Golomb对骨牌命名的介绍 [15，第7页]，我们将最前面的12列命名为F I L P N T U V W X Y Z，并且我们可以用两个数字ij给矩阵中对应棋盘上第i行第j列格子的那一列命名。通过给出那些出现了?1?的列的名字，可以很方便地表示每一行。例如，图1就是与下面12行的对应的精确覆盖。

I 11 12 13 14 N 16 26 27 37 L 17 18 28 38 U 21 22 31 41 X 23 32 33 34 W 24 25 35 36 P 51 52 53 62 F 56 64 65 66 Z 57 58 67 76 T 61 71 72 73 V 68 78 86 87 Y 74 82 83 84

15 47 48 42 43 46 63 75 77 81 88 85

解决精确覆盖问题。对于接下来的非确定性算法，由于我们没有想到更好的名字，我们将称之为X算法，它能够找到由特定的01矩阵A定义的精确覆盖问题的所有解。X算法是实现试验——错误这一显而易见的方法的一段简单的语句（确实，一般来说，我想不到别的合理的方法来完成这个工作）。

如果A是空的，问题解决；成功终止。 否则，选择一个列c（确定的）。

选择一个行r，满足 A[r, c]=1 （不确定的）。 把r包含进部分解。

对于所有满足 A[r,j]=1 的j， 从矩阵A中删除第j列； 对于所有满足 A[i,j]=1 的i， 从矩阵A中删除第i行。

在不断减少的矩阵A上递归地重复上述算法。

对r不确定的选择意味着这个算法本质上把自身复制给许多独立的子算法；每个子算法继承了当前的矩阵A，但在考虑不同行r的同时对其进行了删减。如果 列c全部是0，那么就不存在子算法而且这个过程会不成功地终止。很自然地，所有的子算法搭建了一棵搜索树，其根部就是初始问题，并且第k层的每个子算法对 应k个选择的行。回溯就是前序遍历这棵树的过程，即“深度优先”。 这个程序中任意选择列c的体系规则都能找到所有解，但是有些规则运行起来比别的会好得多。例如，Scott [34]说他最初更倾向于先放第一张骨牌，然后再放第二张，依此类推；这就对应了在于之相符该精确覆盖问题中先选择F列，再选择I列，等等。但是他很快意识到这个方法将会变得无可救药的慢。有192种放置F的方法，对于每种又有34种放置I的方法。[24]中介绍的Monte Carlo计算法暗示了该方案的搜索树粗略估计会有2*1012个结点！相较之下，如果一开始选择11列（矩阵中对应棋盘上第1行第1列的那一列），并且大体上按照字典序选择第一个没有被覆盖的列，那么导出的搜索树仅有9,015,751个结点。一个更好的策略被Scott [34]采 用：他意识到X块本质上有3种不同的位置，即中心在23，24和33。更进一步，如果X在33处，我们可以假定P块没有“翻转”，这么一来它就只能取8个 方向中的4种。接着我们一次得到65种本质不同的解，那么全部解集有8*65=520种解，这些解通过旋转和对称很容易得到。X和P的这些约束引导出了3 个独立的问题，当按字典序选择列时,他们的搜索树分别：

有103,005个结点和19组解 (X在23处) 有106,232个结点和20组解 (X在24处)

有126,636个结点和26组解 (X在33处,P没有翻转)。

Golomb和Baurnert [16]建 议，在每个回溯的过程中，选择能够导出最少分支的子问题，任何时候这都是可以被有效完成的。在精确覆盖问题中，这意味着我们希望每步都选择在当前A中包含 1最少的列。幸运的是我们将看到dancing links技术让我们相当好地做到这一点；使用这个技术后，Scott的骨牌问题的搜索树将分别仅有：

10,421 个结点 (X在23处) 12,900 个结点 (X在24处)

14,045 个结点 (X在33处,P没有翻转)。

舞蹈步骤。一个实现X算法的好方法就是将矩阵A中的每个1用一个有5个域L[x]、R[x]、U[x]、D[x]、C[x]的数据对象（data object）x来表示。矩阵的每行都是一个经由域L和R(“左”和“右”)双向连接的环状链表；矩阵的每列是一个经由域U和D(“上”和“下”)双向连接的环状链表。每个列链表还包含一个特殊的数据对象，称作它的表头（list header）。

这些表头是一个称作列对象（column object）的大型对象的一部分。每个列对象y包含一个普通数据对 象的5个域L[y]、R[y]、U[y]、D[y]和C[y]，外加两个域S[y]（大小）和N[y]（名字）；这里“大小”是一个列中1的个数，而“名 字”则是用来标识输出答案的符号。每个数据对象的C域指向相应列头的列对象。 表头的L和R连接着所有需要被覆盖的列。这个环状链表也包含一个特殊的列对象称作“根”，h，它相当于所有活动表头的主人。而且它不需要U[h]、D[h]、C[h]、S[h]和N[h]这几个域。

举个例子，（3）中的0-1矩阵将用这些数据对象来表示，就像图2展示的那样，我们给这些列命名为A、B、C、D、E、F和G（这个图表在上下左右处“环绕扭曲”。C的连线没有画出，因为他们会把图形弄乱；每个C域指向每列最顶端的元素）。

图2 完全覆盖问题（3）的四方向连接表示法

我们寻找所有精确覆盖的不确定性算法现在可以定型为下面这个明析、确定的形式，即一个递归过程search(k)，它一开始被调用时k=0： 如果 R[h]=h ，打印当前的解（见下）并且返回。 否则选择一个列对象c（见下）。 覆盖列c（见下）。

对于每个r←D[c]，D[D[c]]，……，当 r!=c， 设置 Ok<-r；

对于每个j←R[r]，R[R[r]]，……，当 j!=r， 覆盖列j（见下）； search(k+1)；

设置 r←Ok 且 c←C[r]；

对于每个j←L[r]，L[L[r]]，……，当 j!=r， 取消列j的覆盖（见下）。 取消列c的覆盖（见下）并且返回。

输出当前解的操作很简单：我们连续输出包含O0、O1、……、Ok-1的行,这里包含数据对象O的行可以通过输出N[C[O]]、N[C[R[O]]]、N[C[R[R[O]]]]……来输出。

为了选择一个列对象c,我们可以简单地设置c<-R[h]；这是最左边没有覆盖的列。或者如果我们希望使分支因数达到最小，我们可以设置s<-无穷大，那么接下来： 对于每个j←R[h]，R[R[h]]，……，当 j!=h， 如果 S[j]

那么c就是包含1的序数最小的列(如果不用这种方法减少分支的话，S域就没什么用了)。

覆盖列c的操作则更加有趣：把c从表头删除并且从其他列链表中去除c链表的所有行。

设置 L[R[c]]←L[c] 且 R[L[c]]←R[c]。 对于每个i←D[c]，D[D[c]]，……，当 i!=c， 对于每个j←R[i]，R[R{i]]，……，当 j!=i， 设置 U[D[j]]←U[j]，D[U[j]]←D[j]， 并且设置 S[C[j]]←S[C[j]]-1。

操作（1），就是我在本文一开始提到的，在这里他被用来除去水平、竖直方向上的数据对象。

最后，我们到达了整个算法的尖端，即还原给定的列c的操作。这里就是链表舞蹈的过程：

对于每个i←U[c]，U[U[c]]，……，当 j!=i， 对于每个j←L[i]，L[L[i]]，……，当 j!=i， 设置 S[C[j]]←S[C[j]]+1，

并且设置 U[D[j]]←j，D[U[j]]←j。 设置 L[R[c]]←c 且 R[L[c]]←c。

注意到还原操作正好与覆盖操作执行的顺序相反，我们利用操作（2）来取消操作（1）。（其实没必要严格限制“后执行的先取消”，由于j可以以任何顺 序穿过第i行；但是从下往上取消对行的移除操作是非常重要的，因为我们是从上往下把这些行移除的。相似的，对于第r行从右往左取消列的移除操作也是十分重 要的，因为我们是从左往右覆盖的。）

图3 图2中第A列后面的链表被覆盖

考虑一下，例如，对图2表示的数据（3）执行search(0)会发生什么。通过从其他列移除A的行来将其覆盖；那么现在整个结构就成了图3的样子。注意现在D列出现了不对称的链接：上面的元素首先被删除，所以它仍然指向初始的邻居，但是另一个被删除的元素指向了列头。

继续search(0)，当r指向（A，D，G）这一行的A元素时，我们也覆盖D列和G列。图4展示了我们进入search(1)时的状态，这个数据结构代表削减后的矩阵

现在search(1)将覆盖B列，而且C列将没有“1”。因此search(2)将什么也找不到。接着search(1)会找不到解并返回，图4的状态会恢复。外部的过程，search(0)，将把图4变回图3，而且它会让r前进到（A，D）行的A元素处。

图4 图3中D列和G列后的链被覆盖

很快就能找到解，并输出

A D E F C B G

如果在选择c的时候无视S域，会输出

A D B G C E F

如果每步选择最短的列。（每行输出的第一项是已经完成分支的列的名字）在一些例子上试验过这个算法的读者应该会明白我为什么给这篇论文选这个标题。 效率分析。当算法X用Dancing Links实现时，让我们称之为DLX算法。DLX算法的运行时间本质上和它执行操作（1）来移除表中对象的次数是成比例的；这同时也是它执行操作（2）来还原对象的次数。我们把这个数量称作更新（updates） 的次数。如果每步选择最短的列，则在对（3）求解的的过程中共做了28次更新：第0层更新10次，第1层更新14次，第2层更新4次。如果我们忽略启发条 件S，这个算法就在第1层更新16次，在第2层更新7次，总计33次。但是在后者的更新明显快些，因为S[C[j]←S[C[j]]±1这样的语句可以忽

略；因此全部的运行时间会少些。当然，我们在给启发条件S的期望效果下一般结论前还需要对一些大规模的实例进行分析。

图5 Scott的12片5格骨牌拼图问题的搜索树