効率のよいアルゴリズムの開発｜研究紹介｜研究

グラフのアルゴリズム

いくつかの点と、それらの点の接続関係で与えられるデータのことをグラフと呼びます。たとえば電車の駅と、どの駅とどの駅が線路でつながっているかの情報はグラフで表すことができます。町の住人と、誰と誰が知り合いかという情報もグラフで表されます。このように様々なものがグラフとして表すことができますが、抽象化されたグラフという構造の上で、たとえばある点から別の点への最短経路を求めるアルゴリズムを開発すれば、考えている対象が何かにかかわらずそのアルゴリズムを使うことができます。そこで昔からグラフ上のアルゴリズムは盛んに研究されています。ただ世の中には、どんなグラフでもかならず効率のよい解法が存在するとは限らない問題もたくさん存在します。そこで難しい問題に対して、できるだけ多くのグラフで高速に解ける解法（アルゴリズム）について研究しています。

文字列のアルゴリズム

数の列が与えられたとき（アルゴリズムの世界では数の列と文字列はしばしば同一視されます。文字は文字コードにより数とみなすことができるからです）、その中からいくつかの数を選ぶことを考えます。そのとき選んだ数が、もとの列の中で小さい順に並んでいる場合、選んだ数の列を増加部分列と呼びます。この増加部分列の中で一番長いものを見つけたいという問題が最大増加部分列問題です。最大増加部分列問題はパソコンに保存された２つのファイルの違いを見つけるプログラムに使われたり、ゲノムの解析に用いられたりするとても重要な問題で、様々な研究があります。私はこの問題を一般化した問題や、アルゴリズム、関連する話題についても研究を行っています。

メモリの効率化

最近ではアルゴリズムの高速化の研究と並行して、使用するメモリ量の少ないアルゴリズムについての研究も行っています。近年では当たり前のようにビッグデータが活用されていますが、たとえばハードディスクいっぱいに詰まったデータに対して従来のアルゴリズムを用いようとすると、メモリが足りなくなって計算を行うことができなくなってしまうことがあります。そこで、アルゴリズムの高速性はなるべくそのままで、使用するメモリ量の少ないアルゴリズムの開発を目指しています。