二分決定図 - Wikipedia二分決定図（にぶんけっていず、英: Binary Decision Diagram, BDD）や二分決定グラフ（にぶんけっていグラフ）とは、ブール関数を表現するのに使われる有向非巡回グラフである。グラフに既約していない物は二分決定木（binary decision tree）と呼ぶ。 概要[編集] ビット(0あるいは1)の列を入力として、最終的に1つの 0/1 を返すような関数、すなわちブール関数は、閉路のない有向非巡回グラフで表現できる。ノードのうちの大部分は決定ノードと呼ばれ、それぞれの決定ノードは2つの行き先、つまり2つの子ノードを持つ。決定ノードには「入力の何ビット目を読め」というラベルが与えられている。従って、与えられたブール関数の答えを得るには、指示に従って入力のビット列を読みながら、ビットが0か1かによって、分岐点ごとに2つの行き先のどちらかを選べば良い。さらに、このような決
