Dancing Links X

1. 问题引入

给定一个 \(N\) 行 \(M\) 列的 \(01\) 矩阵 \(A\)（\(N,M\leq 500\)），选出若干行 \((T_1,T_2,\cdots,T_k)\)，使得 \(\forall j\in [1,m],\sum\limits_{i=1}^k A_{T_i,j}=1\)。

即对于矩阵的每一列 \(j\)，在你挑选的这些行中，有且仅有一行的第 \(j\) 个元素为 \(1\)。

暴力的话就是枚举每行是否选择，然后检查是否合法，总时间复杂度 \(O(nm\cdot2^n)\)，如果将每一行看做一个 \(m\) 位二进制数，也只可以优化到 \(O(n\cdot2^n)\)。所以需要一种巧妙的算法来解决这个问题。

2. X 算法

2.1 X 算法流程

X 算法的算法流程为：

1.枚举选择当前矩阵的每一行。

2.删除当前选择的行，删除当前选择的行中为 \(1\) 的列，删除被删除的列中含 \(1\) 的行，得到一个新矩阵。

3.当矩阵不为空，继续递归处理；否则若最后删除的行为全 \(1\) 行，则找到一种解；否则回溯。

假设这个矩阵为 \(A\)。

\(A=\begin{pmatrix} 0&0&1&0&1&1&0\\ 1&0&0&1&0&0&1\\ 0&1&1&0&0&1&0\\ 1&0&0&1&0&0&0\\ 0&1&0&0&0&0&1\\ 0&0&0&1&1&0&1\\ \end{pmatrix}\)

先选择第一行（红色的为被选择的行，蓝色为其他将被删除的元素）。

\(\begin{pmatrix} \color{red}0&\color{red}0&\color{red}1&\color{red}0&\color{red}1&\color{red}1&\color{red}0\\ 1&0&\color{blue}0&1&\color{blue}0&\color{blue}0&1\\ \color{blue}0&\color{blue}1&\color{blue}1&\color{blue}0&\color{blue}0&\color{blue}1&\color{blue}0\\ 1&0&\color{blue}0&1&\color{blue}0&\color{blue}0&0\\ 0&1&\color{blue}0&0&\color{blue}0&\color{blue}0&1\\ \color{blue}0&\color{blue}0&\color{blue}0&\color{blue}1&\color{blue}1&\color{blue}0&\color{blue}1\\ \end{pmatrix}\)

得到新矩阵，此时新矩阵的每一行分别对应原矩阵的第 \(2,4,5\) 行，每一列分别对应原矩阵的第 \(1,2,4,7\) 列。

\(\begin{pmatrix} 1&0&1&1\\ 1&0&1&0\\ 0&1&0&1\\ \end{pmatrix}\)

同样再选择第一行。

\(\begin{pmatrix} \color{red}1&\color{red}0&\color{red}1&\color{red}1\\ \color{blue}1&\color{blue}0&\color{blue}1&\color{blue}0\\ \color{blue}0&\color{blue}1&\color{blue}0&\color{blue}1\\ \end{pmatrix}\)

得到空矩阵 \(\begin{pmatrix} \end{pmatrix}\)，上一次删除的行不为全 \(1\) 行，进行回溯，尝试选择第二行。

\(\begin{pmatrix} \color{blue}1&\color{blue}0&\color{blue}1&\color{blue}1\\ \color{red}1&\color{red}0&\color{red}1&\color{red}0\\ \color{blue}0&1&\color{blue}0&1\\ \end{pmatrix}\)

得到矩阵 \(\begin{pmatrix}1&1\end{pmatrix}\)，显然将这一行选择后，将得到一组解，即选择原矩阵中的 \(1,4,5\) 行。

2.2 X 算法原理

每次删除时将当前选择的行删除无需解释，将当前选择的行中为 \(1\) 的列删除保证了每一列只会有一个 \(1\)，同时再将被删除的列中含 \(1\) 的行删除是因为这些行无法再被选择。

如果得到了一个空矩阵有两种情况，一种是行被删完，一种是列被删完，只有后者才表示出现了一种解，所以只有最后选择的是全 \(1\) 行，才证明列被删完。

但是发现并不容易实现，所以我们使用 Dancing Links ，即双向十字链表来维护这些操作。

3. Dancing Links

3.1 双向十字链表

双向十字链表顾名思义，即对于每一个元素都记录它的上下左右四个元素（\(l,r,u,d\)），同时记录它所在的行和列的编号（\(row,col\)）。

此外我们还需要有一个行首提示和列提示，行首提示即 \(fir_i\) ，记录第 \(i\) 行的第一个元素；列提示是我们虚拟出的 \(m+1\) 个节点，\(1\sim m\) 分别对应第 \(1\sim m\) 列，\(0\) 号节点没有右节点则表示这个 Dancing Links 为空。

3.2 DLX

DLX 的时间复杂度，仅与矩阵中 \(1\) 的个数有关，其理论复杂度大概在 \(O(c^n)\) 左右（\(n\) 表示 \(1\) 的个数），\(c\) 为某个很接近 \(1\) 的常数，所以时间复杂度十分玄学。因此在实现过程中，可能仅仅是循环的方向相反就会相差几倍的时间。所以在这里仅介绍主流写法。

3.2.1 remove 操作

\(remove (p)\) 指的是删除第 \(p\) 列及相关的行。

首先把 \(p\) 删掉，即把 \(l_p\) 的右节点设为 \(r_p\)，把 \(r_p\) 的左节点设成 \(l_p\)。

随后遍历第 \(p\) 列的每个元素，把每个元素这一行中的每个元素都删去，即把 \(u_j\) 的下节点设为 \(d_j\)， \(d_j\) 的上节点设为 \(u_j\)，同时修改每一列的元素个数。

inline void remove(int p)
{
	l[r[p]]=l[p],r[l[p]]=r[p];//删除 p
	for(register int i=d[p];i!=p;i=d[i])//遍历这一列
		for(register int j=r[i];j!=i;j=r[j])//遍历当前行
			u[d[j]]=u[j],d[u[j]]=d[j],--siz[col[j]];//删除这一个元素
	return ;
}

3.2.2 recover 操作

\(recover (p)\) 指的是还原第 \(p\) 列及相关的行。

首先把 \(p\) 还原，即把 \(l_p\) 的右节点、\(r_p\) 的左节点设成 \(p\)。

随后遍历第 \(p\) 列的每个元素，把每个元素这一行中的每个元素都还原，即把 \(u_j\) 的下节点、\(d_j\) 的上节点设为 \(j\)，同时修改每一列的元素个数。即所有操作顺序与 \(remove (p)\) 的操作顺序相反。

inline void recover(int p)
{
	for(register int i=u[p];i!=p;i=u[i])//遍历这一列
		for(register int j=l[i];j!=i;j=l[j])//遍历当前行
			u[d[j]]=d[u[j]]=j,++siz[col[j]];//还原这一个元素
	l[r[p]]=r[l[p]]=p;//还原 p
	return ;
}

3.2.3 build 操作

即初始化一个 Dancing Links，没什么特殊的。

inline void build(int n,int m)//n 行 m 列
{
	for(register int i=0;i<=m;++i)
		l[i]=i-1,r[i]=i+1,u[i]=d[i]=i;
	l[0]=m,r[m]=0,cnt=m;return ;
}

3.2.4 insert 操作

\(insert (i,j)\) 表示插入一个位于 \(i\) 行 \(j\) 列的元素。

将这个元素编号为 \(cnt\)，将它插入到 \(fir_i\) 与 \(r_{fir_i}\)，\(j\) 与 \(d_j\) 之间。

inline void insert(int i,int j)
{
	++cnt;
	row[cnt]=i,col[cnt]=j,siz[j]++;//记录行号，列号，修改这一列的元素个数
	u[cnt]=j,d[cnt]=d[j],u[d[j]]=cnt,d[j]=cnt;//插在 j 与 d[j] 之间
	if(!fir[i]) fir[i]=l[cnt]=r[cnt]=cnt;//如果此行仍为空，直接将 fir[i] 赋值为 cnt
	else l[cnt]=fir[i],r[cnt]=r[fir[i]],l[r[fir[i]]]=cnt,r[fir[i]]=cnt;//插在 fir[i] 与 r[fir[i]] 之间
	return ;
}

3.2.5 dance 操作

这便是我们实现 X 算法的步骤。

1.首先判断 \(r_0\) 是否为空，为空则表示找到一种可行解，直接结束。

2.选择元素最少的一列（优化，具有一定的启发性），将这一列删除，枚举这一列中每一行，这次选择为哪一行。

3.将选择的这一行中每一列删掉。

4.递归至下一层。回溯。

void dance(int dep)
{
	if(!r[0])//找到一种解
	{
		for(register int i=1;i<dep;++i) cout<<ans[i]<<' ';//输出答案
		exit(0);
	}
	int pos=r[0];
	for(register int i=r[0];i;i=r[i]) if(siz[i]<siz[pos]) pos=i;//找到元素最少的一列
	remove(pos);//将这一列删除
	for(register int i=d[pos];i!=pos;i=d[i])//枚举这一列中每一行
	{
		//选择第 i 行
		ans[dep]=row[i];
		for(register int j=r[i];j!=i;j=r[j]) remove(col[j]);//将这一行每一列删除
		dance(dep+1);//递归
		for(register int j=l[i];j!=i;j=l[j]) recover(col[j]);//还原
	}
	recover(pos);return ;//还原这一列
}

这样我们就解决了板题。

4. 舞蹈链的应用

4.1 精确覆盖问题

给定 \(n\) 个集合 \(S_i\) 以及一个集合 \(X\)，求满足以下条件的无序多元组 \((T_1,T_2,\cdots,T_m)\)：

1.\(\forall i,j\in [1,m],T_i\bigcap T_j=\varnothing (i \not= j)\)

2.\(\bigcup\limits_{i=1}^{m} T_i=X\)

3.\(\forall i\in [1,m],T_i\in\left\{S_1,S_2,\cdots,S_n\right\}\)

只需要将 \(S_i\) 中的元素离散化，然后构造一个矩阵使 \((i,{S_i}_j)\) 为 \(1\)，就转化成了板题的形式。

这就是 DLX 最基础的建模。即行表示决策，对应一个集合，表示选/不选；列表示状态，第 \(i\) 列对应着某个条件 \(P_i\)。

4.2 数独问题

要求你完成一个 \(16\times 16\) 的数独。

我们考虑如果我们往 \((r,c)\) 中填入 \(x\)，会对我们什么造成影响，第 \(r\) 行，第 \(c\) 列，第 \(b\) 宫不能再填入 \(x\)，同时 \((r,c)\) 格不能再填入数字。

所以对于表示 \((r,c)\) 中填入 \(x\) 这一行，有 \(4\) 列上为 \(1\)。我们发现宫并不是决策的参数，因为它可以被确定的 \(r,c\) 表示出来；

所以数独问题其实为最典型的精确覆盖问题。

4.3 重复覆盖问题

给定一个 \(N\) 行 \(M\) 列的 \(01\) 矩阵 \(A\)（\(N,M\leq 500\)），选出若干行 \((T_1,T_2,\cdots,T_k)\)，使得 \(\forall j\in [1,m],\sum\limits_{i=1}^k A_{T_i,j}\geq 1\)。

重复覆盖问题也就是说对于每一列我们可以选择若干个 \(1\)，那么我们在处理的时候，只需要删除与当前选择行相关的所有列。

但是这样矩阵的下降速度会变慢，所以要加上一个强剪枝，即启发式搜索中的估价函数。一般可以判断当前状态最优情况是不是已经比全局最优解劣，也就是最优性剪枝。或者也可以使用 IDA*进行迭代加深。

inline void remove(int p)
{
	//这里删除的时候，不要把 p 也给删掉，因为接下来还要遍历 p 所在的行
	for(register int i=d[p];i!=p;i=d[i])
        l[r[i]]=l[i],r[l[i]]=r[i],--siz[col[i]];
	return ;
}
inline void recover(int p)
{
	for(register int i=u[p];i!=p;i=u[i])
        l[r[i]]=r[l[i]]=i,++siz[col[i]];
	return ;
}
inline int h()
{
    int ans=0;
    for(register int i=1;i<=tot;++i) st[i]=0;//初始化
    for(register int i=r[0];i;i=r[i])//遍历每一列
    {
        if(st[i]) continue;
        ++ans,st[i]=1;//如果还未被选择
        for(register int j=d[i];j!=i;j=d[j])//最优情况下，所有与之相关的列的所有相关的行都可以被选择过
            for(register int k=r[j];k!=j;k=r[k])
                st[col[k]]=1;
    }
    return ans;
}
void dance(int dep)
{
	if(!r[0]){ANS=min(ANS,dep-1);return ;}//取最优解
	int pos=r[0];if(dep+h()>ANS) return ;//最优性剪枝
	for(register int i=r[0];i;i=r[i]) if(siz[i]<siz[pos]) pos=i;//选出元素最少的列。
	for(register int i=d[pos];i!=pos;i=d[i])//枚举选择哪一行
	{
        remove(i);//删除当前列
		for(register int j=r[i];j!=i;j=r[j]) remove(j);//删除其他相关列
		dance(dep+1);//递归下一层
		for(register int j=l[i];j!=i;j=l[j]) recover(j);//还原其他相关列
        recover(i);//还原当前列
	}
	return ;
}