贪心可满足性（GSAT）算法可用于求解CNF编码的搜索问题我知道，既然GSAT是贪婪的，它是不完整的（这意味着存在可能存在解决方案的情况，但是GSAT找不到它）。从下面的链接中，我了解到，当翻转变量贪婪地将我们困在一个循环中时，这可能发生，例如i→i'→i'→i。
http://www.dis.uniroma1.it/~liberato/ar/incomplete/incomplete.html
我一直在努力寻找一个能证明这一点的实际例子，但一直未能（也找不到其他地方的例子）任何帮助都将不胜感激。谢谢）
我不是在说“硬”k-sat问题，在这个问题中，变量与子句的比率接近4.3。我只想找一个简单的例子，可能涉及最少数量的变量和/或子句。
最佳答案
取一个n个变量的不可满足的小公式，运行GSAT>2^n步因为只有2^n个不同的组合可以尝试，gsat必须重复它自己-它不会因为公式不满足而停止。
一个不可满足的小公式是（a v b-v c）^（~avb-vc）^（a v~bvc）^（~av~bvc）^（avb-v~c）^（~avb-v~c）^（av~bv~c）^（~av~bv~c）^（~av~bv~c）-所有8个3变量项的组合。
在Knuth vol 4A第7.1.1节中，等式32 P 56 Knuth给出了一个有趣的8子句公式，其中包含8个不同的变量。