2020年4月 - 2023年3月
離散問題のモデリングとアルゴリズム ~部分問題からのアプローチ~
日本学術振興会 科学研究費助成事業 基盤研究(C) 基盤研究(C)
離散問題(離散最適化問題、離散決定問題、離散列挙問題など)はオペレーションズ・リサーチやデータサイエンスにおいてきわめて重要な応用を持つ。本研究は離散問題に関する以下の問いに対する答えを、事例研究を通じて模索するものである。(a) 離散問題をどのように部分問題に分解して解けばよいのか。(b) 部分問題を解くためのアルゴリズムをどのように統合して、元の問題を解くのに用いればよいのか。(c) ある問題について効果的なアプローチを、ほかの関連問題をどのように適用すればよいのか。(d) 一連のアルゴリズムをどのように実装すればよいのか。
2021年度の成果およびその意義は以下のとおりである。(1)要素の集合とその部分集合族から成る対を集合システムという。合流システムと呼ばれる集合システムに関してある列挙問題を考え、逆探索に基づいた多項式遅延アルゴリズムを提案した。その列挙問題とは、各要素にアイテム集合が付された合流システムが与えられ、共通アイテム集合に関して極大な部分集合をすべて列挙することを問うものである。この問題はデータマイニングにおける相関ルール抽出問題の一般化である。また様々なクラスの部分グラフ列挙問題を含み、その中にはこれまで多項式遅延アルゴリズムが知られていなかったクラスも含まれる。この成果の最大の意義は、多項式遅延で列挙可能な集合システムの範囲を押し拡げ、理論の発展に寄与したことである。一連の成果をまとめた論文を、離散アルゴリズムに関する著名誌の一つであるAlgorithmica上で発表した。(2) NP困難問題に対する欲張り法に用いる評価関数を強化学習によって獲得するための研究が近年盛んに進められている。その多くは深層学習を用いたものだが、高価な計算コストと過剰学習が懸念される。そこでより簡素な学習モデルを用いてこれを実現するべく、モデルと実装の整備を進めた。
2021年度の成果およびその意義は以下のとおりである。(1)要素の集合とその部分集合族から成る対を集合システムという。合流システムと呼ばれる集合システムに関してある列挙問題を考え、逆探索に基づいた多項式遅延アルゴリズムを提案した。その列挙問題とは、各要素にアイテム集合が付された合流システムが与えられ、共通アイテム集合に関して極大な部分集合をすべて列挙することを問うものである。この問題はデータマイニングにおける相関ルール抽出問題の一般化である。また様々なクラスの部分グラフ列挙問題を含み、その中にはこれまで多項式遅延アルゴリズムが知られていなかったクラスも含まれる。この成果の最大の意義は、多項式遅延で列挙可能な集合システムの範囲を押し拡げ、理論の発展に寄与したことである。一連の成果をまとめた論文を、離散アルゴリズムに関する著名誌の一つであるAlgorithmica上で発表した。(2) NP困難問題に対する欲張り法に用いる評価関数を強化学習によって獲得するための研究が近年盛んに進められている。その多くは深層学習を用いたものだが、高価な計算コストと過剰学習が懸念される。そこでより簡素な学習モデルを用いてこれを実現するべく、モデルと実装の整備を進めた。
- ID情報
-
- 課題番号 : 20K04978
- 体系的課題番号 : JP20K04978