算法合集之由對(duì)稱性解2-sat問(wèn)題(編輯修改稿)
2024-11-14 18:37 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 Sj ? 這樣構(gòu)造出一個(gè)新的 有向無(wú)環(huán)圖。 ? 此圖與原圖 等價(jià) 。 1 3 2 4 5 6 7 8 S1 S139。 S2 S239。 S339。 S3 圖的收縮 ? 通過(guò)求強(qiáng)連通分量，可以把圖轉(zhuǎn)換成新的有向無(wú)環(huán)圖，在這個(gè)基礎(chǔ)上，介紹一個(gè)新的算法。 ? 新算法中，如果存在一對(duì) Ai, Ai39。屬于同一個(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)圖方式為： Ai Aj39。 Aj Ai39。 ? 前面提到過(guò)，這樣的兩條邊 對(duì)稱 ，也就是說(shuō)： ? 如果存在 Ai Aj，必定存在 Aj39。 Ai39。 。 1 3 2 4 5 6 7 8 引理：原圖具有 對(duì)稱 傳遞性 ? 等價(jià)于： Ai Ak Ak39。 Ai39。 ? 方便起見(jiàn)，之后“ ”代表這樣一種傳遞關(guān)系 Ai Ak Aj Ai39。 Ak39。 Aj39。 猜測(cè) 1：圖中的環(huán)分別 對(duì)稱 ? 如果存在 Ai,Aj， Ai,Aj屬于同一個(gè)環(huán)（記
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1