列挙することが最適化への近道
計算時間を劇的に短縮する超高速アルゴリズム
情報科学研究科 コンピュータサイエンス専攻 知識ソフトウェア科学講座 アルゴリズム研究室・教授
博士(工学)湊 真一
プロフィール
1965年生まれ。京都大学工学部情報工学科卒業、同大学大学院工学研究科情報工学専攻修了。博士(工学)。日本電信電話株式会社LSI研究所でLSI設計自動化のためのアルゴリズム研究に従事、米国スタンフォード大学客員研究員などを経て、2004年から北海道大学准教授、10年から現職。大規模論理データ処理、知識索引技術の研究に従事。09年、JST戦略的創造研究推進事業ERATOに採択され、離散構造処理系プロジェクトの研究総括を務めている。
計算回数を減らすことで処理を高速化するアルゴリズム
湊先生が研究しているアルゴリズム技術とはどういうものですか。
湊 アルゴリズムは、プログラムに書かれた計算手順・戦略のことで、小説に例えるならあらすじのようなものです。さまざまな計算を行うとき、アルゴリズムを工夫することによって計算時間を何十倍、何百倍も短縮することができるのです。
計算を速くするには、まずコンピュータの計算能力を上げるという手法があります。スーパーコンピュータ「京」はその最高峰で、1秒間に京回（兆の一万倍）の計算ができるのが京コンピュータです。しかし、スパコンは誰もが使えるようなものではありません。
一方アルゴリズム技術は、1回の計算速度を上げるのではなく、計算の回数を減らすことで処理時間を短縮するのが特徴です。巨大なデータを扱う計算も、アルゴリズムを工夫して計算回数を減らせば、スパコンでなくても十分計算が可能になります。ただし、問題によって処理が非常に速くなるものと、それほど速くならないものがあり、どのような問題にどんなアルゴリズム技術が適しているかを探究することも重要になってきます。
アルゴリズムを工夫するというのは、具体的にどういうことなのでしょうか。
湊 大規模な論理データを高速に処理する技法として「二分決定グラフ」(BDD: Binary Decision Diagram)（解説１）と呼ばれるデータ構造があります。例えば金額の違うクーポン券を何枚か使ってちょうど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）」（解説２）を考案しました。これは「1の時の行き先がゼロ（空集合）であれば削除する」という新しい圧縮ルールで、クーポンの例で言えば、「他のどのクーポンと組み合わせても1,000円にはならない」というクーポンは最初からなかったことにするという考え方です。このルールを使うと、役に立たないクーポンが多いような例題では、BDDに比べてさらに数十倍以上の圧縮ができる場合があります。
ZDDが実現したスマートグリッドの最適化
実際にZDDを使って計算した例はありますか。
湊 私たちが手がけたものでは、電力網の配電経路の最適化問題がその好例です。図4は実際の配電網をモデル化したもので、4つの変電所を中心に、電線に接続された一般家庭などに電力を供給する様子を表しています。配電網の最適化には、電線各所に配置されているスイッチのオン／オフで電力の供給ルートをコントロールし、最もロスの少ない配電経路を見つけることが必要ですが、電線には合計468ヵ所のスイッチがあり、その組み合わせ総数は2468（２の468乗）通り、つまり10の140乗に達します。これらを完全に調べ尽くして、真に最適な経路を現実的な時間内に見つけるのは不可能と思われていました。
そこで私たちはZDDを使って諸条件を満たす経路の抽出を試み、わずか10分程度ですべての可能な組み合わせから停電を起こさない正しい組み合わせを抽出し、その中から最適な経路を探し出すことに成功しました。我々が抽出した組み合わせの総数は10の63乗通りという凄まじい数ですが、ZDDで圧縮されてCD-ROM 1枚に納まるくらいのデータ量になりました。この試みの成功は、電力の流れを供給側と需要側両方か効率的に管理する「スマートグリッド」の実現に大きく貢献できると考えられます。
列挙することで広がる可能性と選択肢
ZDDの研究は今後どのような展開が期待されるのでしょうか。
湊 今までは有効な組み合わせが全部で何通りあるかわからないまま最適化を求めてきましたが、ZDDを採用することで、膨大な組み合わせ総数の中から有効なものだけを抽出することができるようになったのは大きな成果です。すべてを列挙し全体像を把握することで、条件や環境の変化にも応じた「現時点での最適な答え」を素早く選択することができます。「最適化」と「列挙」は車の両輪であり、ZDDはこれまで列挙することが不可能だと思われた問題についても列挙を可能にしました。
ZDD研究は、平成21年度の独立法人科学技術振興機構（JST）のERATOプロジェクトに採択され、5年半の予定でさまざまな研究を行っています。BDDやZDDが効力を発揮すると考えられる問題には、災害時などの避難所の配置や物流の効率化、選挙区の区割りなど身近な分野にも広がり、それぞれの分野の専門家と協力して最適化の計算に取り組んで行く予定です。
解説
解説１：二分決定グラフとBDD
「0」「1」で分岐する構造の二分決定木では、3回の分岐で23（2の3乗）＝8通りとなる。BDDでは「0でも1でも分岐先が同じ場合は分岐せずに直結する」「共通の行き先を持つ分岐が2個以上あれば1個にまとめる」という圧縮ルールで、これを使うと分岐先の数（＝処理数）を大幅に圧縮することができる。
解説２：ZDD（Zero-suppressed BDD=ゼロサプレス型二分決定グラフ）
湊教授が1993年に考案したBDDの一部を改良した新しいデータ構造。大規模なデータを表現するのに適しており、VLSI論理設計の他、データベース解析や確率推論計算などに利用されている。この理論はアルゴリズム研究の第一人者であるドナルド・エルビン・クヌース博士の著書『The Art of ComputerProgramming Vol.4』の中で紹介された。クヌース博士の著書に数十ページにわたって詳しく紹介されたことは日本人初の快挙。
図４
