著者

湊 真一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)

巻号頁・発行日

vol.105, no.72, pp.31-38, 2005-05-13

被引用文献数

6

---

二分決定グラフ(BDD)は, 大規模な論理関数データを効率よく表現する技法として広く利用されている.BDDの中でも, ゼロサプレス型BDD(ZBDD)と呼ばれるデータ構造は, 大規模な組合せ集合を非明示的に列挙し効率よく演算処理するのに適しており, 情報科学における様々な問題に適用できる.我々は, 数式により組合せ集合の演算を記述し, これをZBDDを用いて計算するプログラム「VSOP」を開発した.VSOPは単なる組合せ集合演算だけでなく, 集合の各要素に整数値(係数あるいは重み)を定義し, 加減乗除や大小比較等の算術演算を含む数式を処理できることを特長とする.本稿では, VSOPの内部データ構造や演算方法, データ表示形式について述べ, いくつかの応用例を示す.