研究内容

コンピュータを使って問題を解く（情報を処理する）ための，問題のモデル化と解法アルゴリズム設計に関する研究を行っています．特に組合せ最適化問題を 対象としています．自宅から学校までの「通学手段の組合せ最適化問題」を例に説明します．毎日タクシーで通学すると10分で行けるかもしれませんが，莫大 な費用がかかります．徒歩通学すると費用はかかりませんが，1時間半かかるかもしれません．そこで，自転車，バス，電車などを乗り継ぐことにしたとします．このとき「自転車に乗り，バスに乗り，電車に乗る」「自転車に乗り，バスに乗り，電車に乗らない」「自転車に乗らず，バスに乗り，電車に乗る」などの組合せが考えられ，このような組合せが解の候補となる問題を組合せ問題と呼びます．また，25分以内で通えるという制約条件の下で，最も安価な通学手段を求めるといった問題を組合せ最適化問題と呼びます．組合せ問題の最適解を，コンピュータを使って求めるためには，どういった制約条件があるか，何が目的か（何を最適化したいか）というのを数式として表現して（モデル化），どういう手順で解を求めるか（アルゴリズム設計）ということが必要になります．できるだけ高速なアルゴリズムを設計することが求められます．バスや電車の経路作成や時刻表作成は規模が大きくなっただけで基本的には上の例と同じ問題です．また，企業での生産計画やコスト削減問題なども制約条件や目的が少し異なる組合せ問題で，高速なアルゴリズムが社会活動を向上させることができます．