圧縮索引構造を用いた汎用的かつ実用的な多様な解の発見アルゴリズム

点击翻译按钮获取中文摘要

本研究では実世界の最適化問題に対し，多様な解を列挙する実用的なアルゴリズムを開発する.最適化問題では通常，アルゴリズムは単一の最適解を出力する.しかし実用上は，モデルに書ききれない曖昧な制約があり，最適解1つでは不十分なことがある.そこで多様な解を列挙できれば有用だが，多くの問題はNP困難であることが知られている.そこで本研究では，大規模な組合せ集合を圧縮して表現できる索引構造を用いて汎用的かつ実用的なアルゴリズムの開発を目指す.本研究の成果は理論と実用のギャップを埋めるという学術的意義に加え，Web検索，推薦 システム，データベースといった幅広い分野での応用が期待される.本年度は，多様性最大化に対するゼロサプレス型二分決定グラフ（ZDD）を用いた近似手法の検討を行った．解の集合がZDDで表されている場合，線形重み最大の解を見つけることはZDDのサイズに対する線形時間でできる.この性質を用いて，解の集合を表すZDDが与えられたとき，ZDDのサイズに対する多項式時間で動作する多様性最大化に対する制度保証付き近似アルゴリズムを設計した.ZDDのサイズは最悪の場合は入力サイズに対して指数的に大きくなるが，実用的な多くの場合では十分圧縮が効くので，このアプローチは多様性最大化に対する統一的かつ効率的な近似手法になりうると考えている.研究成果について，国内会議および国際会議での発表を検討している．