Dancing Link X 求精确覆盖与重复覆盖入门
DLX算法入门文……主要说一下我对这个算法的理解。 问题描述 精确覆盖问题： 以矩阵模型介绍，给你一个矩阵，其每个格子的权值范围是 [0,1] ，让你选出若干行，使得选出的行的 1 覆盖了一行的所有格子，且不能有重叠。 重复覆盖问题： 与精确覆盖问题基本相同，但是所选的行集合中，同一列的 1 允许重叠。 这个问题当然不可能让你输出可行方案，输出的应该是行数最小的方案。 算法理解 精确覆盖和重复覆盖都是NP问题，通常的，我们只能通过搜索去解决它。事实上DLX算法也是基于搜索算法。这里放上我的学习博客，里面讲的非常详细，一般人写的博客已然不会超过他。 所以我写这个个人理解其实主要是给自己看的。 首先最容易的当然是 ( 2^{row} ) 的最简单的裸搜，这谁都想得到……而且复杂度很高…… 其实当我们选中一行时，对于这一行的每一个 1 元素，含有与选中行同一列的 1 元素的行自然是不能选的，与此同时对于选中行每一个 1 元素，它所在的列其实我们也已经不再需要去考虑它们，因此，我们可以把这些元素删除，…