|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 分 ： [ぶん, ふん] 1. (n,n-suf,pref) (1) part 2. segment 3. share 4. ration 5. (2) rate 6. (3) degree 7. one's lot 8. one's status 9. relation 10. duty 1 1. kind 12. lot 13. (4) in proportion to 14. just as much as 1 ・ 決 ： [けつ] 【名詞】 1. decision 2. vote ・ 図 ： [ず] 1. (n,n-suf) figure (e.g., Fig 1) 2. drawing 3. picture 4. illustration
二分決定図（にぶんけっていず、Binary Decision Diagram、BDD）とは、ブール関数を表現するのに使われるデータ構造である。二分決定グラフあるいは（基本的には二分木のような構造であることから）二分決定木と呼ぶこともある。 == 概要 == ビット(0あるいは1)の列を入力として、最終的に1つの 0/1 を返すような関数、すなわちブール関数は、環状構造を持たない有向グラフで表現できる。ノードのうちの大部分は決定ノードと呼ばれ、それぞれの決定ノードは2つの行き先、つまり2つの子ノードを持つ。決定ノードには「入力の何ビット目を読め」というラベルが与えられている。従って、与えられたブール関数の答えを得るには、指示に従って入力のビット列を読みながら、ビットが0か1かによって、分岐点ごとに2つの行き先のどちらかを選べば良い。さらに、このような決定を十分な回数行うと、2つの終端ノード、0終端あるいは1終端のどちらかに行き当たる。その場合には、どちらの終端が得られたかを、ブール関数の答えとして返す。 例えば下の左図は、ブール関数 を表す二分決定木と真理値表を示している。この木構造で、引数群の値の組み合わせに対応した関数の値はグラフを上から順にたどっていけば決定できる。従って、 の関数値は、まず から点線()をたどって ノードに行き、続いて実線() をたどって へ、最後に実線()により1終端ノードにたどり着く。従って, の値は 1 ということになる。 開始ノードから降りていったときに現われる変数の順序が（どの経路でも）同じである二分決定図を「順序付き; ordered」BDDと呼ぶ。また、特定の規則によって簡約した二分決定図を「既約; reduced」BDDと呼ぶ。左の図に示した二分決定木は、簡約することで規約な右の図へと変換される。簡約のための規則は以下のとおりである。 * あるノードが子ノードとを持つ時、同様にとを子ノードに持つような、機能的に重複したノードは存在しない。 * 2つの子ノードが同じノードであるような、決定に関して意味のないノードは存在しない。 一般的に、BDDと言えば「既約な順序付き二分決定図」を指すのが普通である（既約で順序付きであることを強調する場合は ROBDD と記されることもある）。ROBDD の利点は特定の関数を最も簡単に表現している点にある。この特徴から、ブール関数を論理回路化するのに使われたり、機能の等価性の判定に使われたりする。 根のノードから1終端ノードまでの経路は、そのBDDが表現しているブール関数が真(1)となる変数群の値を経路で表している（経路上に現われない変数の真理値は関数の値に影響しない）。このとき、あるノードから HIGH （子）ノードへの経路を通る場合、そのノードに対応する変数の値が 1 であることを示し、LOW ノードの場合は 0 であることを示す。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「二分決定図」の詳細全文を読む 英語版ウィキペディアに対照対訳語「 Binary decision diagram 」があります。 スポンサード リンク
|