7

ブール式の LENGTH を最小限に抑えることができるコードを書き出そうとしているので、コードは式の要素数をできるだけ少なくする必要があります。今、私は立ち往生していて、助けが必要です =[

ルールは次のとおりです。ブール式には任意の数の要素を含めることができますが、AND 演算子と OR 演算子、および角かっこのみが含まれます。

たとえば、ブール式 ABC+BCD+DE を渡すと、最適な出力は BC(A+D)+DE になり、2 つの BC が 1 つに結合されるため、元のユニット スペースと比較して 2 つのユニット スペースが節約されます。

私の論理は、式の中で最も頻繁に出現する要素を見つけて、それを因数分解しようとするというものです。次に、完全に因数分解されるまで、関数を再帰的に呼び出して、因数分解された式に対して同じことを行います。しかし、元の表現で最も一般的な要素を見つけるにはどうすればよいでしょうか? つまり、上記の例では、BC? 要素のさまざまな組み合わせをすべて試して、各組み合わせが式全体に現れる回数を見つける必要があるようです。しかし、これは本当に素朴に聞こえます。2番

誰かがこれを効率的に行う方法についてヒントを与えることができますか? Googleで検索できるいくつかのキーワードでも十分です。

4

6 に答える 6

5

あなたが探しているのは、ブール関数を最小化する方法です。これは、特にチップ設計コミュニティにとって興味深いものです。目的に使用される手法はQuine-McCluskey アルゴリズム です。または、Li-aung Yip がコメントで提案したようにKarnaugh Mapsを使用できます。

于 2012-07-04T08:05:18.287 に答える
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. この公約数を持つ項の数
于 2012-07-04T08:28:50.347 に答える
2

ブール式を最小化するには、 Quine-McCluskeyアルゴリズムを使用します。機能的にはカルノー マップ アプローチと同等ですが、コンピューター上での実装にははるかに適しています。

于 2012-07-04T08:17:38.983 に答える
0

カルノー図を実装するアプレットは次のとおりです。http ：//www-ihs.theoinf.tu-ilmenau.de/~sane/projekte/karnaugh/embed_karnaugh.html

式を入力するか、真理値表に記入することができます。

于 2012-10-23T12:57:44.057 に答える