GSAT（贪婪可满足性）算法可用于找到以 CNF 编码的搜索问题的解决方案。我知道，由于 GSAT 是贪婪的，它是不完整的（这意味着可能存在解决方案但 GSAT 找不到它的情况）。从下面的链接中，我了解到，当翻转变量贪婪地将我们困在 I → I' → I'' → I 这样的循环中时，就会发生这种情况。
http://www.dis.uniroma1.it/~liberato/ar/incomplete/incomplete.html
我一直在努力想出一个可以显示这一点的实际实例，但一直未能（也无法在其他地方找到示例）。任何帮助将非常感激。谢谢 ：）
PS 我不是在谈论变量与子句的比率接近 4.3 的“硬”k-SAT 问题。我只是在寻找一个简单的例子，可能涉及最少数量的变量和/或所需的子句。
公式呢：
{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），你被卡住了。然后，只有重新启动另一个初始任务才能帮助您摆脱困境。
当然，由于两个双重子句，这有点构建，但我相信可以轻松扩展它以实现没有重复子句的公式。
取一个带有 n 个变量的小不可满足的公式并运行 GSAT > 2^n 步。由于只有 2^n 种不同的组合可以尝试，GSAT 必须重复自己——它不会因为公式不满足而停止。
一个小的不可满足的公式是 (AVBVC) ^ (~AVBVC) ^ (AV ~BVC) ^ (~AV ~BVC) ^ (AVBV ~C) ^ (~AVBV ~C) ^ (AV ~BV ~C) ^ (~ AV ~BV ~C) - 3 变量项的所有 8 种组合。
在 Knuth vol 4A 第 7.1.1 节等式 32 P 56 Knuth 给出了他所谓的有趣的 8 子句公式，其中包含八个不同的变量。