算法合集之《由對(duì)稱(chēng)性解2-sat問(wèn)題》-文庫(kù)吧
2024-10-03 18:37 本頁(yè)面
【正文】 Ai Aj39。 Aj Ai‘ 這樣的兩條邊 對(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必須選， 7不可選 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,Ai39。 都是尚未確定的，它們不與之前的組相關(guān)聯(lián)，前面的選擇不會(huì)影響 Ai, Ai39。 。 ? 算法的時(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同樣如此。 圖的收縮 1 3 2 4 5 6 7 8 ? 對(duì)于原圖中的每條邊 Ai Aj（設(shè) Ai屬于環(huán) Si， Aj屬于環(huán) Sj）如果 Si≠Sj， 則在新圖中連邊： Si
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1