2009年5月19日
BDD/ZDDを用いたペントミノパズルの解の列挙
電子情報通信学会技術研究報告. COMP, コンピュテーション
- ,
- 巻
- 109
- 号
- 54
- 開始ページ
- 1
- 終了ページ
- 7
- 記述言語
- 日本語
- 掲載種別
- 出版者・発行元
- 一般社団法人電子情報通信学会
二分決定グラフ(BDD)は,論理関数のグラフ表現であり,大規模な論理関数データでも比較的コンパクトなデータ構造として表現できる.さらに,BDDの特殊な型であるゼロサプレス型BDD(ZDD)は組合せ集合データの表現・処理に適しており,情報科学における様々な問題に応用できる.その一つの例が制約充足問題である.制約充足問題を解くために多くのアルゴリズムが考案されているが,その一方で,解集合の解析や新たな制約を加えて別の制約充足問題を解くということは,また別の問題として残っている.そこで,BDDまたはZDDで解全体を同時に表現することで,それらを効率よく行う方法を述べる.本稿では,古くから親しまれてきたペントミノパズルを取り上げ,これを制約充足問題として定式化した上でBDDとZDDに基づいた解法を示す.
- リンク情報
-
- CiNii Articles
- http://ci.nii.ac.jp/naid/110007338420
- CiNii Books
- http://ci.nii.ac.jp/ncid/AN10013152
- ID情報
-
- ISSN : 0913-5685
- CiNii Articles ID : 110007338420
- CiNii Books ID : AN10013152
- identifiers.cinii_nr_id : 1000010374612