研究 / Research

グラフ理論で最適な計算法を考える

私が得意としているのは離散数学、さらにその中でも「グラフ理論」と「理論計算機科学」といった領域の研究をしています。グラフ理論は、点と点同士を結ぶ線からなるグラフに関する研究で、実社会とは関わりがなさそうに思われがちですが、携帯電話の周波数割り当てや、カーナビのアルゴリズムの最適化など、身近なところに応用されています。理論計算機科学は、例えばチューリングマシンのように理論上の計算機を想定して、さまざまな計算（アルゴリズム）の可能性を考えるものです。 「離散グラフ理論」という分野の研究者は日本では少ないのですが、自分としては世界に引けを取らない研究をしているつもりです。

物や情報を送る最適な経路を証明する

はじめから社会貢献を意識して数学の理論を研究しているわけではありませんが、実社会のニーズに応えることには興味があります。その１つがネットワークです。平面上に複数の始点と終点があって、その間を結んで、できるだけ多くの物や情報が送れるようにしたい。他と交差しないようにすべての始点と終点を結ぶ経路があるかどうか、またどのくらいの物量が送れるのかを知りたい、とします。
始点と終点の組が一組だけならすごく簡単な話ですが、複数組あると、直感的に経路を作れてもそれが最適かどうかを数学的に証明するのは難しい。場合によっては、うまく経路が設定できない場合もあります。こういう配置だったら OK で、こっちはだめ、という判定がなかなかできない。このようなときに数学の理論が役立ちます。

数学の知識を駆使して計算量を減らす

この問題の例では、始点・終点が密に集中している部分があるとすると、その部分は、全体の経路が設定できるかどうかという判定には影響がなくなってきます。影響がないと数学的に確認できれば、そういう部分は除いて、影響のあるところだけで計算・判定をすればよい。つまり入力されるデータの構造を見て、判定に不要な部分を捨てていくとうまく計算できることがあるのです。
こうしてデータをクリーニングすることで、「最適ではないがかなり良い」経路を見つけるための作業量（計算量）を大きく減らすこともできるようになります。巨大なネットワークの中で、できるだけ多くの物流や情報を流そうとした場合に、どんな経路を作るか、全部の点を結ぶ必要があるのかどうか、といったことがわかるようになるのです
グラフ理論の歴史は古いのですが、新しい発見がまだあります。例えば 50 年近く前に提示された「強理想グラフ予想」が解かれたのはつい最近でした。この予想は数学的に面白い問題ですが、もとはと言えば、情報理論の研究から出てきたもので、そのまま手つかずだったわけです。このように、数学的な理論が必要になるテーマはまだたくさんあります。そういったテーマを研究したいと考えています。

PDFをダウンロード

[NII研究紹介動画]グラフ理論で最適な計算法を考える

リンク

• [NII Today] 未来の情報科学の達人を育てる
• [NII SEEDS] アルゴリズムが世界を変える─未来のIT産業を支える若き人材を育成
• [NII SEEDS] ビッグデータ数理国際研究センターの設立-巨大グラフとビッグデータ数理-
• [書籍] これも数学だった！？　カーナビ、路線図、SNS - 情報研シリーズ16

ニュースリリース

• 光を使って難問を解く新しい量子計算原理を実現〜量子ニューラルネットワークの開発〜
• ビッグデータ数理国際研究センター／応用数理分野における世界最大の学会で研究機関紹介ビデオに登場