简单易懂的Dancing links讲解（1）

解决重复覆盖问题

问题描述：

给定一个n*m的矩阵，有些位置为1，有些位置为0。如果G[i][j]==1则说明i行可以覆盖j列。

Problem：

1）选定最少的行，使得每列有且仅有一个1.

2）选定最少的行，使得每列至少一个1.

DLX原理：

这类属于NP问题的问题，可以使用搜索解决。但是普通的搜索必超时无疑。因此我们要设法加优化来加快速度。

Dancing Links从数据结构方面对此类搜索进行了优化，通过仅保留矩阵中有用的部分提高了搜索速度。DLX的存储结构采用循环十字链表，在搜索过程中不断将不需要的部分切除，随着迭代深度的增加，矩阵迅速变得稀疏。

甚至一些你想不到的优化，DLX都替你想好了。

对于