舞蹈链

维基百科,自由的百科全书
跳转至: 导航搜索
The Dancing Links algorithm solving a polycube puzzle

计算机科学 中, Dancing Links ,舞蹈链, 也叫 DLX, 是由 Donald Knuth 提出的技术,目的是快速实现他的 Algorithm X.[1] Algorithm X 是一种递归算法,时间复杂度不确定, 深度优先, 通过回溯寻找完全覆盖问题所有可能的解。有一些著名的完全覆盖问题,包括铺砖块,八皇后问题,数独问题。

名字来自于这个算法的工作方式,算法中的迭代让链接与同伴链接"跳舞",很像“精心编排的舞蹈”。 Knuth 归功于 Hiroshi Hitotsumatsu 与 Kōhei Noshita 在1979的研究 ,[2] 但是Knuth的论文让舞蹈链流行。

算法实现[编辑]

文章的剩余部分讨论这种算法在Algorithm X中的应用,强烈建议读者先阅读 Algorithm X

主要思想[编辑]

舞蹈链的主要思想来自于 双向链表

x.left.right ← x.right;
x.right.left ← x.left;

以上代码会从链表中移除x元素

x.left.right ← x;
x.right.left ← x;

以上代码会恢复x元素在链表中的位置(如果x的左侧元素和右侧元素没有变的话)。不管链表中有多少个元素,就算只有一个,算法也可以工作。

Knuth 发现用朴素算法实现Algorithm X会花费大量的时间来搜索1。当要选择一列的时候,要搜索整个矩阵来找到1。当选择一行的时候,需要在整列中搜索1。为了把搜索时间从 complexity O(n) 降到 O(1), Knuth 使用了一个 稀疏矩阵 ,只存放所有1 的位置。

无论何时,矩阵中的每个节点都会与左边和右边的节点(原始矩阵中的1的位置)、上面和下面(原始矩阵中同一列的1),以及列头连接。每一行和每一列都会形成一个双向链表。

链表头[编辑]

每一列都会有特殊的,叫做“列头”的节点,作为列表中的一部分。列头形成了特殊的一行,(“控制行”)包括了原始矩阵中还存在的每一列。

最后,每一列的头会记录这一列中节点的个数,我们可以用这些信息来定位节点最少的一列,只花费complexity O(n) 的时间复杂度。 (而不是O(n×m)),这里的n指的是列的个数,m指的是行的个数。选择节点最少的一列来进行搜索在一些情况下可以提高性能,但不是每个问题中都需要这么做。

搜索[编辑]

在 Algorithm X中,行与列是按照规则生成的,存储着原始矩阵。每次移除一列以及那列中的一行。如果选中的列没有包括任何行,当前的矩阵是无解的,必须回溯。当移除元素时,每一列中与那一行有交叉点的(原始矩阵中的1)都会被移除。列被移除了,因为他们已经被填满,行被移除是因为他们与指定的列有冲突。要移除某一列,要先移除那列的头,接着,遍历所有与这一列有交集的行,把那行与其他行的交点都去掉(这样阻止了这些列与当前列的冲突)。对包含1的列重复这样的列移除操作。这样的做法保证每个节点只被移除一次,并且按照顺序,这样就可以正确地回溯了。如果代入过程的矩阵没有任何的行,那么这已经被填满,选中的列就是一个解。

回溯[编辑]

要回溯,之前的操作需要反过来做一遍,使用刚才提到的第二个算法。Knuth 的论文给了一个清晰的这两个操作的关系以及移除、恢复操作的具体方式,并放宽了要求。

有可能出现的制约因素[编辑]

It is also possible to solve one-cover problems in which a particular constraint is optional, but can be satisfied no more than once. Dancing Links accommodates these with primary columns which must be filled and secondary columns which are optional. This alters the algorithm's solution test from a matrix having no columns to a matrix having no primary columns, but doesn't require any further changes. Knuth discusses optional constraints as applied to the n queens problem. The chessboard diagonals represent optional constraints, as some diagonals may not be occupied. If a diagonal is occupied, it can be occupied only once.

參考資料[编辑]

  1. ^ Knuth, Donald. Dancing links. Millenial Perspectives in Computer Science. P159. 2000, 187 [2006-07-11]. arXiv:cs/0011047. 
  2. ^ Hitotumatu, Hirosi; Noshita, Kohei. A Technique for Implementing Backtrack Algorithms and its Application. Information Processing Letters. 1979, 8 (4): 174–175. doi:10.1016/0020-0190(79)90016-4. 

外部連結[编辑]


Template:Donald Knuth navbox