おねえさんのコンピュータを作ってみた

まだやってたのか、と言われてしまいそうですが、おねえさんが計算にかけた時間と比べればまだまだです。

『フカシギの数え方』おねえさんといっしょ！みんなで数えてみよう！

この動画で出てくるおねえさんのコンピュータを作ってみた、というお話。

検索アルゴリズム

HTML+CSSでコンピュータの画面を再現してみました。Javascriptを組むより、そっちの方に時間がかかった気がする。経路の描画にはCanvasを使ってます。

この問題は自己回避歩行(Self-avoiding walk)と呼ばれるものらしいです。単にグラフ上を移動するだけなので、小さいなサイズなら単純な深さ優先検索(DFS)で解けます(大きなサイズで何が起こるのか・・・それは動画で)。実装では、DFSによる検索プログラムをWeb Workerを使って走らせ、スタートとゴールを結ぶ経路を見つけたらメッセージを飛ばしてます。

さすがに全部は表示できないので、実際に表示するのは50ms秒程度の間隔。 4×4以下ではそれだと速すぎて何が何だかわからないので、待ち時間を入れてある。

さあ、君も10×10にチャレンジだ！！

おねえさんに教えて上げよう！

しかしながらDFSだけだとなんだか負けた気がして悔しいので、高速化したアルゴリズムも試してみた。「おねえさんに教えてあげる」のチェックボックスにチェックを入れると高速化したアルゴリズムで問題を解きます。

ゼロサプレス型二分決定グラフ

自分が色々試行錯誤している間に他の人が解いてしまった(「フカシギの数え方」の問題を解いてみた) ので、それを参考に実装してみた。

今回の問題は「グラフ上の経路問題」ですが、どの枝を通ってどの枝を通らないかという「枝の選択問題」として考えることができます。その組み合わせを効率良く表すための方法が、ゼロサプレス型二分決定グラフ(ZDD; Zero-Suppressed Binary Decision Diagram)。 ZDDは数学の組み合わせでよく使う樹形図の一種で、同じ結果になる枝を集めることで樹形図を効率良く表したものです。概要はBDD/ZDDを基盤とする離散構造と処理演算系の最近の展望を参照。もっと詳しい説明はThe Art of Computer Programmingに書いてあるらしい(まだ読んでない)。

ZDDを考えた湊先生は最初の動画の企画・監修も努めている方なので、動画中の数値もZDDを使って求めたものと思われます。

Simpath

ZDDは単なる組み合わせの表現方法なので、別途グラフからZDDを求める手法が必要になります。これに関する簡単な解説がZDDを用いたパスの列挙と索引生成から見られます。

上のセミナー資料ではZDDの基本演算を使った列挙の方法が紹介されているけど、今回はクヌース先生のSimpathを採用。 Simpathでは(既約でない)ZDDを作ることができます。経路の両端にのみ着目し、この情報をmateという配列で管理。 frontierと呼ばれる頂点のmateを用いてZDD上のノードを共有することで簡略化を行います。

実際使ったアルゴリズム

セミナー資料では幅優先でノードを作ってみるように見えるけど、今回の実装では深さ優先で経路数だけカウント。 ZDDのノードを作るのが面倒だったんです。しかし、覚えなければならないmateが大量になってしまいメモリがああああ！！すべて覚えるのは諦め、一部のmateだけ覚えるようにしました。

「おねえさんに教えてあげる」のチェックを入れると、適当実装のSimpathで計算します。計算中一部の枝が灰色になるのは、ZDD上でノードの共有化が行われたため、実際には枝が処理されなかったためです。格子上の点に丸がついているのはfrontier。この点の継続情報を用いて共有化を行います。

まとめ

おねえさんのコンピュータの実装と高速化を行いました。高速化の結果、処理に数分かかっていた6×6の計算が200msで終わるようになりました。 10×10も1分程度で終わります。

ただ、表示のためのオーバーヘッドがあるとはいえ、他の人と比べると少し遅いような。なにか実装間違っているかも。 The Art of Computer Programmingを読んで勉強しないとかな。