【轉載】淺談2—SAT問題

2-SAT：http://www.cppblog.com/ACflying/archive/2009/06/06/86912.html

1 2 - SAT就是2判定性問題，是一種特殊的邏輯判定問題。
2 2 - SAT問題有何特殊性？該如何求解？
3 我們從一道例題來認識2 - SAT問題，並提出對一類2 - SAT問題通用的解法。 

Poi  0106  Peaceful Commission [和平委員會]：

某國有n個黨派，每個黨派在議會中恰有2個代表。
現在要成立和平委員會 ，該會滿足：
每個黨派在和平委員會中有且只有一個代表
如果某兩個代表不和，則他們不能都屬於委員會
代表的編號從1到2n，編號為2a - 1 、2a的代表屬於第a個黨派

輸入n（黨派數），m（不友好對數）及m對兩兩不和的代表編號
其中1≤n≤ 8000 ， 0 ≤m ≤ 20000
 
求和平委員會是否能創立。若能，求一種構成方式。
輸入：     輸出：3   2         1       1   3         4         2   4         5               

原題可描述為：

有n個組，第i個組裡有兩個節點Ai, Ai '  。需要從每個組中選出一個。而某些點不可以同時選出（稱之為不相容）。任務是保證選出的n個點都能兩兩相容。
（在這裡把Ai, Ai '  的定義稍稍放寬一些，它們同時表示屬於同一個組的兩個節點。也就是說，如果我們描述Ai，那麼描述這個組的另一個節點就可以用Ai ' ）

初步構圖
如果Ai與Aj不相容，那麼如果選擇了Ai，必須選擇Aj‘ ；同樣，如果選擇了Aj，就必須選擇Ai’ 。   Ai             Aj ' 
 Aj             Ai‘                    
這樣的兩條邊對稱

我們從一個例子來看：
假設4個組，不和的代表為：1和4，2和3，7和3，那麼構圖：
假設：首先選1 3必須選，2不可選 8必須選， 4 、7不可選  5 、6可以任選一個

矛盾的情況為：
存在Ai，使得Ai既必須被選又不可選。

得到演算法1：
枚舉每一對尚未確定的Ai, Ai‘ ，任選1個，推導出相關的組，若不矛盾，則可選擇；否則選另1個，同樣推導。若矛盾，問題必定無解。
此演算法正確性簡要說明：
由於Ai,Ai '  都是尚未確定的，它們不與之前的組相關聯，前面的選擇不會影響Ai, Ai '  。
演算法的時間複雜度在最壞的情況下為O(nm)。
在這個演算法中，並沒有很好的利用圖中邊的對稱性

 更一般的說：
在每個一個環裡，任意一個點的選擇代表將要選擇此環裡的每一個點。不妨把環收縮成一個子節點（規定這樣的環是極大強連通子圖）。新節點的選擇表示選擇這個節點所對應的環中的每一個節點.對於原圖中的每條邊Ai -> Aj（設Ai屬於環Si，Aj屬於環Sj）如果Si≠Sj，則在新圖中連邊:Si -> Sj

這樣構造出一個新的有向無環圖。此圖與原圖等價。

通過求強連通分量，可以把圖轉換成新的有向無環圖，在這個基礎上，介紹一個新的演算法。

新演算法中，如果存在一對Ai, Ai ' 屬於同一個環，則判無解，否則將採用拓撲排序，以自底向上的順序進行推導，一定能找到可行解。

至於這個演算法的得來及正確性，將在下一段文字中進行詳細分析。
回憶構圖的過程：
對於兩個不相容的點 Ai, Aj，構圖方式為：Ai -> Aj ' ,Aj->Ai ' ,前面提到過，這樣的兩條邊對稱，也就是說：
如果存在Ai -> Aj，必定存在Aj ' ->Ai ' 。
等價於：Ai -> Ak,Ak ' ->Ai '  方便起見，之後“ -> ”代表這樣一種傳遞關係.

猜測1：圖中的環分別對稱
如果存在Ai,Aj，Ai,Aj屬於同一個環(記作Si),那麼Ai ' , Aj ' 也必定屬於一個環(記作Si ' ).
再根據前面的引理，不難推斷出每個環分別對稱。

證明方式與引理相類似
一個稍稍複雜點的結構,其中紅、藍色部分分別為兩組對稱的鏈結構
推廣2：對於任意一對Si, Si '  ，Si的後代節點與Si '  的前代節點相互對稱。
繼而提出:
猜測2：若問題無解，則必然存在Ai, Ai '  ，使得Ai,Ai ' 屬於同一個環。也就是，如果每一對Ai,Ai '  都不屬於同一個環，問題必定有解。下面給出簡略證明：

先提出一個跟演算法1相似的步驟：
如果選擇Si，那麼對於所有Si -> Sj，Sj都必須被選擇。
而Si '  必定不可選，這樣Si’的所有前代節點也必定不可選（將這一過程稱之為刪除）。
由推廣2可以得到，這樣的刪除不會導致矛盾。

假設選擇S3 '  
?選擇S3 ' 的後代節點, S1 '
?刪除S3
?刪除S3的前代節點S1
S1與S1 ' 是對稱的

每次找到一個未被確定的Si，使得不存在Si -> Si '  選擇Si及其後代節點而刪除Si’及Si‘的前代節點。一定可以構造出一組可行解。
因此猜測2成立。

另外，若每次盲目的去找一個未被確定的Si，時間複雜度相當高。
以自底向上的順序進行選擇、刪除，這樣還可以免去“選擇Si的後代節點”這一步。
用拓撲排序實現自底向上的順序。

一組可能的拓撲序列(自底向上）:S1 ' ,S2,S2 ' ,S3 ' ,S3,S1

演算法2的流程：
1 ．構圖 2 ．求圖的極大強連通子圖 3 ．把每個子圖收縮成單個節點，根據原圖關係構造一個有向無環圖 4 ．判斷是否有解，無解則輸出（退出） 5 ．對新圖進行拓撲排序 6 ．自底向上進行選擇、刪除 7 ．輸出

小結：
整個演算法的時間複雜度大概是O(m)，解決此問題可以說是相當有效了。
在整個演算法的構造、證明中反覆提到了一個詞：對稱。發現、利用了這個圖的特殊性質，我們才能夠很好的解決問題。
並且，由2 - SAT問題模型變換出的類似的題目都可以用上述方法解決。

全文總結：
充分挖掘圖的性質，能夠更好的解決問題。
不僅僅是對於圖論，這種思想可以在很多問題中得到很好的應用。
希望我們能掌握此種解題的思想，在熟練基礎演算法的同時深入分析、靈活運用、大膽創新，從而解決更多更新的難題。