ゼロ抑制決定図

FをZDDとする。vをそのルートノードとする。すると：

1. v = ⊥ の場合、他のノードは存在できず、F は空の集合 Ø を表します。
2. v = ⊤ の場合、他のノードは存在せず、F は空集合{ Ø } のみを含む族を表します。これを単位族と呼び、で表します。
3. v に 2 つの子ノードがあるとします。v0 を LO ノード、v1 を HI ノードとします。Fi を vi を根とする ZDD で表されるファミリーとします。これは帰納法の証明によって示すことができます。すると F は次のファミリーを表します。

   $$\displaystyle F_{0}\cup \{\alpha \cup \{v\}\mid \alpha \in F_{1}\}}$$

LOブランチは、 vを含まないFの集合として表すことができる。 $${\displaystyle F_{0}=\{\alpha$$ :\alpha \in F,v\notin \alpha \}}

そして、HI ブランチは、 vを含む F の集合として定義されます。 $${\displaystyle F_{1}=\{\alpha \setminus \{v\}:\alpha \in F,v\in \alpha \}}$$

• 
  図 3
• 
  図 4
• 
  図 5
• 
  図 6

図3：家族${\displaystyle \emptyset \cup \{\emptyset \cup \{2\}\}=\{\{2\}\}}$これを${\displaystyle e_{2}}$基本族。基本族は次の形式から構成されます。${\displaystyle \{\{n\}\}}$、およびは、で表されます。${\displaystyle e_{n}}$。

図4：家族${\displaystyle \{\emptyset \}\cup \{\emptyset \cup \{2\}\}=\{\emptyset ,\{2\}\}}$

図5：家族${\displaystyle \{\{2\}\}\cup \{\emptyset \cup \{1\}\}=\{\{1\},\{2\}\}}$

図6：家族${\displaystyle \{\{1\}\cup \{2\}\}=\{\{1,2\}\}}$

ここでは、ZDDの基本的な操作について説明します。ZDDの操作はBDDの操作とは若干異なるためです。

Empty() は ø (空集合) を返します

Base() は {0} を返します。

Subset1(P, var) は、 var = 1などの P の部分集合を返します。

Subset0(P, var) は、 var = 0となるような P の部分集合を返します。

Change(P, var)は、varが反転したときにPを返します。

Union(P, Q) は (${\displaystyle P\cup Q}$）

Intsec(P, Q) は (${\displaystyle P\cap Q}$）

Diff(P, Q) は (${\displaystyle PQ}$）

Count(P) は${\displaystyle \left\vert P\right\vert }$（要素数）

ZDDには、従来のBDDでは必須の演算であるNOT演算がありません。その理由は、全体集合Uを定義しないと補集合Pを計算できないためです。ZDDでは、PはDiff(U, P)として計算できます。

仮定する${\displaystyle \left\vert P\right\vert =\left\vert P_{0}\right\vert +\left\vert P_{1}\right\vert }$再帰的にZDD内のセット数を計算することで、54個の要素からなるファミリーから34番目のセットを取り出すことができます。ランダムアクセスは高速であり、セットの配列に対して可能なあらゆる操作をZDD上で効率的に実行できます。

湊によると、ZDD の上記の操作は、元の BDD と同様に再帰的に実行できます。アルゴリズムを簡単に説明すると、Getnode(top, P0, P1)変数 top と 2 つのサブグラフ P0 および P1 のノードを返す手順を定義します。各ノードを一意に保つために、uniq-table と呼ばれるハッシュテーブルを使用できます。ノードの削除と共有は、のみによって管理されますGetnode()。

Getnode ( top , P0 , P1 ) {if ( P1 == ø ) return P0 ; /* ノード除去 */P = uniq - table内で( top 、P0 、P1 )を持つノードを検索します。Pが存在する場合は、Pを返します。/*ノード共有 */P = ( top 、P0 、P1 )を持つノードを生成する。ユニークテーブルにPを追加する。Pを返す;}

これを用いることでGetnode()、他の基本的な演算を次のように表現できます。

サブセット1 ( P 、var ) {if ( P . top < var ) return ø ;if ( P . top == var ) return P1 ;/* if (P.top > var) */return Getnode ( P . top , Subset1 ( P0 , var ), Subset1 ( P1 , var ));}Subset0 ( P , var ) {if ( P . top > var ) return P ;if ( P . top == var ) return P0 ;/* if (P.top < var) */return Getnode ( P . top , Subset0 ( P0 , var ), Subset0 ( P1 , var ));}変更（P 、var ）{if ( P . top < var ) return Getnode ( var , ø , P );if ( P . top == var ) return Getnode ( var , P1 , P0 );/* if (P.top > var) */return Getnode ( P . top , Change ( P0 , var ), Change ( P1 , var ));}ユニオン( P 、Q ) {if ( P == ø ) return Q ;if ( Q == ø ) return P ;もし( P == Q )ならばPを返す。if ( P . top > Q . top ) return Getnode ( P . top , Union ( P0 , Q ), P1 );if ( P . top < Q . top ) return Getnode ( Q . top , Union ( P , Q0 ), Q1 );/* if (P.top == Q.top) */return Getnode ( P.top , Union ( P0 , Q0 ), Union ( P1 , Q1 ) ) ;}Intsec ( P , Q ) {if ( P == ø ) return ø ;if ( Q == ø ) return ø ;もし( P == Q )ならばPを返す。if ( P . top > Q . top ) return Intsec ( P0 , Q );if ( P . top < Q . top ) return Intsec ( P , Q0 );/* if (P.top == Q.top) */return Getnode ( P.top , Intsec ( P0 , Q0 ), Intsec ( P1 , Q1 ) ) ;}Diff ( P , Q ) {if ( P == ø ) return ø ;if ( Q == ø ) return P ;if ( P == Q ) return ø ;if ( P . top > Q . top ) return Getnode ( P . top , Diff ( P0 , Q ), P1 );if ( P . top < Q . top ) return Diff ( P , Q0 );/* if (P.top == Q.top) */return Getnode ( P.top , Diff ( P0 , Q0 ), Diff ( P1 , Q1 ) ) ;}カウント( P ) {if ( P == ø ) return 0 ;if ( P == { ø }) return 1 ;return Count ( P0 ) + Count ( P1 );}

これらのアルゴリズムは、最悪の場合、変数の数に対して指数関数的な時間を要します。しかし、BDDと同様の方法で最近の操作の結果を記憶するキャッシュを使用することで、パフォーマンスを向上させることができます。キャッシュは、同等のサブグラフに対する重複実行を防ぎます。重複がなくなることで、アルゴリズムはグラフのサイズに比例した時間で動作できるようになります（図9および図10参照）。

ZDDは、英語の5文字の単語を表すために使用できます。たとえば、 Stanford GraphBaseのWORDSセット（サイズ5757）などです。これを行う1つの方法は、関数を検討することです。${\displaystyle f(x_{1},...,x_{25})}$それは、5つの数字が${\displaystyle (x_{1},...,x_{5})_{2}}$、${\displaystyle (x_{6},...,x_{10})_{2}}$、...、${\displaystyle (x_{21},...,x_{25})_{2}}$英語の単語の文字をエンコードします。${\displaystyle a=(00001)_{2}}$、...、${\displaystyle z=(11010)_{2}}$。 例えば、 ${\displaystyle f(0,0,1,1,1,0,1,1,1,1,0,1,1,1,1,0,0,1,1,0,1,1,0,0,x_{25})=x_{25}}$英語の単語 (GOOFY) をエンコードするのは、${\displaystyle x_{25}}$1. 25個の変数を持つ関数はZ(f) = 6233個のノードを持ち、5757個の単語を表現するには悪くない数です。バイナリツリー、トライ木、ハッシュテーブルと比較すると、ZDDは単純な検索には最適ではないかもしれませんが、部分的にしか指定されていないデータや、キーに近似的に一致するだけのデータを取得するのに効率的です。複雑なクエリも容易に処理できます。さらに、ZDDはそれほど多くの変数を必要としません。実際、ZDDを使用することで、5文字の単語を疎関数として表現できます。${\displaystyle F(a_{1},...,z_{1},a_{2},...,z_{2},...,a_{5},...,z_{5})}$26×5 = 130 個の変数があり、変数${\displaystyle a_{2}}$例えば、2番目の文字が「a」かどうかを判定します。「crazy」という単語を表すには、Fを次の条件で真にすることができます。${\displaystyle c_{1}=r_{2}=a_{3}=z_{4}=y_{5}=1}$そして他のすべての変数は0である。したがって、Fは5757個の部分集合からなる族と考えることができる。${\displaystyle \{w_{1},h_{2},i_{3},c_{4},h_{5}\}}$など。これらの 130 個の変数では、ZDD のサイズ Z(F) は実際には 6233 ではなく 5020 になります。Knuth によると、BDD を使用した B(F) の同等のサイズは 46,189 であり、Z(F) よりかなり大きくなります。理論とアルゴリズムは似ているにもかかわらず、この問題では ZDD は BDD をかなり大きな差で上回ります。したがって、ZDD を使用すると、BDD では負担が大きすぎる特定のクエリを実行できます。部分集合の複雑なファミリーは、基本的なファミリーから簡単に構築できます。特定のパターンを含む単語を検索するには、ZDD 上のファミリー代数を使用して計算できます。 ${\displaystyle (F/P)\sqcup P}$ここでPはパターンであり、例えば${\displaystyle a_{1}\sqcup h_{3}\sqcup e_{5}}$。

ZDDは、無向グラフにおける単純な経路を表すために使用できます。例えば、3×3のグリッド（図11参照）の左上隅から右下隅まで、どの地点も二度通らずに移動する経路は12通りあります。

これらのパスは、図 13 に示す ZDD で表すことができます。この図では、各ノードmn は「パスにmとnの間の弧が含まれているか」という質問を表しています。たとえば、13 と 12 の間の LO ブランチは、パスに 1 から 3 への弧が含まれていない場合、次に問うべきことは、パスに 1 から 2 への弧が含まれているかどうかであることを示しています。ノード 12 から LO ブランチが出ていないということは、1 から 3 に行かないパスはすべて 1 から 2 に行かなければならないことを示しています。（次に問うべきことは、2 と 4 の間の弧についてです。）この ZDD では、ZDD のノード 13、36、68、および 89 の HI ブランチを取ることで、図 12 の最初のパスが得られます（単に ⊥ に向かう LO ブランチは省略されています）。図 13 の ZDD は決して重要ではないように見えるかもしれませんが、グリッドが大きくなるにつれて、ZDD の利点が明らかになります。例えば、8×8のグリッドの場合、角から角への単純経路の数は789,360,053,252通りになります（Knuth）。これらの経路は、ZDD（Zero-Dark Data System）を用いて33,580個のノードで図示することができます。

単純経路の現実世界の例として、ランダル・ブライアントは次のように提案しました。「アメリカ大陸を車で巡り、すべての州都を訪れ、各州を一度だけ通過したいとします。総距離を最小にするには、どのルートを選べばよいでしょうか？」問題は、隣接する都市を結ぶエッジのサブセットを選択し、総長が最小のハミルトン経路を形成することです。このグラフのすべてのハミルトン経路は、メイン州オーガスタ（ME）で開始または終了する必要があります。カリフォルニア州（CA）から開始するとします。CAからMEへのすべての経路を特徴付けるZDDを見つけることができます。クヌースによれば、このZDDはわずか7850個のノードしか持たず、CAからMEへの単純経路が正確に437,525,772,584個存在することを効果的に示しています。エッジの数によって、生成関数は

${\displaystyle 4z^{11}+124z^{12}+1539z^{13}+...+33385461z^{46}+2707075z^{47}}$;

そのため、そのようなパスの中で最も長いものはハミルトンパスであり、そのサイズは 2,707,075 です。この場合、ZDD は単純なパスとハミルトンパスに対して効率的です。

チェス盤上のマス目を表す64個の入力変数を定義します。各変数は、そのマス目にクイーンが存在するか存在しないかを示します。

• 特定の列において、「1」となる変数は1つだけです。
• ある行において、「1」となる変数は1つだけです。
• 特定の対角線上では、1つの変数のみが「1」であるか、またはどの変数も「1」ではない。

この問題はOBDDを構築することで解決できますが、ZDDを使用する方が効率的です。8クイーン問題に対するZDDの構築には、S1からS8までの8つのステップが必要です。各ステップは次のように定義できます。

S1: クイーンを最初の行に配置するすべての選択肢を表します。

S2: 最初のクイーンを侵害しないように、2列目にクイーンを配置するすべての選択肢を表します。

S3: 前のクイーンに違反しないように、3行目にクイーンを配置するすべての選択肢を表します。

…

S8: 前のクイーンに違反しないように、8行目にクイーンを配置するすべての選択肢を表します。

S8 の ZDD は、8 クイーン問題のすべての潜在的な解で構成されます。この特定の問題では、キャッシュによってアルゴリズムのパフォーマンスを大幅に向上させることができます。キャッシュを使用して重複を回避すると、図 10 に示すように、基本操作 (上記で定義) のみを使用する場合と比較して、N クイーン問題の処理速度を最大 4.5 倍向上させることができます。

ナイトの巡回問題は歴史的に重要な意味を持つ。ナイトのグラフは、チェス盤のマス目を表すn ^{2 個の頂点を持つ。辺はナイトの合法的な動きを表す。ナイトは盤上の各マス目をちょうど 1 回ずつ訪れることができる。オラフ・シュレーアー、M. レビング、}インゴ・ウェゲナーは、この問題を、つまり盤上で、グラフの各辺にブール変数を割り当てることによって解決した。すべての辺を指定するために合計 156 個の変数が使用される。問題の解は 156 ビットの組み合わせベクトルで表現できる。ミナトによれば、すべての解に対する ZDD の構築は直接解決するには大きすぎる。分割統治法の方が簡単である。問題を盤の 2 つの部分に分割し、部分空間で ZDD を構築することにより、各解が 64 個の辺を含むナイトの巡回問題を解くことができる。しかし、グラフはあまり疎ではないため、ZDD を使用する利点はそれほど明らかではない。

高橋ら（N. Takahashi et al.）は、OBDDを用いて複数の故障をシミュレーションする手法を提案した。この演繹的な手法では、故障セットを主入力から主出力へ伝達し、主出力における故障を捕捉する。この手法は単一キューブセット式を用いるため、ZDDの方が効率的である。単一キューブセット計算におけるZDDの最適化は、ZDDがVLSI CADシステムの開発やその他多くのアプリケーションにおいて有用であることを示唆している。