現在の研究・目標
私の研究のメインテーマは、アルゴリズムの高速化です。特に、理論的な計算量を下げるにはどのような技術が必要か、という点を解明していきたいと考えています。いくつかの分野に注目し、それらの分野の各問題がどのような技術を用いて高速化できるかを研究し、その分野のアルゴリズムに対する一般的な高速化技術、及び知見を得たいと考えています。また、それらの高速化技術を用いて、周辺分野のアルゴリズム、あるいは他の分野、現実問題に対するアルゴリズムの高速化も行いたいと考えています。
現在、日本でも最適化アルゴリズムの研究はたくさん行われています。いろいろな問題が解かれていて、「どのような問題にはどのような技術を用いたアルゴリズムが有効であるか」という、解こうとしている問題をベースにした知見は多くの分野で得られています。しかし、「どのようなアルゴリズムが、どのような問題に有効か」という、アルゴリズムの性質に関する知見はあまり得られていません。そこで、こういったアルゴリズムの面からの最適化問題の研究、というものを進めていきたいと考えています。
以下に、私が取り組んでいるアルゴリズムの分野について、どのような姿勢で取り組んでいるのか、何を目標にしているのか、どこまで達成できているのかを述べておきます。
列挙アルゴリズム
列挙アルゴリズム (enumeration algorithm) とは列挙問題を解くアルゴリズムのことをいいます。数学的に述べると、与えられた集合の要素をすべて見つけ、出力する問題のことをいいます。具体的には、例えば、与えられた自然数の集合の部分集合で、合計がある値を超えないようなものを列挙する問題、与えられた与えられたグラフの全域木を列挙する問題、線形不等式系で与えられた多面体の端点を列挙する問題などです。
列挙問題は、とても基礎的な問題です。組合せ最適化問題の実行可能解集合や、部分集合族の要素、組合せ多面体の面など、およそ基本的な組合せ、グラフ理論の問題全てに関する列挙問題が研究されています。部分集合族や組合せ多面体の性質を調べたり、最適化を行うために、列挙アルゴリズムは基本的なツールとなるのです。分枝限定法などの組合せ最適化問題の解法は、列挙アルゴリズムをベースにしていますので、いろいろな問題に対して、列挙問題の性質を調べたり、アルゴリズムの開発をしておく必要があるのです。そうすれば、アルゴリズムを開発する手間は減少します。組合せ最適化の研究をする場合にも、いちいち列挙の部分について研究を行い、証明をする必要はなくなり、理論的な面での研究の前進のための助けになるのです。
現在、列挙アルゴリズムは、多くの列挙問題に対して開発されています。また、列挙アルゴリズムを構築する手法についても、いくつかの研究があります。これらの手法を用いて作られたアルゴリズムは、複雑な技法や証明を用いず、明快に記述することが出来ます。一部、問題の自明でない構造を用いて複雑なアルゴリズムを構築している例もありますが、多くのアルゴリズムは比較的単純に作れるのです。構築手法を前提とせず、目の前の１つの問題に対して、アルゴリズムを構築する、という一本の独立した研究をしている論文もあります。しかし、列挙アルゴリズムは他の分野の研究のツールとなる、という点も考慮に入れると、アルゴリズム研究全体のためには、問題の性質やアルゴリズムの形態によって、上手に列挙アルゴリズムの分類を行い、簡潔に解説し、他の分野からの参照をなるべく簡単に行えるようにするべきでしょう。
列挙アルゴリズムにも、高速なものと、そうでないものがあります。出力した解１つあたり、つまり１つ解を見つけるのにかかる時間が、問題の大きさに対してそれほど大きくない（入力多項式）ものと、最悪の場合、指数時間かかってしまうものとがあります。前者のアルゴリズムを出力線形アルゴリズム、あるいは多項式遅延といいます。組合せ的な列挙問題に対して、後者の、つまり解１つ当たり指数時間を要するアルゴリズムを作るのは簡単です。しらみつぶしすべての組合せをチェックするアルゴリズムを作ればいいのですから。ですので、「列挙問題に対して出力線形アルゴリズムを作る」というのが、１つ、面白い研究テーマなのです。この種の研究は40年ほど前から続けられているので、1部の難しい問題を除いて、もはやおおよその問題については、研究され尽くしています。
私の研究テーマである「アルゴリズムの高速化」という観点からすると、列挙アルゴリズムには２つの面白みがあります。1つは、指数時間アルゴリズムしか開発されていない問題に対して、実用上、つまり平均的に高速なアルゴリズムをいかにして作るか、というものです。単純な方法では非常に時間のかかる、極小被覆集合の列挙などの問題も、他の技法を用いてアルゴリズムを作ると、実用上は出力線形に近い時間で動くアルゴリズムができるものがあります。どのようなタイプの問題が、どのような技術で高速化できるのか、そういった知見をまとめあげたいと考えています。
2つ目は、出力多項式のアルゴリズムの計算量をどれだけ小さくすることができるか。つまり、解１つあたりにかかる計算時間を、どれだけ計算量の意味で小さくできるか、というものです。文字列アルゴリズムやグラフアルゴリズムなどの他の離散アルゴリズムの分野でも、このような、計算量を小さくする研究が行われています。これらの研究で使われた技術が、列挙アルゴリズムにも適用できることはできるのですが、それだけで十分な高速化ができるわけではありません。グラフアルゴリズムなどは、1つの解を探すために、反復を行ったり、解を収束させたりし、そういった動きに対する効率的な計算量解析方法を用いて計算量を算定しています。対して、列挙アルゴリズムはたくさんの解を見つけるために、いわば発散して行くような動きをするので、列挙専用の高速化技術・計算量解析方法が必要となるのです。通常のアルゴリズムを高速化するためには、あまり役に立たないような技術が、列挙に対しては効果的に働く、そういった、面白みがあるのです。
理論的な高速化を行ったアルゴリズムは、実用上のアルゴリズムに比べて遅くなってしまったり、アルゴリズムが複雑になってしまうこともあります。しかし、「このような条件が達成できれば、理論的にも速くなる」という知見が得られますので、例えば「このような条件」がたまにしか破られないよう、ヒューリスティックアルゴリズムを作れば、実用上はかなり高速であろう、という知見が得られます。どのようなヒューリスティックを用いれば速くなるか、実用上のアルゴリズムに対する知見も得られるわけです。
このような面から研究を進めて、列挙アルゴリズムの、理論面・実用面からの高速化に対する技術の系統立てを行えるような、そんな研究をしたいと考えています。
私の今までの研究で、有名な部分グラフ列挙問題（全張木、マッチングなど）およそ50ほどのうち、10個ほどに対して、既存のアルゴリズムよりも高速なアルゴリズムの開発に成功しています。列挙アルゴリズムに対する一般的な高速化手法、というものも、1つ開発できました。この手法を用いると、既存の技術では高速化できないアルゴリズムを高速化できる場合があります。どのような列挙アルゴリズムに対してこの手法が有効なのか、この高速化手法を使ったアルゴリズムを開発しつつ、調べて行きたいと考えています。
木構造アルゴリズム
木構造アルゴリズム (tree algorithm) は、木構造ネットワークという種類のネットワークに対する最適化、あるいはその他の問題を解くアルゴリズムのことを言います。通常のネットワークに対する NP-haed 問題の多くが、木構造ネットワークでは、多項式時間で解けることが知られています。これは、木構造ネットワークが単純な形をしており、分割統治法や動的計画が効果的に使えるからです。
木構造アルゴリズムは、古くから研究されていて、いろいろな問題に対してアルゴリズムが提案されています。ですので、他の最適化問題の子問題として現れるような問題、現実問題への応用がある問題などは、ほとんど研究され尽くしています。しかし、アルゴリズムの面からの研究、というものは、まだまだ少ないようです。どういうことかといいますと、通常、木構造アルゴリズムに対する論文は、まず解きたい問題があって、それに対してアルゴリズムを作る、という形になっている、ということです。ですので、同じ技術を使った似たようなアルゴリズムがあちこちに現れることになります。アルゴリズムの研究、という点からは、このような研究スタイルではなく、まず、木構造ネットワークの問題にはどのような技法を用いたアルゴリズムが有効か、それを研究し、一般的な木構造アルゴリズムの形態をいくつか作り、その後で、どのような性質を持つ問題がどの形態のアルゴリズムで解けるのかをまとめる、という方向で研究されるべきでしょう。
このような研究が進めば、例えば、新しい木構造ネットワーク問題を解くアルゴリズムを開発する必要が出てきたときに、その問題がどのような性質を満たすかを調べるだけで、どの形態のアルゴリズムが使えるのかが分かるわけです。理論的にも、プログラムを設計する上でも、すっきりと見通しがよくなります。
私の過去の研究では、木構造アルゴリズムは、過去に1つ、k-tree-core というものを求めるアルゴリズムに対して、線形時間、つまり最適なアルゴリズムを開発しました。ここから得た知見をもとに、いくつかのアルゴリズムが高速化できることが分かってはいたのですが、場当たり的な研究になるので、その一つ一つを論文にまとめるということはしていませんでした。最近になって、いくつかの基本的なアルゴリズムを用いて、各問題がどのような性質を満たす場合に、どのアルゴリズムが適用できるか、という観点の研究を行えば、場当たり的でなく研究を進めていけるな、と思い始めました。しばらくは、この基本アルゴリズムがどのような形になるかを研究して行きたいと思います。
近似解法高速化
近年、大型の組合せ最適化問題を解く方法として、局所探索、タブサーチなどのメタ・ヒューリスティック解法が研究されてきています。様々な問題に対して、どの解法がどの程度精度の良い解をどれくらいの時間で求めるか、つまりそれぞれの解法の各問題に対する性能が検証されています。それぞれの解法の性能を比較するには「この解法でプログラムを組むと、どれくらいの時間でどれくらいの解を見つけるか」ということを計算実験で調べているわけですが、だいたいの研究では、プログラムを組むときにはごく普通の方法を用いています。逆にいえば、アルゴリズムの分野で研究されている最新の技術を用いているものは少ないのです。それぞれの解法の能力を比較するときには、最も優れた技術を使ってプログラミングしたときに、どの程度の性能になるか、ということを比較しなければ、フェアでないと思います。普通の技術だけでは性能が悪くても、良い技術を使えば性能が良くなる解法が、「良くない解法」との評価をされることになるからです。
メタ・ヒューリスティック解法は、比較的大きな問題を比較的短時間で解くことができますが、解く時間を数秒にする、あるいは超大規模な問題を解く、といった目的では作られていません。これらの大規模問題を解く、あるいは超高速アルゴリズムを作るためには、アルゴリズム的な技術を活用して、メタ・ヒューリスティック解法の改良をする必要があります。10分程度で中規模の問題が解ければよい、という要望も、現実ではいくつかあるのですが、例えば、対話型の最適化をしたい場合などは、1分以内に解けないとシステムとしては良くないでしょう。最近の IT 化で大量のデータを集められるようになったので、超大規模な問題も比較的あちこちで見かけるようになってきています。
このような超大規模問題・高速化に対しては、今までの方法とは違う発想が必要でしょう。例えば、正確に局所探索を行うのではなく、ある程度不正確でも、高速に動くような方法を考えたり、不要な探索に関する計算を上手に省略するという発想に基づいたアルゴリズムの技術が必要になってきます。企業活動での問題では、精度の高い解を時間をかけて見つけるよりも、短時間でそれなりの解を得たい、という要望が多いので、こういった研究が企業活動への最適化問題の普及にもつながって行くと考えています。
精度保証の付いた近似解法では、比較的次数の高い多項式の計算量を持つアルゴリズムが多く、こういったものに対してはアルゴリズムの高速化が有効であろうと考えています。しかし、近似解法自体まだ発展途中であり、まったく違ったアイディアをもとにしたアルゴリズム、つまりまったく違う構造を持ったアルゴリズムが最高記録を塗り替える、ということが頻繁に起こっており、1つの近似アルゴリズムに固執した高速化の研究は、すぐに時代遅れになる可能性が高く、あまり意味がないと考えています。しかし、その半面で、ある程度結果が落ち着いている分野もあるわけで、そういった分野に対しては、応用分野からの要望からも、高速なアルゴリズムの開発をしなければいけないのかなと思っています。
メタ･ヒューリスティックに関しては、上記の通り、あまりアルゴリズム高速化、言い換えれば1反復で行う計算の高速化に関する研究は行われてきていません。それもそのはず、という面もありまして、アニｰリングなどは1反復がほぼ定数時間ですから、改良の仕様がないわけです。しかし、局所探索、とくにタブサーチは、現在の解から少々の変更で作れる解の集合（近傍といいます）の中から良いものを見つけ出す、という問題を何回も解かなければならないので、1反復に比較的時間がかかります。近傍を大きく取り、1反復でより良い解を得ようとすれば、それだけ時間がかかります。このような反復計算には、動的データ構造がうまく使えます。現在までの研究で、巡回セールスマン問題、ビンパッキング、スケジューリング問題などでは、1反復の計算速度が、(問題の大きさ)倍ほど速くなる、つまり計算オーダーの次数が1つ小さくなることが確認できています。今後は、これらをちゃんとつめて、どこまで速くなるかを検討した後、まとめようと考えています。
他の研究分野、企業との関わり
近年、最適化問題の研究が進み、大きな問題や複雑な問題が解けるようになってきました。また、オペレーションズ･リサーチの研究の進展から、今までは数理的に捕らえられなかった問題も、いろいろな方法を使って、モデル化できるようになりました。そのため、従来研究が行われてきた企業活動での問題の他に、他の科学研究分野に現れる問題も、モデル化して最適化し、解を求められるようになりました。例えば、建築学での、強度や予算の制約を守るような、構造・使用部材の最適化、バイオ工学での、遺伝子の類似性の数値化、複数の遺伝子の共通因子の発見、各種分野での、ものの価値、あるいは強弱の数値化、言語学での類似語郡の発見、情報工学での、ネットワークの特徴づけ、部分因子の発見などです。
現在、最適化アルゴリズム、という概念はあまり世間に普及していないと思われます。つまり、これらの科学技術分野の多くの問題は、まだ最適化の観点からは研究されてきていないと考えて良いと思われます。ですので、これらの問題の多くが、実は、最適化あるいはオペレーションズ・リサーチの技術を用いることで、効果的に解けるのではないかと考えています。これらの最適化問題は、いわゆる教科書に載っている方法で解けるものは比較的少なく、それにプラスアルファが必要になることが多いものです。このプラスアルファ、難しいものもありますが、すでに研究されてきている他の最適化問題での技術を用いれば、比較的簡単に導き出されるものもあります。今後、これらの分野の研究者や企業の方々と情報交換をして、いろいろな面での応用アルゴリズムを作って行きたいと考えています。