在一些期刊上，我读到 WSAT（步行 SAT）算法在解决 SAT 问题方面比模拟退火算法具有更好的性能。
所以我的问题是，有人可以解释为什么我们得到这个结果吗？可能是因为 SA 更像是一种通用算法？
编辑： 这可能是我读到的最相关的文件。
问问题
194 次
1 回答
2
模拟退火评估随机选择的邻居，算法总是根据物理学直觉移动到更好的邻居。但是 WalkSAT 做得更好，有时即使它更好，也不会搬到邻居那里。
当您开始使用 WalkSAT 解决可满足的 3-CNF 时：或者您已经解决了问题，或者某些子句不满足。子句不满足这一事实意味着必须翻转子句中的至少一个变量才能找到解决方案。如果变量是从长度等于 3 的子句中随机选择的，很容易看出每次翻转都有 33% 或更高的正确率 [1]。
SA没有那么高的成功概率，并且有很高的陷入局部最大值的风险......
这就是我解释为什么 WalkSAT 比 SA 更好的方式，但可能已经有关于这个问题的研究；）你应该仔细看看这篇论文[2]，它提供了 SA 和 WalkSAT 之间的详细比较。
[ 1 ] Papadimitrou, CH 和 Steiglitz, K. (1982)。组合优化：算法和复杂性。出版商：普伦蒂斯·霍尔。
[ 2 ] Selman, B.、Kautz, HA 和 Cohen, B. (1994)。改进局部搜索的噪声策略。在 AAAI（第 94 卷，第 337-343 页）中。
于 2016-07-14T13:48:34.850 回答