もし、北海道の札幌から九州の福岡まで、車に乗って行くとすれば、どのような経路で行けば最短で行けるでしょうか？飛行機なら、札幌空港から、福岡空港まで、直線距離を飛ぶだけの事ですが、車で行くとなれば、複数の都市を結ぶ、国道や、高速道路などを乗り継ぐ必要があります。また、電車で行く場合はどうでしょうか？やはり、複数の駅を結ぶ列車を乗り継ぐ必要があるでしょう。このような問題を解く場合には、まず、問題の本質部分だけを取り出します(抽象化、あるいはモデル化と呼びます)。このためにいくつかの拠点(上記の例では、都市や駅であり、ノードと呼びます)と、その拠点を結ぶ線分(上記の例では、道路や路線であり、アークと呼びます)だけを抜き出したものを考えます(図 1 参照)。このノードとその間を結ぶアークだけを取り出したものを「グラフ」と呼びます。そして、このグラフ上で、二つのノードの間の最短の経路を考えるわけです。この例では一つのノード O から他のノードへの最短の経路(個々のアークの長さは同じ場合を想定しています)が矢印の並びとして表示されています。このようなグラフ上の最短経路を求めるという問題は、交通以外にも、社会の至る所で現れ、ものごとの効率化を図るために解く事を求められる、重要な課題になっています。

私の研究は、この最短経路問題をコンピュータを利用して、いかに早く答えを求めるかというコンピュータのアルゴリズムを考える事です。数学といえば、社会とかけ離れた学問という感じがしますが、こんなところで、実は重要な働きをしているという事も知っていただければと思います。

栗野 俊一