GSAT 不完整示例

Question

GSAT（贪婪满足性）算法可用于查找CNF编码的搜索问题的解决方案。我知道由于 GSAT 是贪婪的，它是不完整的（这意味着在某些情况下可能存在解决方案，但 GSAT 找不到它）。从下面的链接中，我了解到当翻转变量贪婪地将我们困在一个循环中时，就会发生这种情况，例如我→我→我→我。

http://www.dis.uniroma1.it/~liberato/ar/incomplete/incomplete.html

我一直在努力想出一个可以显示这一点的实际实例，但一直无法（并且在其他地方找不到示例）。任何帮助将不胜感激。谢谢:)

附言我不是在谈论变量与子句之比接近 4.3 的"硬"k-SAT 问题。我只是在寻找一个简单的例子，可能涉及所需的最少数量的变量和/或子句。

Answer 1

取一个包含 n 个变量的小公式，运行 GSAT> 2^n 步。由于只有 2^n 种不同的组合可以尝试，因此 GSAT 必须重复自己 - 它不会因为公式不满足而停止。

一个小的不满足公式是 （A V B V C） ^ （~A V B V C） ^ （A V ~B V C） ^ （~A V ~B V C） ^ （A V B V ~C） ^ （~A V B V ~C） ^ （A V ~B V ~

C） ^ （~A V ~B V ~C） - 所有 8 个 3 变量项的组合。

在高德纳第4A卷第7.1.1节中，方程32 P 56高德纳给出了他所谓的有趣的8项公式，其中包含八个不同的变量。

Answer 2

公式呢：

{x_1, x_2, -x_3}, {-x_1, x_2, -x_3}, {-x_2, -x_3}, {-x_2, -x_3}, {x_2, x_3}, {x_2, x_3}

此公式通过赋值 （0,1,0） 满足。但是，如果一个人从初始作业（0,0,1）开始，那么他会得到分数（1,2,2），因此会翻转x_1。然后一个人进入作业（1,0,1），这再次导致分数（1,2,2），你被卡住了。然后，只有重新启动另一个初始任务才能帮助您摆脱困境。

当然，由于两个双子句，这有点构造，但我相信人们可以很容易地扩展它以实现没有重复子句的公式。