由對稱性解SAT問題博客園

1、n2-SAT就是2判定性問題，是一種特殊的邏輯判定問題。n2-SAT問題有何特殊性？該如何求解？n我們從一道例題來認識2-SAT問題，并提出對一類2-SAT問題通用的解法。n某國有n個黨派，每個黨派在議會中恰有2個代表。n現(xiàn)在要成立和平委員會 ，該會滿足：n每個黨派在和平委員會中有且只有一個代表 n如果某兩個代表不和，則他們不能都屬于委員會 n代表的編號從1到2n，編號為2a-1、2a的代表屬于第a個黨派n輸入n（黨派數），m（不友好對數）及m對兩兩不和的代表編號 n其中1n8000，0m 20000 n求和平委員會是否能創(chuàng)立。n若能，求一種構成方式。 例：輸入：3 2 輸出：1 1 3 4

2、2 4 5n原題可描述為： 有n個組，第i個組里有兩個節(jié)點Ai, Ai 。需要從每個組中選出一個。而某些點不可以同時選出（稱之為不相容）。任務是保證選出的n個點都能兩兩相容。（在這里把Ai, Ai 的定義稍稍放寬一些，它們同時表示屬于同一個組的兩個節(jié)點。也就是說，如果我們描述Ai，那么描述這個組的另一個節(jié)點就可以用Ai）n如果Ai與Aj不相容，那么如果選擇了Ai，必須選擇Aj ；同樣，如果選擇了Aj，就必須選擇Ai 。 Ai Aj Aj Ai 這樣的兩條邊對稱對稱n我們從一個例子來看：n假設4個組，不和的代表為：1和4，2和3，7和3，那么構圖：13245678假設： 首先選13必須選，2不可

3、選8必須選，4、7不可選5、6可以任選一個的情況為：存在Ai，使得Ai既必須被選又不可選。 n得到：n枚舉每一對尚未確定的Ai, Ai ，任選1個，推導出相關的組，若不矛盾，則可選擇；否則選另1個，同樣推導。若矛盾，問題必定無解。13245678n此算法正確性簡要說明：n由于Ai,Ai 都是尚未確定的，它們不與之前的組相關聯(lián)，前面的選擇不會影響Ai, Ai 。n算法的時間復雜度在最壞的情況下為O(nm)。n在這個算法中，并沒有很好的利用圖中邊的對稱對稱性n先看這樣一個結構： n更一般的說：n在每個一個環(huán)里，任意一個點的選擇代表將要選擇此環(huán)里的每一個點。不妨把環(huán)收縮成一個子節(jié)點（規(guī)定這樣的環(huán)是極

4、大強極大強連通子圖連通子圖）。新節(jié)點的選擇表示選擇這個節(jié)點所對應的環(huán)中的每一個節(jié)點。此圖中1和3構成一個環(huán)環(huán)，這樣1和3要么都被選擇，要么都不被選。2和4同樣如此。13245678n對于原圖中的每條邊Ai Aj（設Ai屬于環(huán)Si，Aj屬于環(huán)Sj）如果SiSj，則在新圖中連邊： Si Sjn 這樣構造出一個新的有向無環(huán)圖。有向無環(huán)圖。n 此圖與原圖等價等價。13245678S1 S1S2 S2 S3 S3n通過求強連通分量，可以把圖轉換成新的有向無環(huán)圖，在這個基礎上，介紹一個新的算法。n新算法中，如果存在一對Ai, Ai屬于同一個環(huán)，則判無解，否則將采用拓撲排序，以自底向上的順序進行推導，一定能

5、找到可行解。n至于這個算法的得來及正確性，將在下一段文字中進行詳細分析。n回憶構圖的過程：n對于兩個不相容的點 Ai, Aj，構圖方式為： Ai Aj Aj Ai n前面提到過，這樣的兩條邊對稱對稱，也就是說：n如果存在Ai Aj，必定存在Aj Ai 。13245678n等價于：Ai Ak Ak Ai n方便起見，之后“ ”代表這樣一種傳遞關系 Ai Ak AjAi Ak Ajn如果存在Ai,Aj，Ai,Aj屬于同一個環(huán)（記作Si），那么Ai , Aj 也必定屬于一個環(huán)（記作Si ）。再根據前面的引理，不難推斷出每個環(huán)分別對稱。 Ai Aj Ai Aj 13245678S1 S1S2 S2 S

6、3 S3 一個稍稍復雜點的結構 其中紅、藍色部分分別為兩組對稱對稱的鏈結構證明方式與引理相類似S1 S1S2 S2 S3 S3n分開來看，更加一般的情況，即下圖：（說明：此圖中Si有可能為Si的后代節(jié)點） n于是可以得到 n繼而提出n也就是，如果每一對Ai,Ai 都不屬于同一個環(huán)，問題必定有解。下面給出簡略證明：n先提出一個跟算法算法1 1相似的步驟： n如果選擇Si，那么對于所有Si Sj，Sj都必須被選擇。 n而Si 必定不可選，這樣Si的所有前代節(jié)點也必定不可選（將這一過程稱之為刪除刪除）。n由推廣推廣2 2可以得到，這樣的刪除不會導致矛盾。n每次找到一個未被確定的Si，使得不存在Si

7、選擇Si及其后代節(jié)點而刪除Si及Si的前代節(jié)點。 一定可以構造出一組可行解。n因此猜測猜測2 2成立。S1 S1S2 S2 S3 S3 假設選擇S3 選擇S3的后代節(jié)點, S1刪除S3刪除S3的前代節(jié)點S1S1與S1是對稱對稱的n另外，若每次盲目的去找一個未被確定的Si，時間復雜度相當高。n以的順序進行選擇、刪除，這樣還可以免去“”這一步。n用實現(xiàn)自底向上的順序。S1 S1S2 S2 S3 S3一組可能的拓撲序列(自底向上）S1 S2 S2 S3 S3 S1 n1構圖n2求圖的極大強連通子圖n3把每個子圖收縮成單個節(jié)點，根據原圖關系構造一個有向無環(huán)圖n4判斷是否有解，無解則輸出（退出）n5對新圖進行拓撲排序n6自底向上進行選擇、刪除n7輸出小結：n整個算法的時間復雜度大概是O(m)，解決此問題可以說是相當有效了。n在整個算法的構造、證明中反復提到了一個詞：對稱對稱。發(fā)現(xiàn)、利用了這個圖的特殊性質，我們才能夠很好的解決問題。 n并且，由2-SAT問題模型變換出的類似的