算法學(xué)習(xí)：圖論之2-SAT

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