c - D.Knuth 的舞蹈链接算法的术语解释

Question

我从 D.Knuth 的网站下载了 DLX 算法。在 D.Knuth 概述问题的第一部分中，将列分隔为“主要”列和其他列。这些“主要”列是哪些？提前致谢。

Answer 1

这是对 Exact Cover 的轻微概括。正如相关维基百科页面所指出的那样，这种概括区分了“主列”，其规则与基本精确封面（“完全一个”）中的规则相同，以及“次要列”，“最多一”。这种概括的原因是它可以由 Dancing Links 直接有效地处理，而将其转换为等效的正常精确覆盖问题则效率较低。

Knuths论文中有更多关于 Dancing Links 的详细信息。