膨大な組み合わせが存在して正解が導けない　
難解な「組み合わせ最適化問題」を解くには

どの道をどう通れば最も速く目的地に着けるか。カーナビのルート検索は、多くの組み合わせから最適なものを求める「組み合わせ最適化問題」の一つ。現実問題を数理モデルとして定式化し、計算によって答を導きます。
渡邊研究室では、「組み合わせ最適化問題」の基礎理論を研究しています。

アリがエサを運ぶ最短ルートを見つけ出す
生態をシミュレーションしたアルゴリズム

現実の問題をグラフとしてモデル化し
条件に合った最適な解を見つける

またグラフ理論やネットワーク理論を使った「組み合わせ最適化問題」も研究テーマの一つ。「組み合わせ最適化問題」には、頂点を枝で結ぶグラフに数値データを付加する「ネットワーク理論」を応用するものが数多くあります。

たとえば、基本的な「ネットワーク理論」の一つである最大流問題は、始点から終点まで最大量を流す組み合わせを求める方法ですが、水や交通、電気や通信などの流れを扱うさまざまなシステムの構築や解析に広く応用できます。

また、頂点や枝を塗り分ける彩色問題の理論を使って、無線通信においてチャネルを効率的に割り当てる方法を導くことも。現実の問題をグラフやネットワークに抽象化して数式化することで、コンピュータで解ける問題にしていくものです。