Researcher file no.1
優れたアルゴリズムに隠された理論に迫る
現実の問題を解くアルゴリズムを目指す
岩田 陽一
情報学プリンシプル研究系 助教
コンピュータに賢く計算をさせる「アルゴリズム」。コンピュータの将来はアルゴリズムにかかっているといっていいだろう。しかし、その開発においては、理論的には難しいとされる問題が、現実には解けてしまうなど未知の要素が多い。岩田は、この理論と現実のギャップを埋め、理論に裏付けられたアルゴリズムの開発を目指している。
アルゴリズムとの出合いは驚きの連続
「皆さん筆算はできますね。九九しか知らなくても、大きな桁の掛け算や割り算ができます。あれがアルゴリズムなのです」。岩田陽一は自分が研究している「アルゴリズム」について人に話すとき、まず、こう切り出す。一気に、身近なものに感じてもらえるからだ。アルゴリズムとは、簡単な計算しかできないコンピュータに複雑な問題を解かせるための計算方法のことだ。岩田は、このアルゴリズムの理論と現実の間に生じているギャップを埋める研究をしている。
コンピュータの世界に入るきっかけとなった出来事は、岩田にとって驚きの連続だった。高校時代、ゆとり教育で何をやってもいいと与えられた「総合的な学習の時間」を使い、当時、興味を持ち始めていたプログラミングでオセロのAIをつくった。「高校生の私にも自分よりも強いモノをつくれてしまったことに驚きました」。大学に入ってからは、競技プログラミングの大会を目指して勉強を始めた。「世の中には、計算にものすごく時間がかかる"遅いプログラム"というものがあるのです。それは衝撃的でした」と当時、自分が書いたプログラムのことを思い出して笑う。こうしてコンピュータを賢く動作させるプログラムには、優れたアルゴリズムが必要だということを知り、その面白さにのめり込んでいった。この時の体験の数々は、仲間たちとの共著としてまとめられ［1］、コンピュータの世界を目指す後進たちのバイブルになっている。
理論と現実のギャップを"理論的"に埋めたい
大学院の頃から、未知のアルゴリズムに取り組む研究へ向かっていった。「ある計算をするアルゴリズムを開発しようとして行き詰まったとき、それを打開できるかどうかは、ミレニアム問題を解くのと同じくらい難しいと理論的にわかっています」。ミレニアム問題とは、米国のクレイ数学研究所が2000年に100万ドルの懸賞金をかけた7つの問題のことだ。それほどにアルゴリズム開発は難しいということだが、実際には、多くの難しいはずのアルゴリズムが実現されている。理論と現実の間にギャップが生じるのは、理論が一般化された事象を扱うのに対して、現実はそれにいろいろな条件が加わってくるからである。
一例として、岩田がその改良に成功した、2点間の最短距離を問う「最短路クエリ問題」を解くためのアルゴリズムがある。距離が最短となるルートを、通ることのできるすべてのルートから探索するのでは途方もない時間がかかってしまう。しかし、実社会では出発地と目的地が離れていれば、移動には鉄道を使わなくてはならない。この条件によってすべてのルートを考える必要はなくなり、出発地から最寄りの駅までと、目的地と最寄りの駅までという、部分に分けたより狭い範囲内のルートを探索すればいいことになる。こうして計算量を大幅に減らすことができる。
このように次々に現実的なアルゴリズムを開発する岩田だが、一方で「現実に解けるのだからいい」とは考えていない。どういう条件が加われば、難問が一転して現実的に解ける問題へと変わるのか、理論的に解き明かしたいと考えている。「NP困難問題」を解くために広く用いられている「分枝限定法」という方法をより効率的に使うための条件の一部をすでに明らかにしており、理論計算機科学のトップ国際会議であるFOCS 2018に採択されるなど高い評価を受けている。「理論と現実がほんの少しですが歩み寄った感覚ですね」。
その先には、理論に裏付けられた、現実の問題を解くことのできるアルゴリズムの開発が見据えられている。
[1] 「プログラミングコンテストチャレンジブック〜問題解決のアルゴリズム活用力とコーディングテクニックを鍛える〜」（マイナビ／2010年）
