“It's amazingly useful for solving such problems, for enumerating all solutions, and it is fast and completely general.”
Dancing links
用双向链表的可逆操作加速精确覆盖类回溯搜索
Knuth 介绍两个加速组合谜题深度优先搜索的技巧:一是用双向链表上可逆的局部操作实现搜索中的每一步假设,使数据随搜索增量变化;二是为每块拼图增加一个幽灵格,使每块只用一次与每格只盖一次的规则地位相同,从而归结为 0-1 整数规划的抽象形式。他还报告了在 19 块 hexiamond 铺六边形和最多 18 皇后问题上的优异性能。
HN 上的人常把它当作写得漂亮、好读的经典算法论文来推荐,用它解数独等精确覆盖问题,并称它展示了链表这种简单数据结构的威力。
HN 书评
推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及“Lots of fun and is a weekender, but you can expand it to solve anything from sudoku to all kinds of tiling problems.”
“very well written and a somewhat easy read”
“Seriously, study the algorithm before hating on it.”
“Donald Knuth's Dancing Links paper is a beautiful exploration of the power of linked lists.”
“He presented an earlier version of the algorithm in this legendary article”
看全部 12 条 →
“For anyone interested in solving sudokus, I recommend reading Knuth's Dancing Links paper [1]”
“I suggest implementing your own version of these two interesting, satisfying algorithms”
“Real programmers implement Knuth's dancing links and use it to solve a way larger class of problems.”
“Dancing Links (Knuth's paper: Dancing links )”
“Here's the paper describing the algorithm: Dancing links”
“FWIW, "Dancing Links" is a wonderful technique that would be worse than pointless in an immutable language.”
- Dancing links, by Knuth ↗sanj · 2009-05-29 · 2 分
- Knuth's Dancing Links Algorithm ↗mallin · 2013-08-17 · 2 分
- Don Knuth: Dancing Links ↗signa11 · 2018-12-13 · 3 分
- Dancing links – Donald Knuth (2000) [pdf] ↗OskarS · 2021-07-06 · 1 分