Antlr-布尔满足

Question

i具有一个antlr表达式解析器，可以使用生成的访问者评估形式（a＆amp;（b | c））的表达式。A，B和C可以采用2个值true或false中的任何一个。但是，我面临的挑战是找到表达式为真的A，B和C的所有组合。我试图通过以下方法解决此问题。

1. 评估3个变量的表达式，每个变量
2. 这是8个组合，因为2 ^ 3是8
3. i评估给出像000，001、010之类的值........ 111对变量进行评估，并使用访问者进行评估

尽管此方法随着变量数量的增加而变为计算密集型。因此，对于具有20个变量的表达式，需要计算1048576。我如何优化这种复杂性，以便获得所有真实的表达方式？我希望这属于布尔令人满意的问题

Answer 1

它做到了。如果您被置于20-30个变量，则可以简单地强迫所有组合的试验。如果每次尝试需要100NS（这是500个机器说明），则将在大约100秒内运行。比你快。

如果要求解比这更大的方程式，则需要构建一个真正的约束求解器。

编辑由于操作的评论，要试图平行速度加快Java程序，该程序迫使答案：

我不知道您如何代表布尔公式。对于蛮力，您不想解释一条配方树或做其他慢的事情。

一个关键技巧是评估布尔公式 fast 。对于大多数编程语言，您应该能够用手工用该语言来测试该公式，以将其包装为n嵌套循环并编译整个内容，例如，

A=false;
do {
     B=false;
     do {
          C= false;
          do { 
               if (A & (B | C) ) { printf (" %b %b %bn",A,B,C);
               C=~C;
             } until C==false;
          B=~B;
        } until B==false;
     A=~A;
   } until A==false;

编译（甚至由Java夹住），我希望Innner Loop每次布尔操作1-2个机器说明，仅触摸寄存器或单个CACHEC线，再加上2个循环。对于20个变量，大约是42个机器说明，甚至比第一段中的粗略估计更好。

如果有人坚持，可以将最外面的循环（3或4）转换为平行线程，但是如果您想要的只是打印语句，我就不会看到这实际上会在实用程序方面重要。

如果您有许多这样的公式，则很容易编写代码生成器来从您对公式的任何表示形式（例如，Antlr Parse Tree）产生此产品。