算法 Dancing Links X"/>
舞蹈链算法 Dancing Links X
简单易懂的Dancing links讲解（1）
解决重复覆盖问题
问题描述：
给定一个n*m的矩阵，有些位置为1，有些位置为0。如果G[i][j]==1则说明i行可以覆盖j列。
Problem：
1）选定最少的行，使得每列有且仅有一个1.
2）选定最少的行，使得每列至少一个1.
DLX原理：
这类属于NP问题的问题，可以使用搜索解决。但是普通的搜索必超时无疑。因此我们要设法加优化来加快速度。
Dancing Links从数据结构方面对此类搜索进行了优化，通过仅保留矩阵中有用的部分提高了搜索速度。DLX的存储结构采用循环十字链表，在搜索过程中不断将不需要的部分切除，随着迭代深度的增加，矩阵迅速变得稀疏。
甚至一些你想不到的优化，DLX都替你想好了。
对于
更多推荐
舞蹈链算法 Dancing Links X
发布评论