由對(duì)稱性解SAT問(wèn)題博客園

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

2、2 4 5n原題可描述為： 有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)。也就是說(shuō)，如果我們描述Ai，那么描述這個(gè)組的另一個(gè)節(jié)點(diǎn)就可以用Ai）n如果Ai與Aj不相容，那么如果選擇了Ai，必須選擇Aj ；同樣，如果選擇了Aj，就必須選擇Ai 。 Ai Aj Aj Ai 這樣的兩條邊對(duì)稱對(duì)稱n我們從一個(gè)例子來(lái)看：n假設(shè)4個(gè)組，不和的代表為：1和4，2和3，7和3，那么構(gòu)圖：13245678假設(shè)： 首先選13必須選，2不可

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

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

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

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

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