线性 Sat Unsat 与线性 Unsat Sat
Linear Sat Unsat vs Linear Unsat Sat
我知道上述两种算法都采用迭代解决方案来寻找 MAXSAT 问题的最优解，但我想知道为什么从可满足的方面开始寻找 MAXSAT 的解决方案比从不可满足的方面搜索更好？
此外，可满足性方面意味着放宽所有可能的软条款，直到我们达到 UNSAT，而不可满足性方面意味着从不放松条款开始增加数量，直到我们达到 SAT
MAX-SAT 问题通常与不可满足的公式有关。在一般情况下，不可满足性证明比可满足性证明更难编写。当您从实例中删除约束时，不可满足性证明也往往会变得更难，过度约束是一些不可满足性实例容易的主要原因。
因此，使用一种方法，您从简单的实例开始，这些实例逐渐变得难以编写 SAT/UNSAT 证明，而另一种方法则开始尝试编写硬证明，并通过必须编写一个下一次迭代更难。
我知道上述两种算法都采用迭代解决方案来寻找 MAXSAT 问题的最优解，但我想知道为什么从可满足的方面开始寻找 MAXSAT 的解决方案比从不可满足的方面搜索更好？
此外，可满足性方面意味着放宽所有可能的软条款，直到我们达到 UNSAT，而不可满足性方面意味着从不放松条款开始增加数量，直到我们达到 SAT
MAX-SAT 问题通常与不可满足的公式有关。在一般情况下，不可满足性证明比可满足性证明更难编写。当您从实例中删除约束时，不可满足性证明也往往会变得更难，过度约束是一些不可满足性实例容易的主要原因。
因此，使用一种方法，您从简单的实例开始，这些实例逐渐变得难以编写 SAT/UNSAT 证明，而另一种方法则开始尝试编写硬证明，并通过必须编写一个下一次迭代更难。