3

我有一大堆（20000）布尔表达式。它们由AND,OR和NOT运算符以及大量的布尔变量A1, A2, A3... 组成（大约 1000 个）。大多数表达式只包含 5 个，也许是 20 个这些变量。

给定变量 ( A1 = true, A2 = false, A3 = false ...) 的赋值，我必须找到计算结果为 的那些表达式false。

将针对多个 (10-100) 分配评估同一组表达式

以此目的：

  1. 我应该如何将表达式存储在磁盘上，以便我可以快速加载和解析它们（我目前将它们作为一些专门的 DSL 或作为或多或少标准化（并且非常慢）的关系数据结构，但我可以改变它）

  2. 是否有一种快速算法/数据结构来评估我可以使用的此类表达式？

  3. JVM 上的实现是否存在？

4

6 回答 6

5

您可能需要考虑将表达式转换为连接范式并组合类似的术语。然后，您可以将表达式双向映射到一组术语，其中任何一个评估为 false 都意味着整个表达式评估为 false。对于变量的每个分配，从一组表达式开始，评估 CNF 项，直到一个评估为假。如果该术语为假，则涉及该术语的所有表达式也将为假，因此这些表达式也可以从集合中删除。

如果不查看表达式，就不能说这种方法是否适合您的情况 - 对于 1000 个变量和 20000 个表达式，它们可能没有许多共同的 CNF 术语。

在 Java 之外，对于大量的表达式，DNF 可能更有用，因为它在 GPU 上的实现是显而易见的。

于 2012-07-10T15:33:29.743 回答
2

对此的 SOP 答案是将表达式存储为 RPN（反向波兰表示法）中的字符串，然后编写一个简单的 Stack Machine 解析器来评估它们。

通常，RPN 字符串的评估速度几乎与内存中的 AST（抽象符号树）一样快。而且堆栈机器解析器非常容易编写。

于 2012-07-10T15:00:14.477 回答
0

您可以建立一个索引，在其中为每个变量记录两组表达式，变量出现正数的表达式和负数出现的变量。根据变量的值，您收集那些可能由于该变量而变为假的表达式（如果变量设置为假则为正，反之亦然）。编辑：这些只是候选人，你仍然需要评估他们，看看他们是否真的变成了假的。

与仅评估所有表达式相比，这是否有帮助取决于表达式的结构以及有多少评估为假。

于 2012-07-10T20:54:08.567 回答
0

尝试将它们转换为 CNF 并使用 MiniSat 检查表达式的计算结果是真还是假

于 2014-02-11T09:12:58.140 回答
0

更新：以下站点的代码可能会有所帮助。

将表达式列表转换为函数的源代码，当使用变量值调用该函数时，将评估所有函数并返回指示哪些表达式评估为假。编译该函数，然后为您的不同变量值调用它。

我做过类似的事情并使用了 Python。我必须编写的唯一解析和解释是将输入的布尔运算符“&”、“|”、“~”翻译成它们的 Python 等价物。

对于 Python 解决方案，您的问题大小似乎相当不错。

于 2012-07-10T16:09:28.820 回答
0

您似乎很喜欢 Java，但您是否考虑过将这些东西提供给具有 eval() 函数的语言？它可能会减少将表达式保存在文件中并对其进行评估的问题。请注意，如果您不信任表达式的（来源），这会产生安全隐患！

Jython 浮现在脑海中，但可能有几个可以很短的完成这个工作。

如果你嫁给了java，你可能会为布尔代数实现一个递归下降解析器。但这涉及更多。

于 2012-07-10T15:47:03.550 回答