Dancing Links 的相关概念

Dancing Links： $Dancing~Links$ 是一种数据结构，专门能用来解决两种类型的题型，一种是精确覆盖问题，一种是重复覆盖问题。

由于精确覆盖问题和重复覆盖问题都是 $NP$ 完全问题，因此极端的时间复杂度都是 $O(2^n)$ 的时间复杂度，因此看上去 $n$ 的范围不能太大，但是实际上通过 $Dacing~Links$ 优化后 $n$ 的范围可以取到非常大，甚至可以取到 $10^4$ 的级别。但是能用 $Dancing~Links$ 优化的前提是这个矩阵必须是一个稀疏矩阵，也就是矩阵中 $1$ 的个数必须非常少，此时我们才能用 $Dancing~Links$ 来优化。

对于 $Dancing~Links$ 能解决的题，我们都需要先将题目转化成精确覆盖问题或重复覆盖问题，然后再用 $Dancing~Links$ 去做。

Dancing Links 的原理

这里以精确覆盖问题为模型进行原理讲解。

首先需要考虑一下如何存储整个矩阵，由于矩阵中 $1$ 的个数非常少，因此我们在存储的时候只需要存储 $1$，不再存储 $0$。

这里需要用到十字链表来存储所有的 $1$，十字链表其实就是每个节点会有四个指针，分别连向上、下、左、右四个方向上的节点，十字链表的指针是循环的，一个节点如果左边没有节点，那么它的左指针会指向右边第一个节点，其他三个指针也同理。

我们先对所有 $1$ 的位置建立一个节点，$0$ 的位置就不用建了。要建立十字链表也非常好建，十字链表中的第一行和第一列是哨兵（表头），我们先手动创建第一行的哨兵，如果一共有 $m$ 列，那么第一行在创建的时候还要加上第一列上的哨兵，因此一共会循环 $m + 1$ 次，然后再依次将每一行的节点加入到十字链表中。在插入每一行时，我们用两个指针 $hh, tt$ 表示该行的两个节点，然后我们将要插入的节点插入到 $hh$ 和 $tt$ 之间，最开始时该行没有节点，所以最开始将 $hh, tt$ 都初始化成当前要插入的这个点，插入之后我们再更新 $hh, tt$ 的位置让它俩相邻，以便让下一个点插入到它俩之间，这样以此类推将每一行的所有节点加入进来。

注意，我们在插入每一行的时候每次都是将当前行插入到第一行的下面，也就是哨兵的下面，因此其实是倒着插入的，最终除了表头之外第一行是第 $m$ 行，第二行是第 $m-1$ 行，以此类推。然后同理每一行中我们也都是将每个节点插入到头节点的下一个位置，因此行也是倒着插入的。由于行和列都是倒着的，并且我们记录的编号正确的，所以相当于整张图斜着翻转了一下，是不影响整个结构的

建完十字链表之后就需要考虑如何去搜索这个问题，可以发现我们所选择的行和顺序是没有关系的，因此我们 $dfs$ 的过程应该是每次从所有没被选择的行中任意的选择一行，选完之后递归下去处理，这样一定可以把所有方案都搜到。

以上就是 $Dancing~Links$ 的搜索框架，非常简单且暴力，接下来的重点就在于如何去进行剪枝。首先第一个剪枝，我们每次优先选择一个可选择方案最少的一列来看，如果某一列中只有 $1$ 个 $1$，显然这一行必须要选，那么我们就可以把这一行选上。因此我们可以每次选择 $1$ 的个数最少的列。假设 $1$ 的个数最少的列中有 $3$ 个 $1$，那么我们必然要从这 $3$ 行中选择一行出来，因此接下来我们只需要枚举一下选择这 $3$ 行中的哪一行，然后继续递归下去，这一步就是优化搜索顺序的剪枝。

根据以上的搜索顺序每次会有一列满足要求，也就是恰好有 $1$ 个 $1$，此时这一列我们就不需要再考虑了，因此我们就需要将这一列删掉。而当我们选择某一行时，不只要删掉当前我们考虑的这一列，因为该行中可能不止一个 $1$，因此我们要将该行中所有是 $1$ 的列全部删掉，这样才能保证在接下来的搜索中不会重复选择。这一步是将不可行的方案及时剪掉，是可行性剪枝。

注意，在可行性剪枝中删除所有是 $1$ 的列时，如果是从左到右删除的，那么在恢复现场的时候一定要从右到左去恢复，也就是要反着来，否则在个别的情况下可能会造成死循环。

到此我们考虑完了 $dfs$ 过程中需要进行的剪枝，然后我们需要考虑如何实现 $Dancing~Links$ 中删除某一列和恢复某一列的操作。这里在删除的时候有点取巧，我们在 $dfs$ 中选择 $1$ 的个数较少的列时是枚举第一行来选择的，因此我们在删除的时候只需要将第一行中对应这一列的节点删去即可，这样在枚举选择列的时候就不会枚举到已经有 $1$ 的列了。而在删掉这一列的同时我们还要去枚举这一列是 $1$ 的所有行，此时这一列已经有 $1$ 了，那么所有这一列有 $1$ 的行都不能再选了，因此我们还需要将这些行也都删掉，而在删除这些行的时候我们也不需要将整个行删去，只需要将这些行在列的意义上删去即可，因为我们选择的时候是先从第一行中确定我们的列，然后再在这一列中纵向去枚举所有的行，因此我们只需要在纵向意义上将这些行删掉即可，横向意义上不需要过多的处理，而保留横向意义的目的也是为了后面方便去恢复它。至于恢复操作则是和删除操作完全反着来即可。

精确覆盖问题： 给定一个 $01$ 矩阵，要求从中选出若干行，使得选出的所有行中每一列恰好包含一个 $1$。

解题思路：

上述 $Dancing~Links$ 的原理就是以精确覆盖问题为模型进行讲解的，这里直接按照上述思路求解即可，这里不再赘述。

精确覆盖问题要求图中 $1$ 的数量不能太多。

重复覆盖问题： 给定一个 $01$ 矩阵，要求从中选出若干行，使得选出的所有行中每一列至少包含一个 $1$

解题思路：

重复覆盖问题相比于精确覆盖问题就是把每一列对 $1$ 的限制去掉了，每一列可以包含多个 $1$，但是必须有 $1$。

由于重复覆盖问题中每一列可以存在多个 $1$，因此相比于精确覆盖问题的能承受的数据范围要更小一些，而重复覆盖问题不再要求 $1$ 的数量必须少，但是要求答案不能太大。

之所以要求答案不能太大，是因为重复覆盖问题的方案比精确覆盖更多，因此爆搜的时候一般需要基于 $IDA^\*$ 来进行优化，$IDA^\*$ 本质上就是一个启发式的迭代加深，而迭代加深算法要求搜索的层数不能太深，因此答案不能太大。

重复覆盖问题用 $Dancing~Links$ 存储节点的方式和精确覆盖问题是一样的，都是将所有的 $1$ 存入十字链表中。具体存储方式综上。

然后就是如何去进行搜索，重复覆盖问题的搜索框架和精确覆盖问题也是一样的，都是选择一个 $1$ 的数量最少的列，然后用当前列是 $1$ 的所有行来填这一列，再依次往下递归。

在搜索的过程中，我们如果选择了某一列，则这一列将会被填上 $1$，不用再考虑，所以需要将这一列删掉，同时还要将选择好的覆盖这一列的行中所有的 $1$ 对应的列都删掉。到此都和精确覆盖问题的思路一致，但是在精确覆盖问题中，由于每一列只能有一个 $1$，因此当我们在删除其他的列时，会将这些列中所有是 $1$ 的行都删去，这是因为这一列已经有 $1$ 了，别的在这一列有 $1$ 的行都不能选，但是在重复覆盖问题中，每一列是可以有多个 $1$ 的，因此在删除每一列时，我们不用将这一列是 $1$ 的所有行删去，而是可以保留下来继续选择。因此在重复覆盖问题中，我们删除每一列，只需要将这一列删去即可，不用将这一列中所有的行都删掉，相比于精确覆盖问题少了一层循环。

而因为重复覆盖问题比精确覆盖问题少了一层循环，剪枝的数量比较少，所以重复覆盖问题在搜索的时候就会比较慢，因此我们就需要给它加一些其他的优化。而这里就要用到 $IDA^\*$ 来进行优化。

$IDA^*$ 的核心就是需要一个估价函数，判断当前情况下最少还需要再走多少步。对应的重复覆盖问题中就是最少需要选多少行才能让每一列都有 $1$。

这就用到 $Dancing~Links$ 非常经典的一个估价函数，也比较直观，很容易想出来。我们从前往后遍历一下当前还没有被覆盖（未被删掉）的所有列，对于每一列，我们最终必须要覆盖掉它，也就是至少要选这一列中的任意一行，而我们这里直接将所有行都选上，但是在累加需要选择的行数时，只累加一行，最终我们一定能将所有列都覆盖掉，而且此时累加出的行数一定 $\leq$ 真实值。因此这个估价函数就成立了，并且实际应用中效果非常好。

以上就是重复覆盖问题的整体思路，相比于精确覆盖问题其实就是修改了一下删除函数和恢复函数，然后加上了一个新的优化，其余地方都是一样的。