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