プロジェクト

groupA01

計算機科学アプローチによる
組合せ遷移の展開アルゴリズムの自動生成に向けて

MISSION

組合せ遷移に対する「アルゴリズム的メタ定理」を構築することにより,組合せ遷移アルゴリズムの自動生成を目指す.

組合せ遷移に限らず,アルゴリズム開発の第一歩は「事例研究」として始まる.すなわち,解きたい個々の問題に対し,新たな手法を開発して,その問題に特化したアルゴリズムを構築する.そのような事例研究を積み上げていくと,時に「よく似た」アルゴリズムが開発されることがある.対象とする問題こそ違うものの,そこで使われる手法が本質的には同じアルゴリズムである.すると反対に「どういう問題であれば,この手法は有効なのか?」という「アルゴリズム手法の本質」に迫る問いが生まれる.これが,アルゴリズム的メタ定理の研究である.したがってメタ定理は,事例研究の積み重ねから,アルゴリズム手法を「統一された設計技法」へと昇華する研究といえる.

組合せ遷移に対するアルゴリズム開発は,2013年頃から急速に進展し,今ではアルゴリズム理論の著名な国際会議に採択されることも珍しくなくなった.とはいえ,事例研究の積み重ねは未だ十分とはいえず,アルゴリズム的メタ定理の研究もあまり進んでいない.計画研究A01班では,組合せ遷移の未解決問題に挑戦することで事例研究を積み重ねながら,その先に,組合せ遷移に対するアルゴリズム的メタ定理の構築を目指して,研究を進めていく.