二分決定図

二分決定図

二分決定図（にぶんけっていず、Binary Decision Diagram、BDD）とは、ブール関数を表現するのに使われるデータ構造である。二分決定グラフあるいは（基本的には二分木のような構造であることから）二分決定木と呼ぶこともある。
ブール関数は、1つの出発点がある、有向で非環状のグラフ理論 グラフで表現できる。2つの終端ノード（0終端と1終端）以外のノードは決定ノードであり、決定ノードにはブーリアン変数が1つ対応していて、2つの子ノードを持つ。2つの子ノードは、ブーリアンの値が0の場合の HIGH ノードと1の場合の LOW ノードである。根のノードから降りていったときに現われる変数の順序が（どの経路でも）同じである二分決定図を「順序付き; ordered」BDDと呼ぶ。また、次の規則に従って簡約化した二分決定図を「既約; reduced」BDDと呼ぶ。

『フリー百科事典ウィキペディア日本語版』 2008/07/07/22/08、URL: http://ja.wikipedia.org/