DLX 学习笔记

· · 个人记录

DLX 用于解决的精确覆盖问题，比较适合稀疏矩阵。（精确覆盖问题：给定一个 01 矩阵，从里面挑选一些行，使得最终每列都恰好有一个 1）

一、X 算法

简而言之，X 算法就是搜索时删除掉冲突的行，以提高遍历的速度。

比如上面这个 4 \times 4 的矩阵，我们选择了第一行，那么第三行就选择不了了，所以我们直接删除相关的行和列。

二、DLX

DLX 就是 Dancing Links 优化的 X 算法。

Dancing link 是一种数据结构，底层上是一个双向十字链表。链表每个节点储存了四个指针，分别指向上下左右。这样就可以做到快速删除冲突的行。

DLX 的时间复杂度仍为指数级，但是底数接近 1，因此当矩阵 1 的个数在 10^3 至 10^4 级别时也能通过，再大就不好说了。