由對稱性解2-sat問題-資料下載頁
2025-07-20 03:33本頁面
【正文】 及 Si‘的前代節(jié)點。 一定可以構(gòu)造出一組可行解。 ? 因此 猜測 2成立。 S1 S139。 S2 S239。 S339。 S3 假設選擇 S339。 ?選擇 S339。的后代節(jié)點 , S139。 ?刪除 S3 ?刪除 S3的前代節(jié)點 S1 S1與 S139。是 對稱 的 ? 另外，若每次盲目的去找一個未被確定的 Si，時間復雜度相當高。 ? 以 自底向上 的順序進行選擇、刪除，這樣還可以免去“ 選擇 Si的后代節(jié)點 ” 這一步。 ? 用 拓撲排序 實現(xiàn)自底向上的順序。 S1 S139。 S2 S239。 S339。 S3 一組可能的拓撲序列 (自底向上） S1 39。 S2 S239。 S339。 S3 S1 算法 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ì)，我們才能夠很好的解決問題。 ? 并且，由 2SAT問題模型變換出的類似的題目都可以用上述方法解決。 全文總結(jié)： ? 充分挖掘圖的性質(zhì)，能夠更好的解決問題。 ? 不僅僅是對于圖論，這種思想可以在很多問題中得到很好的應用。 ? 希望我們能掌握此種解題的思想，在熟練基礎算法的同時深入分析、靈活運用、大膽創(chuàng)新，從而解決更多更新的難題。
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1