代数的決定図

代数的決定図 (ADD)または多端子二値決定図 (MTBDD) は、任意の有限集合 S を終域とするブール関数を記号的に表現するために使用されるデータ構造です。ADD は、縮小順序二値決定図、または文献で一般的に二値決定図 (BDD)と呼ばれるものの拡張であり、その終端ノードはブール値 0 (FALSE) と 1 (TRUE) に限定されません。^{[ 1 ] [ 2 ]}終端ノードは、定数集合 S から任意の値を取ることができます。

ADD はブール関数を表します ${\displaystyle \{0,1\}^{n}}$ADDは、定数の有限集合S、または代数構造の担体です。ADDは、BDDと同様に複数のノードを持つ、根付き有向非巡回グラフです。ただし、ADDはBDDとは異なり、集合Sの要素である終端ノードを2つ以上持つことができます。

ADD は、関数の終域を拡張することにより、ブール関数またはベクトルブール関数と見なすこともできます。${\displaystyle f:\{0,1\}^{n}\to Q}$と${\displaystyle S\subseteq Q}$そして${\displaystyle card(Q)=2^{n}}$ある整数 n に対して、 ADD にはブール代数の定理、特にブールの展開定理が適用されます。^{[ 1 ]}

各ノードはブール変数でラベル付けされ、2つの出力エッジを持ちます。1つは変数の評価がTRUEであることを表す1エッジ、もう1つはFALSEであることを表す0エッジです。

ADDは、BDD（または縮小順序付きBDD）と同じ削減ルールを採用します。

• 同型な部分グラフをマージし、
• 2つの子ノードが同型であるノードをすべて削除する。

ADDは、特定の変数順序に従って正規化されます。

ADDは、その余因子に応じて行列で表すことができます。^{[ 2 ] [ 1 ]}例えば、関数を考えてみましょう。${\displaystyle f(x,y)}$ブール変数について${\displaystyle x}$そして${\displaystyle y}$値を取る${\displaystyle \{0,1,2,3\}}$定義： ${\displaystyle f(0,0)=1,\quad f(0,1)=2,\quad f(1,0)=3,\quad f(1,1)=0.}$

この関数は行列として表すことができる ${\displaystyle M={\begin{bmatrix}1&2\\3&0\end{bmatrix}},}$ 行は${\displaystyle x\in \{0,1\}}$列は以下に対応します${\displaystyle y\in \{0,1\}}$。

ADD表現では、ルートノードは次のようにラベル付けされます。${\displaystyle x}$、そしてその出力エッジは補因子に対応します${\displaystyle f_{x=0}(y)}$そして${\displaystyle f_{x=1}(y)}$は、それぞれ低（0）エッジと高（1）エッジと呼ばれ、行列の1行目と2行目で表される。各補因子は、さらに に関して分解される。${\displaystyle y}$これにより、行列の要素に対応する終端ノードが得られます。したがって、 ADDで使用されるシャノン分解は、行列を再帰的に部分行列に分割することに対応します。

ADDは、最初に疎行列乗算と最短経路アルゴリズム（ベルマン・フォード法、反復二乗法、フロイド・ウォーシャル法）に実装されました。^{[ 1 ]}

• 二項決定図
• ゼロ抑制決定図