湊慎一『超高速グラフ列挙アルゴリズム』

湊慎一『超高速グラフ列挙アルゴリズム－〈フカシギの数え方〉が拓く，組合せ問題への新アプローチ－』

フカシギの数え方のこの動画。

この動画で一躍有名になった列挙の問題を高速に解く「最新のアルゴリズム」ことZDDの解説書がこの本なんだけど、これは良い本でした。

ZDDの基本的なアイディアはこういうもの。「フカシギの数え方」ではグリッドの左上から右下への全経路を調べるわけだけれど、これの問題をまず「経路に使われたエッジの集合」の数え上げと定式化する。で、「辺1を使う・使わない」という選択肢によって分岐し、次に「辺2を使う・使わない」で分岐し……とやっていくと、高さが辺の数に相当する巨大な二分木ができる。ここから有効なもの（使うエッジの集合が実際にスタートからゴールまでをつなぐ一本の経路になってるもの）だけを使うような制約条件をかければ数え上げられるのだが、もちろんこのままだと巨大な二分木なんでどうしようもない。ただ制約条件の下では木を非常に簡潔なかたちに縮約できますよ、というのがZDD。もちろん、最初に巨大な木を作ってから縮約していくのでは意味がないので、初めからZDDを作っていく。

この本ではまず前半でこうした問題の概略を説明し、コアとなるデータ構造であるZDDと、その構成方法が説明される。さらに作者の作ったGraphillionというライブラリの簡単なサンプルコードもついている。このデータ構造は知らなかったので、ここがまず面白かった（ZDDやBDDはTAOCPの4Aでも触れられているらしい）。

本の後半は、パズル（ナンバーリンクやスリザーリンクなど）、電力図、路線図などの経路問題への応用の説明。こちらもGraphillionを使ったサンプルコードつき。いじわるな見方をすれば解法に応じた問題設定とも見えなくもないけれど（路線図の問題など）、全体的になかなか応用できる場面がいろいろありそうな雰囲気を醸し出している。

最後のアドバンストな話になると、一般的なZDDからフカシギの数え上げ方に向けての（定数倍の）最適化手法の説明や、頻出アイテムマイニングや文字集合の表現方法などのトピックにも触れられている。文字集合はトライ木をベースにしたDAWG (directed acyclic word graph)と本質的には同じになるらしい。でもZDDベースだと木の演算（合成や差分）が自然に表現できるから良いんだとか。うーんこれは本当なのかな（つまり、合成や差分はこの分野でできると嬉しいことなのか、DAWGでは難しいのだろうか）。まあこの辺はあまり追えてません。

良い本だなと思ったのは、まず（自分は）知らないデータ構造・アルゴリズムに関する話を解説していて、応用事例も含めて説明があるので、なかなか学びの多いから。ただ今んとこ自分は表面的に書いてあることを眺めただけなので、より細かい話は参考文献を読んだりサンプルコードを動かしてみたりといったことが必要かな、という感じですかね。