algorithm - 反转乘积 bool 和的快速算法

Question

我正在尝试实现一个非常非常快的 bool 表达式引擎。我用它来表示非常大的状态空间中的状态，所以我需要它每秒处理尽可能多的操作。在这个引擎的最基础是产品的总和。不过，我遇到了优化 NOT 运算符的问题。例如，如果我有一个包含 N 个最小项的乘积总和，其中每个最小项都有大约 M 个变量，那么尝试反转它会创建 M^N 个最小项，然后使用浓缩咖啡算法对其进行简化。如果我在逆运算期间间歇性地运行 espresso 算法，我可以稍微加快速度并节省一些内存，但这还不够。我怀疑我是第一个遇到这个问题的人，我已经尝试进行研究，但我似乎无法找到一种有效的方法来做到这一点。

谁能指出我正确的方向？

Answer 1

所以，我发布这个问题已经 5 年了。在最近重新发现它之后，我意识到我犯了大罪。从那时到现在，我发现了一个相当快的算法来完成这项工作，并且再也没有回来回答这个问题。问题是我丢失了所有相关文档。嗯...在这里。如果我重新发现来源，我会更新这个答案。

https://github.com/nbingham1/boolean/blob/a0f21eb1808dbcf86a3360ea85ab4eae15f5bf49/boolean/cover.cpp#L1055

编辑:找到来源

PLA 合成的多值逻辑最小化，作者 Richard L. Rudell，第 58 页

https://apps.dtic.mil/dtic/tr/fulltext/u2/a606736.pdf

这使用广义香农展开，递归地补充展开的两侧，并使用简化的启发式合并补充。