組み合わせ爆発を説明した動画がいろんな意味で面白い

日本科学未来館が作成した、組み合わせ数が急速に増える様子を説明した動画。
某所では「公共が病気」とか「人類には早すぎる動画」とか「謎の感動」とか言われているが、面白いので見てない人はぜひ見てほしい。結末は衝撃的だ。


おねえさんの狂気っぷりと子供のドン引きさが、なんかツボにはまる。

さて、最短経路(つまり右か下にしか進まない)のケースでは高校のときに確率の授業で習っている。
NxNのときには 2N個の中からN個を選ぶ組み合わせを計算すればよい。
実際に数え上げる必要はなく、Nがいくら大きくなっても単に公式「C(2N,N)=(2N)!/(N!*N!)」を計算すれば簡単に解くことができる。

ではこの動画のお姉さんのように、最短でない経路も数えないといけない場合はどうなのだろう?

これはSelf-avoiding walkと呼ばれる問題らしく、解析的に解くことはできない。つまり答えを求める公式は存在しないので、正確な答えを求めるには数え上げるしかない。
そのうえNP困難といわれる部類の非常に難しい問題ではないかと推測されている。もしそうなら、どんなに工夫しようと効率的に数え上げる方法は存在しないということだ。

それでもこの動画の最後で言われているように、おねえさんのように総当たりで数えるよりもマシな数え方は考えられている。
これまでのところは19x19までは解が求まっているようだ。
意外だったのは、プログラマには神のような存在のクヌース先生もこの問題に取り組んだことがあるようで、1995年に12x12のときを解いている。

このように経路の総数を求めるということは非常に難しい問題であるが、この問題自体に何の意味があるのか?高速に数え上げたところで何の役に立つのか? という疑問は当然湧いてくる。
税金使って変な動画作りやがってというツッコミもあるようだ。

この動画を作った日本科学未来館のページをみると、この問題そのままではないが、例えば電気の送電網でどのような経路で電気を送るともっとも電力のロスが少ないか?といったテーマでその応用例をあげている。

子供向けの動画のようだが、大人が見てもいろいろと深くて面白い背景があることに気づかせてくれる素晴らしい動画だと思う。

2012.09.27追記
最近記録を更新して21x21の解を求めた人がいるようです! 論文もここでみれます。
更新したのは・・・この動画の最後のクレジットにでてくる関係の人たちみたいですね。