2011 年 4 巻 3 号 p. 224-230
二分決定グラフ(BDD: Binary Decision Diagram)は,論理関数を効率良く表現するデータ構造の一種である.BDD に関する処理技法は主にVLSI 設計技術の分野で1990 年代に発展したものであるが,近年ではデータマイニングや知識発見の分野でも効果的に活用されるようになってきている.中でも,ゼロサプレス型BDD(ZDD: Zero-suppressed BDD)と呼ばれるBDD の変化形は,データベース解析の多くの問題で見られるような「疎な組合せの集合」を扱う場合に特に効果的である.本稿では,離散構造を処理するための基本的な技術として,BDD,ZDD をはじめとする種々の決定グラフの演算処理系を解説し,それらの効果的な応用について述べる.最後に,我々が現在進めている「離散構造処理系プロジェクト」の概要を紹介する.