企业🤖AI智能体构建引擎,智能编排和调试,一键部署,支持私有化部署方案 广告
<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Dancing Link - 舞蹈链 -------- #### 问题 集合$$ s = [x_{1}, x_{2}, \dots , x_{m}] $$拥有$$ m $$个成员,有$$ n $$个子集$$ t = [ s_{1},s_{2}, \dots ,s_{n} ] $$,其中子集$$ s_{i} $$拥有成员的数量为$$ n_{i} $$($$ 1 \le i \le n, 0 \le n_{i} \le m $$)。 在$$ t $$选择一些子集,组成集合$$ p = [ s_{1}, s_{2}, \dots ] $$,使$$ p $$中的子集所包含的成员可以覆盖集合$$ s $$。设$$ p $$中所有子集包含的成员组成的集合为$$ q $$(即对于$$ \forall x \in q $$,都存在$$ \exists s_{i} \in p $$使得$$ x \in s_{i} $$),则对于$$ \forall x \in s $$,都存在$$ \exists s_{i} \in p $$使得$$ x \in s_{i} $$。 重复覆盖:对于$$ \forall x \in s $$,存在至少一个$$ \exists s_{i} \in p $$使得$$ x \in s_{i} $$(多则不限)。例如集合$$ s = [ 0,1,2,3 ] $$,子集$$ s_{1} = [ 0,1 ], s_{2} = [ 1,2 ], s_{3} = [ 1,3 ] $$组成$$ p = [ s_{1},s_{2},s_{3} ] $$,称这样的$$ p $$是$$ s $$的重复覆盖。显然$$ p $$允许两个$$ s_{i} \bigcap s_{j} \ne \emptyset $$。 精确覆盖:对于$$ \forall x \in s $$,存在且只存在一个$$ \exists s_{i} \in p $$使得$$ x \in s_{i} $$。例如集合$$ s = [ 0,1,2,3 ] $$,子集$$ s_{1} = [ 0,1 ], s_{2} = [ 1,2 ], s_{3} = [ 2,3 ] $$组成$$ p = [ s_{1},s_{2} ] $$,称这样的$$ p $$是$$ s $$的精确覆盖。显然$$ p $$必然满足$$ \forall s_{i}, s_{j} \in p, s_{i} \bigcap s_{j} = \emptyset, i \ne j $$。 求集合$$ s $$和子集集合$$ t = [s_{1}, s_{2}, \dots, s_{n}] $$的重复覆盖和精确覆盖。 #### 重复覆盖 设初始时重复覆盖$$ p = \emptyset $$,$$ p $$的所有子集中的元素所组成的集合为$$ q = \emptyset $$。对于$$ \forall x \in s $$,若$$ x \notin q $$,则在$$ t $$中寻找$$ s_{i} $$满足$$ x \in s_{i} $$,将该子集加入重复覆盖中$$ p = [ s_{i} ] $$,将所有$$ \forall y \in s_{i} $$都加入$$ q $$。每个子集只能加入$$ p $$中一次,不能重复加入。当然也可以用染色来标记所有子集$$ t = [ s_{1}, s_{2}, \dots ,s_{n} ] $$中已经加入$$ p $$的那些,来防止重复加入。 遍历完成后$$ p $$即为重复覆盖。求重复覆盖的时间复杂度为$$ O(n \times m) $$。 #### 精确覆盖 设初始时精确覆盖$$ p = \emptyset $$,$$ p $$的所有子集中的元素所组成的集合为$$ q = \emptyset $$。 对于$$ \forall x \in s $$,每个包含$$ x $$的子集都可能是$$ p $$的一员,我们用一种类似递归的方式考虑所有可能。利用$$ p $$中任意两子集的交集为空的特性,若$$ x \in s_{i} $$且$$ s_{i} \in p $$,那么只要$$ s_{j} \bigcap s_{i} \ne \emptyset $$,那么必然$$ s_{j} \notin p $$。 初始时将$$ t $$中的所有子集标记为白色(未被使用过)。 $$ (1) $$ 遍历$$ \forall x \in s $$,若$$ x \notin q $$,这时我们有$$ k $$个候选子集$$ [ s_{i}, s_{j}, \dots ] $$,它们都包含$$ x $$。我们遍历这$$ k $$个候选子集,假定选择$$ s_{i} $$加入$$ p $$,即$$ p = [s_{i}] $$,将所有$$ \forall y \in s_{i} $$加入$$ q $$。然后将所有包含$$ s_{i} $$中任意元素的子集染红(已被使用); $$ (2) $$ 然后我们考虑第二个$$ x \in s $$,若$$ x \notin q $$,这时我们有$$ k $$个候选子集$$ [ s_{i}, s_{j}, \dots ] $$,它们不能是红色的(不能被使用过)。我们遍历这$$ k $$个候选子集,假定选择$$ s_{i} $$加入$$ p $$,将所有$$ \forall y \in s_{i} $$加入$$ q $$。然后将所有包含$$ s_{i} $$中任意元素的子集染红(已被使用)。若已经有$$ x \in q $$则直接跳过这个元素,继续遍历下一个; $$ \cdots $$ 重复上述过程,只有两种结果:$$ 1) $$所有$$ x $$都已经加入$$ q $$,这时的$$ p $$即为精确覆盖;$$ 2) $$所有$$ x $$还没都加入$$ q $$,这时所有的子集$$ t = [s_{1}, s_{2}, \dots ,s_{n}] $$都已经被染红。说明上次在候选子集中做出的选择是错的。 我们需要记录每次选择时染红了哪些子集,以及当时遍历到的元素$$ x $$。将$$ s_{i} $$这次选择回退,把当时染红的子集重新染回白色,然后选择下一个候选者$$ s_{j} $$。再重复上述过程。 下图中集合$$ s = [1, 2, 3, 4, 5, 6, 7] $$,子集分别是$$ 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] $$,$$ n = 6, m = 7 $$。用一行来表示一个子集,一列来表示集合中的一个元素,可得$$ n $$行$$ m $$列矩阵: ![DancingLink1.svg](../res/DancingLink1.svg) 舞蹈链算法用十字链表这种特别的数据结构将所有元素串联起来,坐标为$$ [i, j] $$的节点下标是$$ i \times m + j $$,表示$$ j \in s, j \in s_{i} $$。沿着十字链表的行可以遍历子集$$ s_{i} $$的所有元素,沿着十字链表的列可以遍历所有包含$$ j $$的子集。 ![DancingLink2.svg](../res/DancingLink2.svg) ![DancingLink3.svg](../res/DancingLink3.svg) $$ (1) $$ 对于上图中的示例,元素$$ x = 1 $$的候选子集有$$ s_{1}, s_{2} $$,假定选择$$ s_{1} $$,可得$$ p = [s_{1}], q = [1, 3, 5, 6] $$,然后将所有包含$$ q $$中元素的子集染红($$ s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, s_{6} $$); ![DancingLink4.svg](../res/DancingLink4.svg) $$ (2) $$ 接着考虑元素$$ x = 2 $$,其候选子集有$$ s_{3}, s_{4} $$,但它们都被染红了无法使用,这时不存在一个可用的子集,说明上一轮选择错误。不选择上一轮的$$ s_{1} $$,将$$ s_{1}, s_{2}, s_{3}, s_{4}, s_{5}, s_{6} $$染回白色,假定选择$$ s_{2} $$,可得$$ p = [s_{2}], q = [1, 4, 7] $$,染红$$ s_{1}, s_{2}, s_{3}, s_{5} $$; ![DancingLink5.svg](../res/DancingLink5.svg) $$ (3) $$ 再次考虑元素$$ x = 2 $$,其候选子集有$$ s_{4} $$($$ s_{3} $$已被染红),假定选择$$ s_{3} $$,可得$$ p = [s_{2}, s_{4}], q = [1, 2, 3, 4, 6, 7] $$,染红$$ s_{1}, s_{3}, s_{4} $$($$ s_{1}, s_{3} $$上一轮已被染红); $$ (4) $$ 元素$$ 3, 4 \in q $$,因此可以直接跳过; ![DancingLink6.svg](../res/DancingLink6.svg) $$ (5) $$ 考虑元素$$ x = 5 $$,其候选子集有$$ s_{6} $$($$ s_{5} $$已被染红),假定选择$$ s_{6} $$,可得$$ p = [s_{2}, s_{4}, s_{6}], q = [1, 2, 3, 4, 5, 6, 7] $$,染红$$ s_{5}, s_{6} $$($$ s_{5} $$之前已被染红); $$ (6) $$ 元素$$ 6, 7 \in q $$,可以直接跳过。至此$$ s = q $$,所有元素都被覆盖到,并且$$ p = [s_{2}, s_{4}, s_{6}] $$中任意两子集的交集为空,算法结束。 其实十字链表并不需要“染红”这个操作来标记一个子集是否可以使用,而是用添加、删除来操作链表上的节点。例如元素$$ x = 1 $$选择子集$$ s_{2} = [1, 4, 7] $$时,将节点$$ 1 $$从头节点一行中删除,将包含$$ x = 1 $$的子集$$ [s_{1}, s_{2}] $$(包括$$ s_{2} $$自己)的元素也从所在的列中删除。如图所示: ![DancingLink7.svg](../res/DancingLink7.svg) 仔细观察可知,删除之后仍然能够判定$$ s_{1}, s_{2} $$包含元素$$ 1 $$($$ [1, 8, 15] $$拥有列关系),且可知$$ s_{1} = [1, 3, 5, 6], s_{2} = [1, 4, 7] $$($$ [8, 10, 12, 13] $$,$$ [15, 18, 21] $$拥有行关系)。这些遗留的列表指针可以恢复错误选择。对于子集$$ s_{2} = [1, 4, 7] $$上的所有元素进行相同的链表操作,等价于将$$ s_{1}, s_{2}, s_{3}, s_{5} $$染红: ![DancingLink8.svg](../res/DancingLink8.svg) 若尝试所有子集组合后仍无法找出精确覆盖,则说明该条件下不存在精确覆盖。舞蹈链算法的时间复杂度与递归的时间复杂度一样是$$ O(n^m) $$。 -------- #### 源码 [DancingLink.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/DancingLink.h) [DancingLink.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/DancingLink.cpp) #### 测试 [DancingLinkTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/Search/DancingLinkTest.cpp)