離散構造を有する列挙問題の解法に関する研究

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

近年の情報化技術の発達により,人工知能,データーマイニング,オペレーションズリサーチなど様々な分野で『離散構造を有する列挙問題』が解かれるようになってきた.しかしながら,これまで提案されているアルゴリズムのほとんどは,発見的なものであり,列挙の速度,領域,列挙の順序(例えば,重要なものから列挙する)などのアルゴリズムの精度保証がなく,問題例によっては,莫大な計算時間,領域が必要になる.本研究では,まず,離散構造を有する列挙問題の構造解析を行うことにより,様々な列挙問題の計算の複雑さを明らかにするとともに,効率的なアルゴリズム開発を行う.このアルゴリズム開発においては,(A)(理論的な)精度の保証,(B)汎用性の高さ,(C)実用性,に重点をおく.また,高速化のために,ランダム化手法,並びに,並列,分散計算等の手法についても考察する。このような研究を遂行することで,離散構造をもつ列挙問題に関する基礎理論構築を目指す.本年度は,離散最適化分野において重要な役割をもつマトロイドに関連するいくつかの列挙問題に対する計算量を明らかにすると共に,高速なアルゴリズム開発に成功した[L.Khachiyan, E.Boros, K.Borys, K.Elbassioni, V.Gurvich, K.Makino : On the Complexity of Some Enumeration Problems for Matroids. SIAM Journal on Discrete Mathematics 19(2006)966-984],[L.Khachiyan, E.Boros, K.Borys, K.Elbassioni, V.Gurvich, K.Makino : Generating Cut Conjunctions and Bridge Avoiding Extensions in Graphs. ISAAC 2005:156-165].