まずはこの動画を見るべし → 『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！。
きちんとした解答がすでに上がっている → 「フカシギの数え方」の問題を解いてみた。
まあでも、これだけ力作な動画を見せられたら自分でも解いてみたいと思うのが理系というもの。Knuth先生に経緯を払いつつ車輪の再発明をしてみた。元ペーパーとか読めばいいんだろうけど、こちらの資料が素晴らしかったので参照 → ZDDを用いたパスの列挙と索引生成。
ZBDDの基本的な考えは、集合の各要素についてTrue or Falseで分岐する二分木を作ってやると末端に部分集合に対応した数だけ分岐ができるので、そこにさらにTrue or False をぶら下げると部分集合の集合を表現できるでしょうというもの。例えばこのwikipediaの図は、{x1, x2, x3}という3要素からなる集合について、{{}, {x2, x3}, {x1, x2}, {x1, x2, x3}}を表していると見なせる。で、これだけだと当然組み合わせ爆発が起きるので、同じ形のノードが現れたらくっつけたり、それ以降潜っても結果が1種類(True or Falseのどちらか)に決まってしまっている部分は削除したりして圧縮しようというのがZBDDの考え方。
経路探索問題では、経路の部分集合の表現としてZBDDを使うことができる。例えばABCDからなる四角形の経路(フカシギの数え方で言うと1×1の場合)を考えると、経路の集合は{AB, BD, AC, CD}の4通りで、そのうち解である{{AB, BD}, {AC, CD}}を表現するZBDDを組み立てることが目標となる。このZBDDをどのような戦略で組み立てるとよいかは、先ほど紹介したPDFを見るといろいろ解説されている。
書いたコードはgistにおいてある。
8×8の格子の3,266,598,486,981,642という回答を出すのに、動画中ではスパコンで4時間かかっていた内容が、手元のMBAで30秒ほどで結果を出すことができた。スパコンで6年かかっていた9×9だと、155秒ほどで4.10442087026325e+19という回答が。さすがにPerlでざっくり書いただけだとNOXさんのように"7兆7千憶倍の高速化"とはいかないが、それでもかなりの効果だと思う。
