算法學習：圖論之2-SAT

由對稱性解2 SAT問題伍昱 2 SAT 2 SAT就是2判定性問題 是一種特殊的邏輯判定問題 2 SAT問題有何特殊性 該如何求解 我們從一道例題來認識2 SAT問題 并提出對一類2 SAT問題通用的解法 Poi0106PeacefulCommission 和平委員會 某國有n個黨派 每個黨派在議會中恰有2個代表 現(xiàn)在要成立和平委員會 該會滿足 每個黨派在和平委員會中有且只有一個代表如果某兩個代表不和 則他們不能都屬于委員會代表的編號從1到2n 編號為2a 1 2a的代表屬于第a個黨派 輸入n 黨派數(shù) m 不友好對數(shù) 及m對兩兩不和的代表編號其中1 n 8000 0 m 20000 求和平委員會是否能創(chuàng)立 若能 求一種構(gòu)成方式 例 輸入 32輸出 1134245 分析 原題可描述為 有n個組 第i個組里有兩個節(jié)點Ai Ai 需要從每個組中選出一個 而某些點不可以同時選出 稱之為不相容 任務是保證選出的n個點都能兩兩相容 在這里把Ai Ai 的定義稍稍放寬一些 它們同時表示屬于同一個組的兩個節(jié)點 也就是說 如果我們描述Ai 那么描述這個組的另一個節(jié)點就可以用Ai 初步構(gòu)圖 如果Ai與Aj不相容 那么如果選擇了Ai 必須選擇Aj 同樣 如果選擇了Aj 就必須選擇Ai AiAj AjAi 這樣的兩條邊對稱 我們從一個例子來看 假設(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同樣如此 圖的收縮 對于原圖中的每條邊AiAj 設(shè)Ai屬于環(huán)Si Aj屬于環(huán)Sj 如果Si Sj 則在新圖中連邊 SiSj 這樣構(gòu)造出一個新的有向無環(huán)圖 此圖與原圖等價 圖的收縮 通過求強連通分量 可以把圖轉(zhuǎn)換成新的有向無環(huán)圖 在這個基礎(chǔ)上 介紹一個新的算法 新算法中 如果存在一對Ai Ai 屬于同一個環(huán) 則判無解 否則將采用拓撲排序 以自底向上的順序進行推導 一定能找到可行解 至于這個算法的得來及正確性 將在下一段文字中進行詳細分析 新算法的提出 深入分析 回憶構(gòu)圖的過程 對于兩個不相容的點Ai Aj 構(gòu)圖方式為 AiAj AjAi 前面提到過 這樣的兩條邊對稱 也就是說 如果存在AiAj 必定存在Aj Ai 1 3 2 4 5 6 7 8 引理 原圖具有對稱傳遞性 等價于 AiAkAk Ai 方便起見 之后 代表這樣一種傳遞關(guān)系 AiAkAj Ai Ak Aj 猜測1 圖中的環(huán)分別對稱 如果存在Ai Aj Ai Aj屬于同一個環(huán) 記作Si 那么Ai Aj 也必定屬于一個環(huán) 記作Si 再根據(jù)前面的引理 不難推斷出每個環(huán)分別對稱 Ai Aj AiAj 推廣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 那么對于所有SiSj Sj都必須被選擇 而Si 必定不可選 這樣Si 的所有前代節(jié)點也必定不可選 將這一過程稱之為刪除 由推廣2可以得到 這樣的刪除不會導致矛盾 對稱性的利用 每次找到一個未被確定的Si 使得不存在SiSi 選擇Si及其后代節(jié)點而刪除Si 及Si 的前代節(jié)點 一定可以構(gòu)造出一組可行解 因此猜測2成立 假設(shè)選擇S3 選擇S3 的后代節(jié)點 S1 刪除S3 刪除S3的前代節(jié)點S1S1與S1 是對稱的 另外 若每次盲目的去找一個未被確定的Si 時間復雜度相當高 以自底向上的順序進行選擇 刪除 這樣還可以免去 選擇Si的后代節(jié)點 這一步 用拓撲排序?qū)崿F(xiàn)自底向上的順序 一組可能的拓撲序列 自底向上 S1 S2S2 S3 S3S1 算法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問題模型變換出的類