算法合集之《由對稱性解2-SAT問題》.ppt

由對稱性解2-SAT問題,2-SAT:,2-SAT就是2判定性問題，是一種特殊的邏輯判定問題。 2-SAT問題有何特殊性？該如何求解？ 我們從一道例題來認識2-SAT問題，并提出對一類2-SAT問題通用的解法。,Poi 0106 Peaceful Commission 和平委員會,某國有n個黨派，每個黨派在議會中恰有2個代表。 現(xiàn)在要成立和平委員會 ，該會滿足： 每個黨派在和平委員會中有且只有一個代表 如果某兩個代表不和，則他們不能都屬于委員會 代表的編號從1到2n，編號為2a-1、2a的代表屬于第a個黨派,輸入n（黨派數(shù)），m（不友好對數(shù)）及m對兩兩不和的代表編號 其中1n8000，0m 20000,求和平委員會是否能創(chuàng)立。 若能，求一種構(gòu)成方式。,例：輸入：3 2 輸出：1 1 3 4 2 4 5,分析：,原題可描述為： 有n個組，第i個組里有兩個節(jié)點Ai, Ai 。需要從每個組中選出一個。而某些點不可以同時選出（稱之為不相容）。任務是保證選出的n個點都能兩兩相容。 （在這里把Ai, Ai 的定義稍稍放寬一些，它們同時表示屬于同一個組的兩個節(jié)點。也就是說，如果我們描述Ai，那么描述這個組的另一個節(jié)點就可以用Ai）,初步構(gòu)圖,如果Ai與Aj不相容，那么如果選擇了Ai，必須選擇Aj ；同樣，如果選擇了Aj，就必須選擇Ai 。 Ai Aj Aj Ai 這樣的兩條邊對稱,我們從一個例子來看：,假設(shè)4個組，不和的代表為：1和4，2和3，7和3，那么構(gòu)圖：,1,3,2,4,5,6,7,8,假設(shè)： 首先選1 3必須選，2不可選 8必須選，4、7不可選,5、6可以任選一個,矛盾的情況為： 存在Ai，使得Ai既必須被選又不可選。,得到算法1： 枚舉每一對尚未確定的Ai, Ai ，任選1個，推導出相關(guān)的組，若不矛盾，則可選擇；否則選另1個，同樣推導。若矛盾，問題必定無解。,1,3,2,4,5,6,7,8,此算法正確性簡要說明： 由于Ai,Ai 都是尚未確定的，它們不與之前的組相關(guān)聯(lián)，前面的選擇不會影響Ai, Ai 。,算法的時間復雜度在最壞的情況下為O(nm)。 在這個算法中，并沒有很好的利用圖中邊的對稱性,先看這樣一個結(jié)構(gòu)：,更一般的說： 在每個一個環(huán)里，任意一個點的選擇代表將要選擇此環(huán)里的每一個點。不妨把環(huán)收縮成一個子節(jié)點（規(guī)定這樣的環(huán)是極大強連通子圖）。新節(jié)點的選擇表示選擇這個節(jié)點所對應的環(huán)中的每一個節(jié)點。,此圖中1和3構(gòu)成一個環(huán)，這樣1和3要么都被選擇，要么都不被選。 2和4同樣如此。,圖的收縮,對于原圖中的每條邊Ai Aj（設(shè)Ai屬于環(huán)Si，Aj屬于環(huán)Sj）如果SiSj，則在新圖中連邊： Si Sj,這樣構(gòu)造出一個新的有向無環(huán)圖。 此圖與原圖等價。,圖的收縮,通過求強連通分量，可以把圖轉(zhuǎn)換成新的有向無環(huán)圖，在這個基礎(chǔ)上，介紹一個新的算法。 新算法中，如果存在一對Ai, Ai屬于同一個環(huán)，則判無解，否則將采用拓撲排序，以自底向上的順序進行推導，一定能找到可行解。 至于這個算法的得來及正確性，將在下一段文字中進行詳細分析。,新算法的提出,深入分析：,回憶構(gòu)圖的過程： 對于兩個不相容的點 Ai, Aj，構(gòu)圖方式為： Ai Aj Aj Ai 前面提到過，這樣的兩條邊對稱，也就是說： 如果存在Ai Aj，必定存在Aj Ai 。,1,3,2,4,5,6,7,8,引理：原圖具有對稱傳遞性,等價于：Ai Ak Ak Ai 方便起見，之后“ ”代表這樣一種傳遞關(guān)系,Ai Ak Aj,Ai Ak Aj,猜測1：圖中的環(huán)分別對稱,如果存在Ai,Aj，Ai,Aj屬于同一個環(huán)（記作Si），那么Ai , Aj 也必定屬于一個環(huán)（記作Si ）。,再根據(jù)前面的引理，不難推斷出每個環(huán)分別對稱。,Ai Aj,Ai Aj,推廣1：新圖中，同樣具有對稱傳遞性。,S1,S1,S2,S2,S3,S3,一個稍稍復雜點的結(jié)構(gòu) 其中紅、藍色部分分別為兩組對稱的鏈結(jié)構(gòu),證明方式與引理相類似,分開來看，更加一般的情況，即下圖： （說明：此圖中Si有可能為Si的后代節(jié)點）,于是可以得到 推廣2：對于任意一對Si, Si ，Si的后代節(jié)點與Si 的前代節(jié)點相互對稱。,繼而提出 猜測2：若問題無解，則必然存在Ai, Ai ，使得Ai, Ai 屬于同一個環(huán)。 也就是，如果每一對Ai,Ai 都不屬于同一個環(huán)，問題必定有解。下面給出簡略證明：,問題的關(guān)鍵,先提出一個跟算法1相似的步驟： 如果選擇Si，那么對于所有Si Sj，Sj都必須被選擇。 而Si 必定不可選，這樣Si的所有前代節(jié)點也必定不可選（將這一過程稱之為刪除）。 由推廣2可以得到，這樣的刪除不會導致矛盾。,對稱性的利用,每次找到一個未被確定的Si，使得不存在Si Si 選擇Si及其后代節(jié)點而刪除Si及Si的前代節(jié)點。 一定可以構(gòu)造出一組可行解。 因此猜測2成立。,假設(shè)選擇S3 選擇S3的后代節(jié)點, S1 刪除S3 刪除S3的前代節(jié)點S1 S1與S1是對稱的,另外，若每次盲目的去找一個未被確定的Si，時間復雜度相當高。 以自底向上的順序進行選擇、刪除，這樣還可以免去“選擇Si的后代節(jié)點”這一步。 用拓撲排序?qū)崿F(xiàn)自底向上的順序。,一組可能的拓撲序列 (自底向上） S1 S2 S2 S3 S3 S1,算法2的流程：,1構(gòu)圖 2求圖的極大強連通子圖 3把每個子圖收縮成單個節(jié)點，根據(jù)原圖關(guān)系構(gòu)造一個有向無環(huán)圖 4判斷是否有解，無解則輸出（退出） 5對新圖進行拓撲排序 6自底向上進行選擇、刪除 7輸出,小結(jié)：,整個算法的時間復雜度大概是O(m)，解決此問題可以說是相當有效了。 在整個算法的構(gòu)造、證明中反復提到了一個詞：對稱。發(fā)現(xiàn)、利用了這個圖的特殊性質(zhì)，我們才能夠很好的解決問題。 并且，由2-SAT問題模型變換出的類