WSAT爲什麼勝過模擬退火？

Question

在某些日記上，我讀到WSAT（Walking SAT）算法在解決SAT問題方面比模擬退火算法有更好的性能。

所以我的問題是，有人可以解釋我們爲什麼得到這個結果？ 可能是因爲SA更像是一種通用算法？

---

編輯： Here也許最相關的文檔，我讀一下。

Answer 1

模擬退火評估隨機選擇的鄰居，算法總是移動到鄰居，如果它更好，遵循物理學的直覺。但WalkSAT有時會更好，有時候而不是移動到鄰居，即使它更好。

當您開始解決WalkSAT可以滿足的3-CNF：或者您已經解決了您的問題，或者某些子句不滿意。子句不滿足的事實意味着子句中的至少一個變量必須翻轉才能找到解決方案。如果從長度等於3的子句中隨機選擇變量，很容易看出每個翻轉的機會是正確的33％或更好[1]。

SA不具備這樣的高概率獲得成功，並有被卡在一個地方最大的高風險...

這是我會怎樣解釋自己爲什麼WalkSAT比SA更好，但有可能是已經研究了這個問題;）你應該仔細看看this paper [2]，提供SA和WalkSAT之間的詳細比較。

---

[1] Papadimitrou，C.H.，& Steiglitz，K。（1982）。組合優化：算法和複雜性。出版商：Prentice Hall。

[2] Selman，B.，Kautz，H.A.，& Cohen，B。（1994）。改善本地搜索的噪音策略。在AAAI（第94卷，第337-343頁）中。