<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 $$列矩陣：  舞蹈鏈算法用十字鏈表這種特別的數據結構將所有元素串聯起來，坐標為$$ [i, j] $$的節點下標是$$ i \times m + j $$，表示$$ j \in s, j \in s_{i} $$。沿著十字鏈表的行可以遍歷子集$$ s_{i} $$的所有元素，沿著十字鏈表的列可以遍歷所有包含$$ j $$的子集。   $$ (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} $$）；  $$ (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} $$；  $$ (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 $$，因此可以直接跳過；  $$ (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} $$自己）的元素也從所在的列中刪除。如圖所示：  仔細觀察可知，刪除之后仍然能夠判定$$ 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} $$染紅：  若嘗試所有子集組合后仍無法找出精確覆蓋，則說明該條件下不存在精確覆蓋。舞蹈鏈算法的時間復雜度與遞歸的時間復雜度一樣是$$ 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)