复杂的布尔表达式优化，范式？
我正在开发一个流规则引擎，我的一些客户有几百条规则，他们想对到达系统的每个事件进行评估。规则是纯（即无副作用）布尔表达式，它们可以任意深度嵌套。
客户在运行时创建、更新和删除规则，我需要动态检测和适应规则的数量。目前，表达式计算在内部 AST 上使用解释器，我还没有开始考虑 codegen。
与往常一样，树中的某些谓词的计算成本比其他谓词要便宜得多，而且我一直在寻找一种算法或数据结构，以便更容易找到便宜的谓词，并且可以有效地解释为控制整个表达。我对这种模式的心理标题是“ANDs all way to the root”，即所有祖先都是ANDs的任何谓词都可以解释为控制。
尽管进行了几天的文献搜索，阅读了有关 ROBDD、CNF、DNF 等的信息，但我还是无法从行业中的常见做法到我的特定用例关闭循环。我发现似乎相关的一件事是布尔表达式索引的分析和优化，
但不清楚如何在不自己实现 BE-Tree 数据结构的情况下应用它，因为似乎没有开源实现。
我一直半开玩笑地向我的团队提到，这些天我们将需要一个 SAT 求解器。我想编写一个遍历树并跟踪每个祖先是 AND 还是 OR 的递归算法可能就足够了，但我一直有“这肯定是一个已解决的问题”的感觉。:)
编辑：与几个朋友交谈后，我想我可能有一个解决方案的草图！
- 将表达式转换为联合范式，根据定义，其中每个节点都处于有效的短路位置。
- 使用 Tseitin 算法尽量避免 CNF 变换导致的表达式大小的指数膨胀
- 对于树中的每个AND，按成本升序排序（即最便宜的到左边）
- ？？？
- 利润！^Weval 像往常一样:)