講演抄録/キーワード |
講演名 |
2012-06-21 09:30
組合せ問題の解を列挙索引化するZDD構築アルゴリズムの汎用化 ○川原 純(JST/北大)・湊 真一(北大/JST) COMP2012-12 |
抄録 |
(和) |
多くの組合せ問題の解全体は集合族として表現可能である.集合族を表すデータ構造として,Zero-suppressed Binary Decision Diagram (ZDD) が用いられる.解全体を表すZDDが構築できれば,組合せ問題の解全体を列挙して出力することは容易であり,さらに,解の効率的な保持,条件を指定しての検索,一様サンプリング等,解の活用が可能となる.我々が提案するフロンティア法は,組合せ問題の解全体を表現するZDDを直接的に構築する手法であり,複数の研究者によって個々の問題に対して提案されている手法を汎用化したものである.フロンティア法が適用可能な問題には様々な種類があるが,本稿では,それらを分類,整理して,統一的な視点から述べる. |
(英) |
There are various combinatorial problems whose solutions can be represented as a family of sets. The Zero-suppressed Binary Decision Diagram (ZDD) is often used as the data structure for a family of sets. Once a ZDD which represents all solutions of a combinatorial problem has been constructed, it is easy to enumerate and output all solutions one by one by using the ZDD. Moreover, it is possible to efficiently store all solutions, find solutions satisfying desired conditions, and sample a solution uniformly at random. The frontier method, to which we generalize the methods proposed by several researchers for individual problems, is the way to construct such a ZDD directly. We can apply the frontier method to many kinds of problems. In this paper, we categorize these problems and discuss them generally. |
キーワード |
(和) |
BDD / ZDD / フロンティア法 / 列挙問題 / / / / |
(英) |
BDD / ZDD / Frontier Method / Enumeration Problem / / / / |
文献情報 |
信学技報, vol. 112, no. 93, COMP2012-12, pp. 1-7, 2012年6月. |
資料番号 |
COMP2012-12 |
発行日 |
2012-06-14 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2012-12 |