GSAT不完整示例

可以使用GSAT（贪婪可满足性）算法来找到在CNF中编码的搜索问题的解决方案。我知道，由于GSAT是贪婪的，它是不完整的（这意味着会有解决方案可能存在的情况，但GSAT找不到它）。从下面的链接，我才知道，这可能发生翻转变量时，贪婪地捕捉我们在一个周期内，如I→我”→‘我’→一GSAT不完整示例

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

我一直挺难拿出一个实际的例子，可以显示这一点，但一直没有能力（和其他地方找不到例子）。任何帮助将非常感激。谢谢:)

P.S.我不是在谈论变量与条款的比率接近4.3的“硬”k-SAT问题。我只是寻找一个简单的例子，可能涉及最少数量的变量和/或子句需要。

来源

2014-02-27 sarora

我认为该链接上的算法有一个错误：在选择最佳变量进行更改后，如果还有不满意的子句，则它将转到步骤* 1 *，这将导致所有内容都被随机重新初始化，而不是尝试第二贪婪的一步。 –

即使问题得到解决，也无法说明这个算法找不到的问题实例，因为它可能因为初始随机赋值给变量而变得幸运。 –

取n个变量的小不可满足公式，并运行GSAT> 2^n个步骤。由于只有2^n个不同的组合可以尝试，所以GSAT必须重复自己 - 它不会停止，因为公式不被满足。一个小的不可满足公式是（AVBVC）（AVBVC）（AV_BVC）（AV_VBC））^（〜AV〜BV〜C） - 3个变量项的所有8种组合。

Knuth第4A卷7.1.1方程32 P 56 Knuth给出了他称之为有8个不同变量的有趣8个子句的公式。

来源

2014-02-27 06:09:23 mcdowella

他/她正在寻找无法通过GSAT解决的*可满足*公式。（尽管在OP提供的链接描述的GSAT算法中，没有可满足的问题实例可以保证被错过，因为它可以通过它的第一个随机变量赋值而“幸运”。） –

谢谢你的回答/评论。正如j_random_hacker提到的那样，我正在寻找一个将会给GSAT带来困难的_satisfiable_公式。我知道，给定一个解决方案给予足够的时间（因为GSAT重新启动与随机初始任务），但我正在寻找一组条款和**一些初始任务**，将抛出GSAT（可能扔到一个循环，以便它必须重新启动）。 – sarora

怎么样的公式：

{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），你被卡住了。然后，只有重新启动另一个初始分配才能帮助您脱身。

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

来源

2014-06-27 09:45:47 Arne

GSAT不完整示例

回答

相关问题