6

二分決定図の背景については、wikipedia の BDD を参照してください。

最も簡単な方法は、BDT (二分決定木) を作成し、次の 2 つのルールに従って縮小することです。
- 同形サブグラフをマージします。
- 2 つの子が同型であるノードを削除します。
しかし、BDD に比べて BDT が非常に巨大になる可能性がある大きな問題が 1 つあります。最初に BDT をビルドせずに BDD をビルドする方法はありますか?

4

3 に答える 3

6

Andersenの pp. 16-17の(Mkノードの作成) およびBuild(BDD の構築) アルゴリズムを使用します。私はしばらく BDD を扱っていませんが、HまたはTのいずれかがハッシュ テーブルであるべきだと思います。安全のために、両方にハッシュテーブルを使用してください。

于 2010-11-02T11:13:26.947 に答える
1

BDD を構築する方法は、構築しようとしているブール関数を表す式の解析ツリーからです。

つまり、(A+B).(C+D) の BDD が必要な場合は、まず (A+B).(C+D) をツリーに解析します。

   .
  / \
 + +
/ \ / \
あいうえお

次に、BDD を再帰的に構築します。2 つの BDDS の AND と OR を形成できるメソッドと、基本ケース (単一変数 BDD) が必要です。

これは、論理回路でも同様に機能します (ツリーではなく解析 DAG として表示します)。

BDD に関するこれらのメモでは、AND と OR を実装する方法と、物事を効率的に機能させるために必要なハッシュテーブルについて説明しています: http://bit.ly/cuClGe

于 2010-11-02T15:18:43.837 に答える
-1

正しく読みたい場合は、Knuth を読んでみてください。

https://www-cs-faculty.stanford.edu/~knuth/fasc1b.ps.gz

より正確には、その本の章の14ページから始まるアルゴリズム「R」は、OPに対する正確かつ完全な答えです。

ここに画像の説明を入力

全体として、Knuth の本の章は非常に優れた詳細な参考文献であり、たまたま (RO)BDD について書いたものであり、BDD を真剣に実装しようとしている人にとっては非常に幸運です。

于 2018-05-24T19:59:28.027 に答える