研究テーマ

身近にもたくさん存在する最適化問題を解くアルゴリズム理論の基礎研究

一定の条件を満たす組合せの中から，最もよい組合せを選ぶような問題は，アルバイトのシフト，ルートの検索，スケジューリングなど私たちの身近にもたくさんあります．上嶋研究室では，こうした「組合せ最適化問題」において効率のよいアルゴリズムのあり方を探っています．
(研究室紹介サイト WHO'S LAB)

組合せ最適化問題の計算複雑さ解明とアルゴリズム設計

我々の身近には，よくよく目を凝らすと本質的には組合せ的な構造の振舞いに支配されている問題が数多くあることに気付くでしょう． 例えば，効率的な資材の切り出し，人員配置，ルート検索，スケジューリングなど問題解決のために要件を満たすパターンを組合せ的に選ぶ問題はいくらでも挙げられます． 事実，与えられた制限を満たすような組合せ集合の中から一番よい組合せを選ぶ組合せ最適化問題は，計算機科学の分野はもちろん，オペレーションズ・リサーチ，システム工学，さらには経営学，経済学，社会科学に至る広範な領域において様々な形をとって現れてきます． これらの問題の中には，計算機の処理速度が飛躍的に向上したとしても現実的な時間ではとても歯が立たない問題が我々の身近に数多く存在する一方で，一見効率的には解けないような問題であっても，それらの持つ組合せ的な性質を理解し計算効率の良いアルゴリズムにより華麗に解決を見る問題も多数含まれています． そのため，組合せ最適化問題の持つ本質的な計算複雑さを明らかにし，問題が内在する数学的な構造を用い工夫を凝らした効率の良いアルゴリズムを設計することは，実社会で登場する様々な問題に対し理論的な後ろ盾を与えることであり，ひいては社会的貢献に繋がります．

当研究室では，組合せ構造の表現に多用されるグラフ・ネットワークについての組合せ最適化問題に関する計算複雑さの解明および最適化アルゴリズムの設計に力を入れており，また組合せゲーム・パズルの計算複雑さの証明，手番による優位性の評価，必勝手順の設計などにも取り組んでいます．
(情報工学専攻のパンフレットから抜粋)