はじめに

武永研究室では、情報科学のあらゆる分野で不可欠な、アルゴリズムや計算量に関する研究を行なっています。アルゴリズムとは、問題を処理するための手順のことです。コンピュータはプログラムを実行することにより動作していますが、プログラムとは、アルゴリズムをコンピュータが理解できるような形で、きちんと書いてあげたものだといえます。ここで「良い」アルゴリズムを用いることは非常に重要です。同じ処理を行なうにも、計算量の少ない、良いアルゴリズムを用いるのと効率の悪いアルゴリズムを用いるのでは、かかる時間が時として比べ物にならないくらい変わってくるのです。実際、現代のわれわれの生活は、目に見えないものなので普段気にかけることはなくても、さまざまなアルゴリズムを使っています。インターネットで検索をしたとき世界中の膨大なデータの中から一瞬で必要な情報を探してくれるのも、メールが早く正しく届くのも、（ハードウェアの進歩とともに）効率的なアルゴリズムの開発による部分が大きいのです。しかし、実際に解きたい問題の中には、簡単な問題だけでなく、どのようなアルゴリズムを用いても莫大な計算量を必要とすると考えられる計算困難な問題が存在することが知られています。このような問題の性質を明らかにしていくことも、適切な解法を考える上で重要になってきます。われわれは、アルゴリズムや計算量についての基礎的研究を行い、効率的なアルゴリズムの設計手法の開発や、問題の性質の解明を目指しています。


論理関数の効率的な表現方法とアルゴリズム

写真 効率的なアルゴリズムの設計手法として、論理関数（0,1の値だけをとる関数)の効率的な表現法として知られる二分決定グラフ（OBDD)を用いたアルゴリズムの設計手法について研究を行なっています。左の図が二分決定グラフの一例です。x,y,zと３つの変数が必ずこの順番で上から現れます。各変数の値が1,0,1とすると、変数の値の示す枝をたどっていくとこのときの関数の値が1となることがわかります。 二分決定グラフは多くの分野でデータの表現法として広く利用されています。本研究室では、条件を満たす答を列挙するなどの、二分決定グラフを用いたアルゴリズムの設計手法について、また、二分決定グラフを用いてどのような関数が小さく表現できるか、などの研究を行なっています。


グラフ問題に対するアルゴリズム

グラフとは、数学的にはいくつかの点と、2点を結ぶいくつかの線（辺とよぶ）で結んだものを言います。道路網など様々なものがグラフで表せることから、グラフ上の問題に対するアルゴリズムの研究は非常に盛んに行なわれています。しかし、多くのグラフ問題は、グラフのサイズが大きくなると解くのに莫大な時間がかかると考えられています。本研究室では、一般に莫大な時間がかかる問題でも、特別な性質を持つグラフに限ると簡単に解けることが多いことに着目し、そのようなグラフに近いグラフについても簡単に解けるかもしれない、そのような場合のアルゴリズムや計算量を明らかにする研究等を行なっています。


ゲーム・パズルの計算量

多くの人が楽しむ様々なゲーム・パズルにも、本質的に難しい問題と易しい問題があり、計算量の研究テーマとしても面白い題材が含まれています。本研究室でも、このようなゲーム・パズルの「難しさ」を解明する研究を行ない、たとえば、Rogue(古いRPG)やぷよぷよなどに関する問題が、計算量的に難しいことを証明しました。また、条件を満たすパズルの問題や解答を（ときには上記のOBDDを用いて）全て列挙する研究も行っています。