HOME > 研究活動・産学官連携 > ネットジャーナル > ネットジャーナル11

ネットジャーナル11

列挙することが最適化への近道
計算時間を劇的に短縮する超高速アルゴリズム

写真:博士(工学) 湊 真一

情報科学研究科 コンピュータサイエンス専攻 知識ソフトウェア科学講座 アルゴリズム研究室・教授
博士(工学) 湊 真一

プロフィール

1965年生まれ。京都大学工学部情報工学科卒業、同大学大学院工学研究科情報工学専攻修了。博士(工学)。日本電信電話株式会社LSI研究所でLSI設計自動化のためのアルゴリズム研究に従事、米国スタンフォード大学客員研究員などを経て、2004年から北海道大学准教授、10年から現職。大規模論理データ処理、知識索引技術の研究に従事。09年、JST戦略的創造研究推進事業ERATOに採択され、離散構造処理系プロジェクトの研究総括を務めている。

計算回数を減らすことで処理を高速化するアルゴリズム

――湊先生が研究しているアルゴリズム技術とはどういうものですか。

湊 アルゴリズムは、プログラムに書かれた計算手順・戦略のことで、小説に例えるならあらすじのようなものです。さまざまな計算を行うとき、アルゴリズムを工夫することによって計算時間を何十倍、何百倍も短縮することができるのです。

計算を速くするには、まずコンピュータの計算能力を上げるという手法があります。スーパーコンピュータ「京」はその最高峰で、1秒間に京回(兆の一万倍)の計算ができるのが京コンピュータです。しかし、スパコンは誰もが使えるようなものではありません。 一方アルゴリズム技術は、1回の計算速度を上げるのではなく、計算の回数を減らすことで処理時間を短縮するのが特徴です。巨大なデータを扱う計算も、アルゴリズムを工夫して計算回数を減らせば、スパコンでなくても十分計算が可能になります。ただし、問題によって処理が非常に速くなるものと、それほど速くならないものがあり、どのような問題にどんなアルゴリズム技術が適しているかを探究することも重要になってきます。

――アルゴリズムを工夫するというのは、具体的にどういうことなのでしょうか。

湊 大規模な論理データを高速に処理する技法として「二分決定グラフ」(BDD: Binary Decision Diagram)(解説1)と呼ばれるデータ構造があります。例えば金額の違うクーポン券を何枚か使ってちょうど1,000円になる組み合わせが何通りあるかを計算する場合、クーポンが1枚増えるたびに組み合わせの総数は2倍になり、組み合わせ総数は2n(2のn乗)通りになります。図2のようにクーポンが10枚(n=10)のとき、組み合わせの数は全部で1024通り、その中でちょうど1,000円になるのは10通りです。クーポンの枚数が増えるごとに組み合わせ総数は爆発的に増えていき、60枚になると総数は約100京通りになります。

そこで、クーポンの組み合わせに同じパターンがあるもの(50円+80円=130円でも130円1枚でも同じ)をまとめると、本来8通りの組み合わせが7通りに減ります(図3)。それ以降の分岐でも同じパターンのものをまとめていくと、最後には198通りにしかならないことが分かります。1024通りすべてを調べなくても良いことになり、約5倍の高速化が図れます。この例では5倍ですが、クーポンの枚数が多くなれば100倍、1000倍の違いが出てきます。

私はさらにBDDを一部改良したデータ構造「ZDD(ゼロサプレス型BDD)」(解説2)を考案しました。これは「1の時の行き先がゼロ(空集合)であれば削除する」という新しい圧縮ルールで、クーポンの例で言えば、「他のどのクーポンと組み合わせても1,000円にはならない」というクーポンは最初からなかったことにするという考え方です。このルールを使うと、役に立たないクーポンが多いような例題では、BDDに比べてさらに数十倍以上の圧縮ができる場合があります。

ページの先頭へ