0

我目前正在为考试研究 2SAT 问题，但我真的不明白如何使用蛮力检查解决方案是否存在。我知道这看起来有点奇怪，但我了解如何更好地实现蕴含图，但我不太确定如何实现蛮力策略。

有人可以分享一些见解吗？也许在伪代码或java中。

谢谢

4

2 回答 2

2

公式中的变量可以编码为整数值中的位。然后，蛮力方法归结为积分“容器”可能采用的所有可能值的范围。

换句话说，你有一个整数数组，它代表你公式的所有变量，你用进位递增整数，并在每一步检查它代表的解决方案与你的公式。当解决方案匹配时，您停止。

对于这样的变量容器，这是一个非常简单的实现：

class OverflowException extends RuntimeException {}

public class Variables {
    int[] data;
    int size;

    public Variables(int size_){
        size = size_;
        data = new int[1 + size/32];
    }
    public boolean get(int i){
         return (data[i/32] & (1 << i%32)) != 0;
    }
    public void set(int i, boolean v){
        if (v)
            data[i/32] |= (1 << i%32);
        else
            data[i/32] &= ~(1 << i%32);
    }
    public void increment(){
         int i;
         for (i=0; i < size/32; i++){
             data[i]++;
             if (data[i] != 0) return;
         }
         if (size%32 != 0){
             data[i]++;
             if ((data[i] & ~((1 << (size%32)) - 1)) != 0)
                 throw new OverflowException();
        }
    }
}

（警告购买者：未经测试的代码）。

变量数组也可以更简单地表示为一个boolean容器，但是由于增量步骤，您可能会损失一些性能（尽管可以通过使用格雷码而不是简单的二进制编码来进行增量操作来缓解这种情况，但是这个实现的复杂性似乎表明相反，如果你选择一个复杂的解决方案，它也可能是一个好的 sat2 求解器）。

于 2013-02-08T20:15:18.703 回答
0

这就是我们不使用蛮力解决方案的原因:)，它们消耗大量资源。我的算法不是创建一个具有所有可能性的矩阵。但是要创建一个作业，然后立即对其进行测试。然后创建下一个。当您找到第一个解决方案时，您可以停止。

于 2013-02-08T19:16:40.087 回答