2可滿足性問題算法

Question

任何人都可以解釋2可滿足性問題的算法還是提供相同的鏈接？我無法找到理解它的好鏈接。

Answer 1

你可以用貪婪的方法解決它。 或者使用圖論，這裏是使用圖論解釋解的鏈接。 http://www.cs.tau.ac.il/~safra/Complexity/2SAT.ppt

Answer 2

這是關於該主題的Wikipedia頁面，其中描述了一個多項式時間算法。 （僅僅嘗試所有不同真值分配的蠻力算法就是指數時間。）也許一些進一步的解釋會有所幫助。

表述「如果P則Q」是假僅當P爲真和Q是假的。因此表達式具有與「Q或不P」相同的真值表值。它也相當於它的對立性，即「如果不是Q然後不是P」，並且又相當於「不是P或Q」（與另一個相同）。

所以算法涉及取代形式爲「A或B」的每個表達式中，用兩個表達式，「如果不是A，那麼B」和「如果不是則B A」。 （把它的另一種方式，A和B不能同時爲假。）

接下來，構造表示這些影響的曲線圖。爲每個「A」和「不是A」創建節點，併爲上面獲得的每個影響添加鏈接。

最後一步是確保沒有一個變量是相當於其自身的否定。也就是說，對於每個變量A（或不是A），按照鏈接發現所有可以從它到達的節點，並注意檢測循環。

如果這些變量中的一個，A，可以達到「非A」，和「未A」也可以達到A，則原始表達式是不令人滿意的。 （這是一個悖論。）如果沒有一個變量做到這一點，那麼它是可以滿足的。

（這沒關係，如果A蘊含「不是」，而不是其他方式這僅僅意味着一個必須被否定，滿足表達式。）

Answer 3

如果你有個變量和M條款：

用2n個頂點創建一個圖形：直觀上，每個頂點類似於每個變量的真或假真值。對於每個子句（a v b），其中a和b是文字，創建一個從！a到b和從！b到a的邊。這些邊緣意味着如果a不是真的，那麼b必須是真的，反之亦然。

一旦有向圖被創建，經過圖，看看是否有是同時包含A和！一對一些變量的循環。如果存在，那麼2SAT就不可滿足（因爲a意味着！a，反之亦然）。否則，它是令人滿意的，這甚至可以給你一個令人滿意的假設（選擇一些字面意思，以便a不暗示！a，從那裏強制所有含義，重複）。您可以使用任何標準圖算法ala Breadth-First Search，Floyd-Warshall或這些算法來完成這部分任務，具體取決於您對算法的時間複雜程度有多敏感。

Answer 4

2 satisfiabilty：！

如果x & x被強連接 然後從X，我們可以達到X 從X，我們可以達到X

所以在我們的操作中， 萬一！ x， 我們只有2個選項， 1.taking x（x）導致！X 2.rejecting X，導致X 兩者的選擇都是導致的在同一時間服用，並拒絕選擇的悖論

因此可滿足是不可能的（X！）：d