logo标签列表

算法 - 最小化布尔表达式

pythonalgorithmmathboolean
10
我正在尝试编写一段代码，可以将布尔表达式的长度缩减到最小，因此该代码应尽可能减少表达式中的元素数量。目前我卡住了，需要一些帮助=[
规则如下：布尔表达式中可以有任意数量的元素，但仅包含AND和OR运算符以及括号。
例如，如果我传入一个布尔表达式：ABC+BCD+DE，则最佳输出将是BC(A+D)+DE，与原始表达式相比，它节省了2个单位空间，因为两个BC组合成了一个。
我的逻辑是，我将尝试找到表达式中出现最频繁的元素，并将其分解出来。然后我递归调用该函数来对分解后的表达式执行相同的操作，直到完全分解。
然而，如何在原始表达式中找到最常见的元素？也就是说，在上面的例子中，如何找到BC？似乎我必须尝试所有不同的元素组合，并找到每个组合在整个表达式中出现的次数。但这听起来非常幼稚。
有人能给出有效完成此操作的提示吗？甚至一些关键词我可以在Google上搜索。
@Li-aungYip 是的，我也考虑过这个问题，但那只是在使用铅笔和纸的情况下对吧？我该如何编写计算机代码来实现呢？ - turtlesoup
有了括号，BC（A+D）+DE和ABC+BCD+DE的长度相同。我现在正在解决同样的问题。这个链接在代数化简部分稍微讲了一下。我认为它只是对公式应用布尔恒等式进行传递。 - douggard
6个回答
7
你所需要的是一种最小化布尔函数的方法。这在芯片设计社区中尤其受到关注。用于你目的的技术是Quine-McCluskey算法，或者你可以像Li-aung Yip在评论中建议的那样使用卡诺图。
哎呀，你比我快了12分钟。 :) - Li-aung Yip
我已经了解了一些关于Quine-McCluskey算法的知识，它说随着输入规模的增大，内存和时间会呈指数级增长。我正在寻找一种能够处理数百个输入（表达式中的文字）的方法...那么还有其他方法吗？或者我误解了如何使用Quine算法？谢谢！ - turtlesoup
1
@Jimster：我强烈建议你阅读链接的维基百科文章，该文章讨论了这个问题。维基百科文章提到，大布尔表达式可以通过“Espresso”缩小器进行启发式处理，其缩放比Quine-McCluskey更好。 - Li-aung Yip
正如@Li-aungYip所说，处理大型表达式有一些启发式方法，而Espresso是探索这些方法的好工具包。但总的来说，你想做的事情在计算上非常困难。电子设计自动化（负责所有芯片设计工具）行业已经在这个和类似领域工作了很长时间，但没有快速解决方案，精确算法在变量数量上呈指数级增长。 - Alex Wilson
4

很抱歉我还没有了解所有这些酷炫的算法，但是你问到如何找到共同因子，所以我想到了以下方法：

import itertools
def commons(exprs):
    groups = []
    for n in range(2, len(exprs)+1):
        for comb in itertools.combinations(exprs, n):
            common = set.intersection(*map(set, comb))
            if common:
                groups.append(
                            (len(common), n, comb, ''.join(common)))
    return sorted(groups, reverse=True)

>>> exprs
['ABC', 'BCD', 'DE', 'ABCE']

>>> commons(exprs)
[(3, 2, ('ABC', 'ABCE'), 'ACB'),
 (2, 3, ('ABC', 'BCD', 'ABCE'), 'CB'),
 (2, 2, ('BCD', 'ABCE'), 'CB'),
 (2, 2, ('ABC', 'BCD'), 'CB'),
 (1, 2, ('DE', 'ABCE'), 'E'),
 (1, 2, ('BCD', 'DE'), 'D')]

该函数返回按以下方式排序的列表：
  1. 共同因子的长度
  2. 具有此公共因子的项数

请注意，保留了HTML标签。
感谢提供找到公因数的算法，我将尝试在此基础上构建一个布尔转换器。目前现有的算法在我的情况下难以实现 =] - turtlesoup
我认为仅仅因式分解是不够的，你必须知道何时消除表达式。上面的例子可以比使用单个因子进一步简化得多。它可以首先转换为：B(AC+CD+ACE) + DE，然后可以转换为BC(A+D+AE) + DE。然后注意到A+AE是多余的，所以最终得到BC(A+D) + DE。 - speedplane
3
3
使用Quine-McCluskey算法来最小化布尔表达式。它在功能上等同于Karnaugh图方法，但更适合在计算机上实现。
1
很不幸，大部分给出的建议可能并不能真正满足@turtlesoup的需求。@turtlesoup要求一种方法来最小化给定布尔表达式的字符数。大多数简化方法并不以字符数为简化的重点。在电子学中，当涉及到最小化时，用户通常希望使用最少的门（或零件）。这并不总是会导致表达式在“长度”方面更短——大多数情况下确实如此，但并非总是如此。事实上，有时表达式在长度方面可能会变得更大，尽管从电子学角度来看它可能更简单（需要较少的门来构建）。
boolengine.com是我所知道的最好的数字电路布尔简化工具。它不允许数百个输入，但允许14个，这比大多数简化工具要多得多。
在处理电子学时，简化程序通常会将表达式分解为乘积和形式。因此，表达式'(ab+)'cd变为'c+b+a+d'。这个"简化"结果需要更多的字符来打印作为表达式，但从电子学的角度来看，更容易构建。它只需要一个4输入OR门和3个反相器（4个部件）。而原始表达式需要2个AND门、2个反相器和1个OR门（5个零件）。
在将@turtlesoup的示例提供给BoolEngine后，它显示BC(A+D)+DE变为E+D+ABC。这是一个更短的表达式，并且通常会是这样。但当然并不总是这样。
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接