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

　日本科学未来館の常設展示「メディアラボ」は，情報技術と創造性が結びついた展示品を紹介するコーナである．物理的な形にしづらい「情報技術」を体験的に学べるように，さまざまな工夫を凝らした展示が行われている．ここでは，2012年8月1日～2013年2月25日に展示されている第11期展覧会「フカシギの数え方 The Art of 10⁶⁴ -Understanding Vastness-」を紹介する（写真1）．

写真1　日本科学未来館の常設展示「メディアラボ」

●組み合わせ爆発で現れる「不可思議」という単位

　タイトルにある「フカシギ」とは，一・十・百・千・万・億・兆・京... と続く数の単位の一つ「不可思議」であり，10の64乗を指す．例えば，畳の敷き詰め方や路線探索，LSIの配置配線問題，機械スケジューリング問題などについて（あるいは，分岐の存在するプログラムにおいて），すべての組み合わせを数え上げようとすると，組み合わせの数は膨大になる．この展示では，コンピュータによる一般的な数え方と，より効率の良い数え方を「技」に例え，5段階に分けて紹介している．

　展覧会のポスト・カードは，畳を敷き詰めたようなデザインになっている（写真2）．しかもよく見ると，複数のポスト・カードで畳の敷き方や文字の色，フォントなどが微妙に異なっており，ここにも何通りもの組み合わせがあることを示唆している．

写真2　第11期展覧会「フカシギの数え方 The Art of 10⁶⁴ -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極（以下略）...という膨大な数になる．