DancingLinks精确覆盖问题.docVIP

【转】DancingLinks精确覆盖问题 阅读31次?2013/10/9 16:27:30 原文链接：/works/dlxcn/　　（只转载过来一部分，全文请看原文，感觉讲得很好~）正文??? 精确覆盖问题??? 解决精确覆盖问题??? 舞蹈步骤??? 效率分析??? 应用于六形组??? 一个失败的试验??? 应用于四形条??? 应用于皇后问题??? 结语??? 致谢??? 历史注记??? 程序正文 我写这篇论文的目的，是觉得这个简单的程序技巧理应得到广泛认可。假设x指向双向链的一个节点；L[x]和R[x]分别表示x的前驱节点和后继节点。每个程序员都知道如下操作： L[R[x]] ← L[x], R[L[x]] ← R[x] （1） 是将x从链表删除的操作；但是只有少数程序员意识到如下操作： L[R[x]] ← x, R[L[x]] ← x （2） 是把x重新链接到双向链中。当然，指出这种操作以后，这个结果是显然的。但是，当我真正认识到操作（2）的作用以后，我突然感到了定义“啊哈”这个词语时候的感觉，因为，L[x]和 R[x]的值在x从链表中删除以后早已没有了它原来的语义。确实，一个精心设计的程序在x被删除后会通过把L[x],R[x]赋值为x 或者赋值为空值（null）来清理掉这些不用的数据结构。而让一个链外的对象指向链本身有时具有潜在的危险性。例如，指针就可以干扰垃圾回收机制的运作。那么是什么关于操作（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行