ANTLR - 布尔satisfiabilty(ANTLR - Boolean satisfiab

我有一个ANTLR表达式分析器，其可以评估的形式的表达式|使用所生成的访问者（A＆（B C））。 A，B和C可采取任何的2个值的true或false 。 但是我面对发现A，B和C的所有组合的量，表达式为真的一个挑战。 我试图通过下面的方法来解决这个问题。

1. 评估的3个变量采取真假每个表达式
2. 这涉及到8点的组合，因为2 ^ 3是8
3. 我给评估值像000，001，010 ....... 111变量和评估使用访客

虽然这工作该方法成为计算密集型的变量数量的增加。 因此，对于具有20个变量的表达式需要1048576次计算。 如何优化这一复杂性，使我得到的所有的真实表情？ 我希望这符合布尔satisfiabilty问题

Answer 1:

它的作用。 如果您liimted 20-30变量，你可以简单的蛮力所有组合的审判。 如果需要每尝试为100ns（这就是500的机器指令），它将在约100秒的运行。 这比你快。

如果你想解决比这更大的方程，你需要建立一个真正的约束求解。

编辑由于对试图去并行加速这一野蛮强制答案Java程序OP备注：

我不知道你是怎么表现你的布尔公式。 对于蛮力，你不想解释公式树或做其他事是缓慢的。

一个关键的诀窍是让布尔公式快速的评价。 对于大多数编程语言，你应该能够编写公式来测试，通过手在语言中的天然表达，把它包装ñ嵌套循环和编译整个事情，例如，

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

编译（或甚至被Java即时编译），我期望的肠子环采取每布尔运算1-2的机器指令，仅接触寄存器或单个cachec线，加2为循环。 对于20个变量那是约42机器指令，比我在第一段粗略的估计更好。

如果一个坚持，一个可以转换的最外层循环（3或4）转换成并行线程，但是如果你想要的是打印语句我不明白如何将实际在实用性方面关系。

如果你有许多公式，很容易写一个代码生成器，从你的公式（例如，ANTLR解析树）的任何表示产生此。

文章来源: ANTLR - Boolean satisfiabilty