文献

J-GLOBAL ID：201202255564308914   整理番号：12A1052361

組合せ問題の解を列挙索引化するZDD構築アルゴリズムの汎用化

Generalization of ZDD Construction Algorithms for Enumerating and Indexing the Solutions of Combinatorial Problems

著者 (4件)： 川原純 (JST-ERATO) ,  川原純 (北大 大学院情報科学研究科) ,  湊真一 (JST-ERATO) ,  湊真一 (北大 大学院情報科学研究科)
資料名： 電子情報通信学会技術研究報告  (IEICE Technical Report (Institute of Electronics, Information and Communication Engineers))
巻： 112  号： 93(COMP2012 12-25)  ページ： 1-7  発行年： 2012年06月14日 
JST資料番号： S0532B  ISSN： 0913-5685  資料種別： 会議録 (C)
記事区分： 短報  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 多くの組合せ問題の解全体は集合族として表現可能である。集合族を表すデータ構造として,Zero-suppressed Binary Decision Diagram(ZDD)が用いられる。解全体を表すZDDが構築できれば,組合せ問題の解全体を列挙して出力することは容易であり,さらに,解の効率的な保持,条件を指定しての検索,一様サンプリング等,解の活用が可能となる。我々が提案するフロンティア法は,組合せ問題の解全体を表現するZDDを直接的に構築する手法であり,複数の研究者によって個々の問題に対して提案されている手法を汎用化したものである。フロンティア法が適用可能な問題には様々な種類があるが,本稿では,それらを分類,整理して,統一的な視点から述べる。(著者抄録)

シソーラス用語： *組合せ問題 ,  *二分決定グラフ ,  アルゴリズム
準シソーラス用語： *ZDD ,  列挙アルゴリズム

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (11件)：

• KNUTH, D. E. The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1. 2011
• MINATO, S. Zero-suppressed BDDs for set manipulation in combinatorial problems. Proceedings of the 30th ACM/IEEE Design Automation Conference, 1993. 1993, 272-277
• AKERS, S. B. Binary decision diagrams. IEEE Trans. Comput. 1978, 27, 6, 509-516
• BRYANT, R. E. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, C. 1986, 35, 8, 677-691
• 藤田昌宏. 情報処理 (情報処理学会誌). 1993, 584-630

タイトルに関連する用語 (7件)： 組合せ問題 ,  解 ,  索引 ,  ZDD ,  構築 ,  アルゴリズム ,  汎用