お姉さんが人生を懸けて「組み合わせ爆発」を解説する日本科学未来館の動画が、ネット上で大きな話題となりました。この動画に登場した「同じ場所を2度通らずに何通りの線が引けるか」という問題を解くコンピューターが、Webで実装されています。動画では6年掛かりで導き出された「9×9」マスの計算や、25万年掛かった「10×10」マスの計算も忠実に再現。動画の最後で言及されている、高速化したアルゴリズムで解くことも可能です。
▽ おねえさんのコンピュータ
▽ お姉さんが人生を懸けて“組み合わせ爆発”を力説 動画「フカシギの数え方」が壮大すぎる - はてなニュース
再現された「おねえさんのコンピューター」を使って、実際に5×5の問題に挑戦してみました。動画でもそうだったように、数秒で計算が終了します。コンピューターが線を辿りながら組み合わせを計算している様子も再現されていました。
左が「おねえさんのコンピューター」、右が動画に出てくるコンピューター
さらに、ページの下部にある「おねえさんに教えてあげる」にチェックを入れると、高速化したアルゴリズムを使って問題を解けます。試しに「おねえさんに教えてあげる」モードを利用してみると、通常の処理だと数分掛かっていた6×6の計算は一瞬で終了。お姉さんがスーパーコンピューターを導入しても4時間半掛かった8×8は約10秒、6年半掛かった9×9は約30秒で結果が表示されました。
左が約30秒で解けた9×9の結果。右が6年半掛けて9×9の問題に挑んだお姉さん。ああ、お姉さん……
同サービスを制作したIchinose Shogoさんによると、動画で使われているマスの問題は、線形高分子の統計力学モデル「自己回避歩行」と呼ばれるもの。グラフ上を移動するだけなので、小さなサイズであれば「深さ優先検索（DFS）」というアルゴリズムを使って解けるそうです。高速化のアルゴリズムは「ゼロサプレス型二分決定グラフ（ZDD）」と呼ばれるもので、動画の制作に参加した北海道大学准教授の湊真一さんが考案しました。
▽ おねえさんのコンピュータを作ってみた
▽ 良いもの。悪いもの。: 「フカシギの数え方」の問題を解いてみた
アルゴリズムの重要さを改めて感じさせられるこのサービス。可能ならば、お姉さんに教えてあげたい……。
