DancingLink 舞蹈链

问题

集合s=[x1,x2,…,xm]s = [x_{1}, x_{2}, \dots , x_{m}]拥有mm个元素，集合t=[s1,s2,…,sn]t = [ s_{1},s_{2}, \dots ,s_{n} ]拥有nn个元素，其中任意sis_{i}是集合ss的一个子集，sis_{i}包含ss中元素的数量为nin_{i}（1≤i≤n,0≤ni≤m1 \le i \le n, 0 \le n_{i} \le m）。

集合pp是tt的一个子集，且pp中的子集所包含的ss的元素可以覆盖集合ss。设集合qq是pp中所有元素所包含的ss中元素组成的集合。例如

s=[1,2,3,4,5,6,7,8,9]t=[s1,s2,s3,s4,s5]p=[s2,s4,s5]q=[2,3,4,5,7,8,9]\begin{matrix} s & = & [1, 2, 3, 4, 5, 6, 7, 8, 9] \\ t & = & [ s_1, s_2, s_3, s_4, s_5 ] \\ p & = & [ s_2, s_4, s_5 ] \\ q & = & [ 2, 3, 4, 5, 7, 8, 9 ] \end{matrix}

其中

s1=[1,2,3]s2=[2,3,4,5]s3=[6]s4=[7,8]s5=[8,9]\begin{matrix} s_1 & = & [1, 2, 3] \\ s_2 & = & [2, 3, 4, 5] \\ s_3 & = & [6] \\ s_4 & = & [7, 8] \\ s_5 & = & [8, 9] \\ \end{matrix}

重复覆盖：对于∀x∈s\forall x \in s，存在至少一个∃si∈p\exists s_{i} \in p使得x∈six \in s_{i}。例如集合s=[0,1,2,3]s = [ 0,1,2,3 ]，子集s1=[0,1],s2=[1,2],s3=[1,3]s_{1} = [ 0,1 ], s_{2} = [ 1,2 ], s_{3} = [ 1,3 ]组成p=[s1,s2,s3]p = [ s_{1},s_{2},s_{3} ]，称这样的pp是ss的重复覆盖。显然pp允许两个si⋂sj≠∅s_{i} \bigcap s_{j} \ne \varnothing。

精确覆盖：对于∀x∈s\forall x \in s，存在且只存在一个∃si∈p\exists s_{i} \in p使得x∈six \in s_{i}。例如集合s=[0,1,2,3]s = [ 0,1,2,3 ]，子集s1=[0,1],s2=[1,2],s3=[2,3]s_{1} = [ 0,1 ], s_{2} = [ 1,2 ], s_{3} = [ 2,3 ]组成p=[s1,s2]p = [ s_{1},s_{2} ]，称这样的pp是ss的精确覆盖。显然pp必然满足∀si,sj∈p,si⋂sj=∅,i≠j\forall s_{i}, s_{j} \in p, s_{i} \bigcap s_{j} = \varnothing, i \ne j。

求集合ss和子集集合t=[s1,s2,…,sn]t = [s_{1}, s_{2}, \dots, s_{n}]的重复覆盖和精确覆盖。

重复覆盖

设初始时重复覆盖p=∅p = \varnothing，pp的所有子集中的元素所组成的集合为q=∅q = \varnothing。对于∀x∈s\forall x \in s，若x∉qx \notin q，则在tt中寻找sis_{i}满足x∈six \in s_{i}，将该子集加入重复覆盖中p=[si]p = [ s_{i} ]，将所有∀y∈si\forall y \in s_{i}都加入qq。每个子集只能加入pp中一次，不能重复加入。当然也可以用染色来标记所有子集t=[s1,s2,…,sn]t = [ s_{1}, s_{2}, \dots ,s_{n} ]中已经加入pp的那些元素，防止重复。

遍历完成后pp即为重复覆盖。求重复覆盖的时间复杂度为O(n×m)O(n \times m)。

精确覆盖

设初始时精确覆盖p=∅p = \varnothing，pp的所有子集中的元素所组成的集合为q=∅q = \varnothing。

对于∀x∈s\forall x \in s，每个包含xx的子集都可能是pp的一员，我们用递归的方式寻找所有可能。利用pp中任意两子集的交集为空的特性，若x∈six \in s_{i}且si∈ps_{i} \in p，那么只要sj⋂si≠∅s_{j} \bigcap s_{i} \ne \varnothing，那么必然sj∉ps_{j} \notin p。

初始时将tt中的所有子集标记为白色（未被使用过）。遍历ss的所有元素∀x∈s\forall x \in s，进行以下步骤：

若x∉qx \notin q，这时有kk个候选子集[si,sj,… ][ s_{i}, s_{j}, \dots ]（非红色，即未被使用过），它们都包含xx。遍历这kk个候选子集，假定选择sis_{i}加入pp，将所有∀y∈si\forall y \in s_{i}加入qq。然后将tt中所有包含sis_{i}中元素的其他子集染红（标记为已被使用）；

重复上述过程只有两种结果：

(1)(1) 所有xx都已经加入qq，这时的pp即为精确覆盖；

(2)(2) 所有xx还没都加入qq，这时所有的子集t=[s1,s2,…,sn]t = [s_{1}, s_{2}, \dots ,s_{n}]都已经被染红。说明上次在候选子集中做出的选择是错的。

我们需要记录每次选择时染红了哪些子集，以及当时遍历到的元素xx。将sis_{i}这次选择回退，把当时染红的子集重新染回白色，然后选择下一个候选者sjs_{j}，再重复上述过程，指导找到精确覆盖。该过程是递归的。

下面演示舞蹈链算法：

s=[1,2,3,4,5,6,7]t=[s1,s2,s3,s4,s5,s6]s1=[1,3,5,6]s2=[1,4,7]s3=[2,6,7]s4=[2,3,6]s5=[4,5,7]s6=[5]\begin{matrix} s & = & [1, 2, 3, 4, 5, 6, 7] \\ t & = & [ s_1, s_2, s_3, s_4, s_5, s_6 ] \\ s_{1} & = & [1, 3, 5, 6] \\ s_{2} & = & [1, 4, 7] \\ s_{3} & = & [2, 6, 7] \\ s_{4} & = & [2, 3, 6] \\ s_{5} & = & [4, 5, 7] \\ s_{6} & = & [5] \end{matrix}

其中n=6,m=7n = 6, m = 7。

用行来表示子集，列来表示集合中的元素，可得nn行mm列矩阵：

舞蹈链算法用十字链表这种特别的数据结构将所有元素串联起来，坐标为[i,j][i, j]的节点下标是i×m+ji \times m + j，表示j∈s,j∈sij \in s, j \in s_{i}。沿着十字链表的行可以遍历子集sis_{i}的所有元素，沿着十字链表的列可以遍历所有包含jj的子集。

(1)(1) 对于上图中的示例，元素x=1x = 1的候选子集有s1,s2s_{1}, s_{2}，假定选择s1s_{1}，可得p=[s1],q=[1,3,5,6]p = [s_{1}], q = [1, 3, 5, 6]，然后将所有包含qq中元素的子集染红（s1,s2,s3,s4,s5,s6s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, s_{6}）；

(2)(2) 接着考虑元素x=2x = 2，其候选子集有s3,s4s_{3}, s_{4}，但它们都被染红了无法使用，这时不存在一个可用的子集，说明上一轮选择错误。不选择上一轮的s1s_{1}，将s1,s2,s3,s4,s5,s6s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, s_{6}染回白色，假定选择s2s_{2}，可得p=[s2],q=[1,4,7]p = [s_{2}], q = [1, 4, 7]，染红s1,s2,s3,s5s_{1}, s_{2}, s_{3}, s_{5}；

(3)(3) 再次考虑元素x=2x = 2，其候选子集有s4s_{4}（s3s_{3}已被染红），假定选择s3s_{3}，可得p=[s2,s4],q=[1,2,3,4,6,7]p = [s_{2}, s_{4}], q = [1, 2, 3, 4, 6, 7]，染红s1,s3,s4s_{1}, s_{3}, s_{4}（s1,s3s_{1}, s_{3}上一轮已被染红）；

(4)(4) 元素3,4∈q3, 4 \in q，因此可以直接跳过；

(5)(5) 考虑元素x=5x = 5，其候选子集有s6s_{6}（s5s_{5}已被染红），假定选择s6s_{6}，可得p=[s2,s4，s6],q=[1,2,3,4,5,6,7]p = [s_{2}, s_{4}， s_{6}], q = [1, 2, 3, 4, 5, 6, 7]，染红s5,s6s_{5}, s_{6}（s5s_{5}之前已被染红）；

(6)(6) 元素6,7∈q6, 7 \in q，可以直接跳过。至此s=qs = q，所有元素都被覆盖到，并且p=[s2,s4,s6]p = [s_{2}, s_{4}, s_{6}]中任意两子集的交集为空，算法结束。

其实十字链表并不需要“染红”这个操作来标记一个子集是否可以使用，而是用添加、删除来操作链表上的节点。例如元素x=1x = 1选择子集s2=[1,4,7]s_{2} = [1, 4, 7]时，将节点11从头节点一行中删除，将包含x=1x = 1的子集[s1,s2][s_{1}, s_{2}]（包括s2s_{2}自己）的元素也从所在的列中删除。如图所示：

仔细观察可知，删除之后仍然能够判定s1,s2s_{1}, s_{2}包含元素11（[1,8,15][1, 8, 15]拥有列关系），且可知s1=[1,3,5,6],s2=[1,4,7]s_{1} = [1, 3, 5, 6], s_{2} = [1, 4, 7]（[8,10,12,13][8, 10, 12, 13]，[15,18,21][15, 18, 21]拥有行关系）。这些遗留的列表指针可以恢复错误选择。对于子集s2=[1,4,7]s_{2} = [1, 4, 7]上的所有元素进行相同的链表操作，等价于将s1,s2,s3,s5s_{1}, s_{2}, s_{3}, s_{5}染红：

若尝试所有子集组合后仍无法找出精确覆盖，则说明该条件下不存在精确覆盖。舞蹈链算法的时间复杂度与递归的时间复杂度一样是O(nm)O(n^m)。

源码

DancingLink.h

DancingLink.cpp

测试

DancingLinkTest.cpp

PreviousAStarSearch A*搜索NextChapter-4 DataStructure 第4章 数据结构

Last updated