アルゴリズム設計 －コスト・費用・時間節約のための情報処理手法－

● 研究テーマ

• ❖①組合せ問題に対する効率の良いアルゴリズムの設計と解析
• ❖②計算複雑さに関する研究

● 分野

情報学基礎

● キーワード

近似アルゴリズム、 オンラインアルゴリズム、 乱択アルゴリズム、 並列アルゴリズム、 計算複雑さの理論

● 実施中の研究概要

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

● 今後進めたい研究

①離散的アルゴリズム
大学等の研究機関との共同研究を希望します（技術相談、共同研究）。
②計算量
大学等の研究機関との共同研究を希望します（技術相談、共同研究）。
③計算限界
大学等の研究機関との共同研究を希望します（技術相談、共同研究）。

● 研究室ホームページ

• http://theory.ces.kyutech.ac.jp/~miyano/index-j.html