HOME > 研究活動・産学官連携 > ネットジャーナル > ネットジャーナル11

ネットジャーナル11

解説

解説1:二分決定グラフとBDD

「0」「1」で分岐する構造の二分決定木では、3回の分岐で23(2の3乗)=8通りとなる。BDDでは「0でも1でも分岐先が同じ場合は分岐せずに直結する」「共通の行き先を持つ分岐が2個以上あれば1個にまとめる」という圧縮ルールで、これを使うと分岐先の数(=処理数)を大幅に圧縮することができる。

二分決定木BDDの違い
(図1)二分決定木BDDの違い
図2
(図2)
図3
(図3)

本文にもどる

解説2:ZDD(Zero-suppressed BDD=ゼロサプレス型二分決定グラフ)

湊教授が1993年に考案したBDDの一部を改良した新しいデータ構造。大規模なデータを表現するのに適しており、VLSI論理設計の他、データベース解析や確率推論計算などに利用されている。この理論はアルゴリズム研究の第一人者であるドナルド・エルビン・クヌース博士の著書『The Art of ComputerProgramming Vol.4』の中で紹介された。クヌース博士の著書に数十ページにわたって詳しく紹介されたことは日本人初の快挙。

「著書のページ」
(写真1)「著書のページ」

本文にもどる

図4
(図4)

本文にもどる

ページの先頭へ