由對稱性解2-sat問題(編輯修改稿)
2024-08-16 03:33 本頁面
【文章內(nèi)容簡介】 Sj ? 這樣構(gòu)造出一個(gè)新的 有向無環(huán)圖。 ? 此圖與原圖 等價(jià) 。 1 3 2 4 5 6 7 8 S1 S139。 S2 S239。 S339。 S3 圖的收縮 ? 通過求強(qiáng)連通分量，可以把圖轉(zhuǎn)換成新的有向無環(huán)圖，在這個(gè)基礎(chǔ)上，介紹一個(gè)新的算法。 ? 新算法中，如果存在一對 Ai, Ai39。屬于同一個(gè)環(huán)，則判無解，否則將采用拓?fù)渑判?，以自底向上的順序進(jìn)行推導(dǎo)，一定能找到可行解。 ? 至于這個(gè)算法的得來及正確性，將在下一段文字中進(jìn)行詳細(xì)分析。 新算法的提出 深入分析： ? 回憶構(gòu)圖的過程： ? 對于兩個(gè)不相容的點(diǎn) Ai, Aj，構(gòu)圖方式為： Ai Aj39。 Aj Ai39。 ? 前面提到過，這樣的兩條邊 對稱 ，也就是說： ? 如果存在 Ai Aj，必定存在 Aj39。 Ai39。 。 1 3 2 4 5 6 7 8 引理：原圖具有 對稱 傳遞性 ? 等價(jià)于： Ai Ak Ak39。 Ai39。 ? 方便起見，之后“ ”代表這樣一種傳遞關(guān)系 Ai Ak Aj Ai39。 Ak39。 Aj39。 猜測 1：圖中的環(huán)分別 對稱 ? 如果存在 Ai,Aj， Ai,Aj屬于同一個(gè)環(huán)（
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1