- 著者
-
鈴木 拡
湊 真一
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション (ISSN:09135685)
- 巻号頁・発行日
- vol.109, no.54, pp.1-7, 2009-05-19
- 参考文献数
- 11
- 被引用文献数
-
1
二分決定グラフ(BDD)は,論理関数のグラフ表現であり,大規模な論理関数データでも比較的コンパクトなデータ構造として表現できる.さらに,BDDの特殊な型であるゼロサプレス型BDD(ZDD)は組合せ集合データの表現・処理に適しており,情報科学における様々な問題に応用できる.その一つの例が制約充足問題である.制約充足問題を解くために多くのアルゴリズムが考案されているが,その一方で,解集合の解析や新たな制約を加えて別の制約充足問題を解くということは,また別の問題として残っている.そこで,BDDまたはZDDで解全体を同時に表現することで,それらを効率よく行う方法を述べる.本稿では,古くから親しまれてきたペントミノパズルを取り上げ,これを制約充足問題として定式化した上でBDDとZDDに基づいた解法を示す.