組み合わせ爆発とその解決法を「体感」せよ! ―― 日本科学未来館 メディアラボ 第11期展覧会
日本科学未来館の常設展示「メディアラボ」は,情報技術と創造性が結びついた展示品を紹介するコーナである.物理的な形にしづらい「情報技術」を体験的に学べるように,さまざまな工夫を凝らした展示が行われている.ここでは,2012年8月1日~2013年2月25日に展示されている第11期展覧会「フカシギの数え方 The Art of 1064 -Understanding Vastness-」を紹介する(写真1).
写真1 日本科学未来館の常設展示「メディアラボ」

●組み合わせ爆発で現れる「不可思議」という単位
タイトルにある「フカシギ」とは,一・十・百・千・万・億・兆・京... と続く数の単位の一つ「不可思議」であり,10の64乗を指す.例えば,畳の敷き詰め方や路線探索,LSIの配置配線問題,機械スケジューリング問題などについて(あるいは,分岐の存在するプログラムにおいて),すべての組み合わせを数え上げようとすると,組み合わせの数は膨大になる.この展示では,コンピュータによる一般的な数え方と,より効率の良い数え方を「技」に例え,5段階に分けて紹介している.
展覧会のポスト・カードは,畳を敷き詰めたようなデザインになっている(写真2).しかもよく見ると,複数のポスト・カードで畳の敷き方や文字の色,フォントなどが微妙に異なっており,ここにも何通りもの組み合わせがあることを示唆している.
写真2 第11期展覧会「フカシギの数え方 The Art of 1064 -Understanding Vastness-」の案内用ポスト・カード

●人間の数え方 vs コンピュータの数え方
最初の段階は「見習い:とにかく『数え上げる』べし!」である.写真3のスタートからゴールまでの道のりが何通りあるのかを考える.スタートからゴールまでをたどる際に,同じ経路を2度通ってはいけない.
写真3 スタートからゴールまでの道のりは何通り?

人間は「まずAを通り,次にDを通ると...? DでなくてFだと...?」などとあり得る可能性を順番に数え上げて,「7通り」という答えを導き出す.これに対してコンピュータで計算する場合,すべての組み合わせを数え上げてから,その中であり得る組み合わせを判定する.いったん2の10乗,つまり1024通りを数え上げることになる(写真4).
写真4 コンピュータの数え方

●組み合わせ爆発を実感する
写真3のような単純なコースでさえ1024通りである.これが,16マス×16マスのマトリックス(行列)になると,組み合わせの数は膨大なものになる(写真5).マトリックスを1マス×1マスから16マス×16マスに変化させ,それぞれの組み合わせの数を羅列したものが次の段階「門下生:『組み合わせ爆発』を感じるべし!」である.
写真5 数の単位と組み合わせ爆発
16マス×16マスのマトリックスにおいて左上のスタート地点から右下のゴール地点までたどるための組み合わせの数は,68那由他7454阿僧祇4560恒河沙9149極(以下略)...という膨大な数になる.

tag: インターフェース