離散アルゴリズムの品質保証技術に関する調査と新しい展開
【研究分野】情報学基礎
【研究キーワード】
離散アルゴリズム / 離散最適化 / 品質保証 / 近似アルゴリズム / オンラインアルゴリズム / 確率アルゴリズム / 量子アルゴリズム / 計算量理論
【研究成果の概要】
最近のIT社会の大規模化と多様化に伴って、従来から常識のように言われていた正確な計算を速く実行するというパラダイムが必ずしも実情に合わなくなってきている。現実的な時間内に限られたメモリ量で問題を解決することは依然として重要であるが、それだけではなく、非確実性をいかに扱うかが主要な課題になっている。したがって、正確さや決定性を犠牲にしても高速に近似最適解を得る、スケーラビリティを重視した情報処理技術が重要になっている。しかし、単純な発見的手法等に頼ったアルゴリズムでは、計算量のメリットと犠牲のトレードオフがまったく分からない場合が多い。本プロジェクトでは、アルゴリズムの品質保証のため、競合比や近似度といった新しい尺度の調査を行った。
具体的には、近似計算、オンライン計算、確率計算(含む量子計算)、通信効率の高い計算、安全性の高い計算、メタヒューリスティックス等の要素技術の調査を行った。この調査の方向性を定めるために主要なメンバーによる2回の会合を開き、また調査報告と討論のために全研究分担者による全体会議を1回開催した。この他、電子メールによる意見の交換を常時行い、アルゴリズム設計において、工学的なアプローチのもとでの厳密性のある総合的な品質保証技術へのパラダイムシフトが必要であることを示した。また、以下の3種類のアプローチによる研究の必要性をまとめた。(1)杜会的評価基準による利用者にとって分かりやすい評価モデルの研究。(2)与えられたモデルの元での計算限界(下限)を証明する限界研究。(3)実際にアルゴリズムを設計して評価尺度の上限を示すことによる最適アルゴリズム構築研究。これらは密接に関連するため、組織を横断する形での緩やかな班組織により研究者が連帯して研究を推進する必要がある。
【研究代表者】