我正在尝试实现一个非常快速的布尔表达式引擎。我将使用它来表示非常大的状态空间中的状态，因此需要尽可能地处理每秒钟的操作次数。在这个引擎的基础上是一种积和形式。然而，我在优化NOT运算符方面遇到了问题。例如，如果我有N个minterms的积和形式，其中每个minterm大约有M个变量，那么尝试反转它将创建M^N个minterm，然后使用espresso算法简化。如果在反向操作期间间歇性地运行espresso算法，则可以稍微加速并节省一些内存，但这还不够。我怀疑我不是第一个遇到这个问题的人，我已经尝试过研究，但似乎找不到有效的方法。请问有谁能指点一下吗？
2个回答
3
所以，自从我发布这个问题已经过去了5年。最近重新发现它后，我意识到我犯了致命的错误。在那时和现在之间的某个时刻，我找到了一个相当快速的算法来完成这个任务，但从未回来回答这个问题。问题是我已经失去了所有相关的文档。好吧...就是这样。如果我重新发现来源，我会更新这个答案。
编辑：已找到来源
用于PLA合成的多值逻辑最小化，作者为Richard L. Rudell，第58页。
这使用广义香农展开，递归地补充展开的两侧，并使用简化启发式合并补充部分。- Ned Bingham
0
您可以使用O(n+m)的时间复杂度来实现它，其中
answer = ( x1 OR x2 OR .. xn ) AND ( y1 OR y2 OR .. ym )
但是你可以优化这个过程，以便在最终答案不是1的情况下找到答案。
answer = ( x1 OR x2 OR .. xn ) LOGICAL-AND ( y1 OR y2 OR .. ym )
在 LOGICAL-AND 中，如果当前值为 0，它将以 O(n+1) 的时间复杂度返回 0
您还可以将此过程转换为集合操作
DEFINE X = { X1, X2, .. Xn }
DEFINE Y = { Y1, Y2, .. Ym }
ANSWER = X ∈ 1 AND Y ∈ 1
并像这样进行优化
IF X ∈ 1
THEN RETURN Y ∈ 1
ELSE RETURN 0
平均而言，您会得到 Time = i + j，其中
i = position of left-most 1 in X
j = position of left-most 1 in Y
最坏情况下需要 O(n+m)
000..001, 000..000
000..001, 000..001
- Khaled.K
1
这篇文章已经发布四年了，但我最近才回来看。你的意思是建议我将反转结果保留在合取范式（CNF）中吗？假设该运算符是某个更大算法的一部分，将结果保留在CNF中只会将复杂性转移到布尔运算符上，这些运算符必须与CNF和DNF进行接口交互。 - Ned Bingham
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
(x1&y1)|(x2&y2)|...|(xn&yn)。否定后，长度为2^n。 - n. m.n个变量，则使用这n个变量编写的函数的真值表中将有2^n个条目。我相当确定，如果您限制自己仅以乘积和形式表示函数，那么总会有一些分配方式，使得乘积和形式必须具有2^n个最小项。但是，如果您不限制自己使用乘积和形式呢？也许这可以带来更好的替代方案。 - Apiwat Chantawibul