「フカシギの数え方」の問題を解いてみた

先日、「『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。これは自己回避歩行(Self-avoiding walk)と呼ばれている問題らしい。 これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。しかし、話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。 動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。そこで、高速化のため

[mujin]

スパコンの事業仕分けのときも話題に上がってたけどアルゴリズム超重要だなー。おねえさあああんのスパコンが25万年かけた計算を、最新アルゴリズムだとノートパソコンで10秒だって。

[Kureduki_Maari]

.｡oO(ZDD) 良いもの。悪いもの。: 「フカシギの数え方」の問題を解いてみた

[perezvon]

「動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。」

[hiroyuki1983]

「これは自己回避歩行(Self-avoiding walk)と呼ばれている問題らしい。」「高速化のためにゼロサプレス型二分決定グラフ(ZDD; Zero-Suppressed Binary Decision Diagram)と呼ばれるアルゴリズムを利用することにした」

[tuki0918]

わからん！

[Itisango]

“良いもの。悪いもの。: 「フカシギの数え方」の問題を解いてみた”

[atsushifx]

アルゴリズム重要。

[Hiro0138]

なるほど、わからん(プログラミングは10年以上やってないので) / “良いもの。悪いもの。: 「フカシギの数え方」の問題を解いてみた”

[AKANE_Daigo]

すごい。TAOCP Vol4とつながったか / 良いもの。悪いもの。: 「フカシギの数え方」の問題を解いてみた -

[fcicq]

Zero-Suppressed Binary Decision Diagram

[tamuo]

あとで（見る|解く）。おねえさんに教えてあげたかった「フカシギの問題」のアルゴリズム