Dancing Links(舞蹈链)

定义

Dancing Links(舞蹈链,DLX)是 Donald Knuth 于 2000 年论文中推广的技术:双向链表删除节点后,只要节点自身仍保留前驱后继指针,执行两条赋值即可把它原位恢复。回溯搜索中大量的"尝试-撤销"因此变得极其廉价,链表节点反复摘下挂回,如舞蹈一般。

原理

Knuth 将其用于精确覆盖问题(Exact Cover)的 Algorithm X:把 0-1 矩阵表示为纵横皆为循环双向链表的稀疏网格,每列有列头。搜索时选择元素最少的列,枚举该列的每一行,"覆盖"相关行列(摘链),递归求解,失败则按相反顺序恢复(挂链)。摘除与恢复均为指针操作,无需复制任何状态。

应用

数独求解是最著名的应用——数独可规约为 729 行 324 列的精确覆盖问题,DLX 求解极快;拼板问题(Pentomino)、N 皇后、排课表等组合搜索也常用 DLX。

优缺点

优点是回溯零拷贝、稀疏矩阵表示紧凑、剪枝(最少候选列)自然;缺点是指针网格实现繁琐、缓存不友好,且仅适合能建模为精确覆盖的问题。