Research on Integrated Techniques of Enumeration and Optimization Based on Discrete Structure Manipulation Systems

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

本年度の研究実績の概要は以下の通りである。(i) 列挙と最適化の統合的アルゴリズム技法の研究と体系化：グラフの最短路問題のように、組合せ問題のアイテムにコストが定義されているときに、コスト総和が所与の閾値以下となるような実行可能解を列挙することは、多くの実用的な応用を持つ汎用的で重要な問題である。このような一般的なコスト制約つき組合せ問題に対して、ZDDを用いて大量の解を高速に全列挙する「区間メモ化技法」を前年度に考案したが、これを実装し実験により有効性を確認した。本研究結果は研究代表者自らが筆頭著者として国内研究会および国際ワークショップで発表した。(ii) 離散構造処理系の基盤アルゴリズムの実装とソフトウェアの整備：BDD/ZDDをベースとする離散構造処理系のアルゴリズムは、原則として「BDDパッケージ」と呼ばれるソフトウェアライブラリとして公開されている。前年度からに開発している高速列挙アルゴリズムの実装もこのパッケージに追加されており、改良を進めている。(iii) 関連分野との連携および応用分野への発展：本研究が呼び水となり、学術変革(A)「アルゴリズム基盤」および学術変革(B)「組合せ遷移」が昨年度後半に相次いで採択され、理論計算機科学を中心とする研究者コミュニティの発展が期待される。学術変革(A)(B)および各分野の第一線で活躍する研究者と研究協力者として定期的に会合し連携を深めた。