情報処理学会 第80回全国大会講演要旨

ZDDは組合せ集合を効率よく圧縮して索引化するデータ構造である.グラフといくつかのトポロジー制約が与えられたとき,それを満たす部分グラフを全列挙するZDDを高速に構築する「フロンティア法」という技法が最近注目されている.フロンティア法の課題として,生成するZDDサイズが変数順序に大きく左右されることが挙げられる.従来のフロンティア法では,前処理で変数順序を固定するヒューリスティックな順序付けが用いられてきた.しかし,ZDDサイズは構築が進むまで不明であり,必ずしも最適に近い順序が得られるわけではない.そこで本研究では,構築途中のZDD幅を考慮しつつ,並行して良い変数順序を求める手法を提案する.