高性能近似アルゴリズムの設計法に関する研究

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

グラフ問題や組合せ問題のような離散構造をもつ問題のほとんどはNP完全(最適化問題の場合はNP困難という)であり,現在の計算機では計算時間が膨大になり手に負えない問題である.しかし,たとえNP困難であっても,計算機を用いてなんとか解かなければならない離散最適化問題が情報処理の現場ではますます増えている.たとえば,ORの分野では,より大規模なネットワーク上での資源割当て問題やスケジューリング問題を解かなければならない.また,人工知能の分野では推論処理のような高度な計算を要求する問題がつぎつぎと発生している.このような現実を踏まえ,たとえ求まる解が最適ではなくとも,それに十分近いことを保証できる近似アルゴリズムの設計論が今日の重要な研究テーマとなっている.本研究では、グラフの彩色問題と集合被覆問題を中心とした代表的離散最適化問題に対する高性能近似アルゴリズムを開発するとともに,これまでに提案されている近似アルゴリズムを設計手法の立場から調査・分類し一般的設計法を構築する.今年度の研究成果は以下のようである.最小重み木状被覆問題と頂点彩色問題に対して近似アルゴリズムを設計した.また重みつき集合被覆問題及び集合多重被覆問題に関して成果を得た.この他,センサーネットワークのプロトコルや無線ネットワークの初期化アルゴリズムについて研究を行った.