組み合わせ爆発とその解決法を「体感」せよ！ ―― 日本科学未来館 メディアラボ 第11期展覧会

●圧縮を体感する

　次の段階「初段：『圧縮』の極意を知るべし！」では，数え上げる組み合わせの数を減らすことを考える．すべての組み合わせを計算するのではなく，「ありえない組み合わせを省略する」ことで分岐を減らしていく（写真6）．さらに，「ゴールにたどり着く」という情報を一つにまとめると，図はさらにシンプルになる（写真7）．このように計算の方法を工夫して組み合わせの数を減らすことを「圧縮」という．次の段階「師範代：奥義『圧縮』炸裂！」では，手で綿を押しつぶすことにより，ディスプレイ上の組み合わせが圧縮される様子を楽しむことができる（写真8，写真9）．

写真6　あり得ない組み合わせを省略する

写真7　同じ情報をまとめる

写真8　実際に「圧縮」してみよう

写真9　奥義「圧縮」炸裂！

●圧縮の応用はスマート・グリッドにも

　最後の段階「師範：『圧縮』が切り開く未来」では，圧縮がどのような分野で役に立っているのかを紹介している（写真10）．身近な例でいうと，発電所から各家庭までをつなぐ送電網および配電網の接続にも不可思議級の組み合わせがあるそうだ．本展示の出展者である独立行政法人科学技術振興機構（JST） ERATO湊離散構造処理系プロジェクトでは，配電網のスイッチ構成を調べ，「ZDD（Zero-suppressed BDD；ゼロサプレス型二分決定グラフ）」と名付けた計算アルゴリズム^注1により，数十万人規模のブロックにおいて配電ロスを最小化する配電経路を発見したという．このアルゴリズムは，電力管理がさらに複雑になるスマート・グリッドにおいても効力を発揮すると考えられる．

写真10　送電網と配電網の接続にも「圧縮」が役に立つ

注1：湊氏は，1986年に米国カーネギーメロン大学教授のランディ・ブライアント氏が考案したBDD（Binary Decision Diagram；二分決定グラフ）を使ったアルゴリズムを拡張する形で，ZDDを考え付いたという．

　もちろん，この展示だけで圧縮のアルゴリズムをマスタできるわけではないが，圧縮という考え方については分かったような気になれる．この展示をきっかけに，情報処理や計算アルゴリズムに興味を持つ人が増えれば，さらに新しいアルゴリズムの開発につながるかもしれない．