みんなで数えてみよう!」という動画を見た。格子状のマスの左上から右下までの経路が何通りあるのかを調べて、格子が多くなればなるほど組み合わせの数が爆発的に増えることを教えてくれる動画だ。walk)と呼ばれている問題らしい。これだけ聞いてもそれほどインパクトはないのだが、動画に出てくるおねえさんの経路を調べあげる執念がもの凄く、ネット上でも結構な話題になっている。執念と言うよりも狂気に近い。話題になった割には動画内で言及されている高速なアルゴリズムを実装したという話を聞かなかったので、自分で確かめることにした。動画のおねえさんは深さ優先探索によるプログラムを使っていると思われるが、それだとスパコンを使っても10×10マスの格子を解くのに25万年も掛かってしまう。Diagram)と呼ばれるアルゴリズムを利用することにした。このアルゴリズムを開発したのは北大の湊先生で、ZDDによりすべての経路を見つけ出すアルゴリズムとしてクヌース先生のSIMPATHを使った。4-1)ではBDD/ZDDの詳細な解説を読むことができる。演習問題の解説だけで書籍の半分を使っていることからしても気合の入れようがわかるだろう。実際に自分のノートPCでZDDアルゴリズムを使ったコードを走らせたら、ほんの10秒程度で10×10マスの問題を解いてしまった。おねえさんがスパコンで25万年かかった問題をノートPCでたった10秒である。約8千億倍の高速化だ。これだけ劇的に変わるとやっぱり楽しい。アルゴリズムの重要性を再認識させられた。以下におねえさんが利用したであろう自作の深さ優先探索(DFS)プログラムと高速な解法であるZDDアルゴリズムの両方を載せておく。ZDDについては4つのプログラムを1つのPythonスクリプトで統合している。GraphBase)ライブラリでグラフを作成し、経路の数え上げにGMPを使ったC++で自作コードを組んだためである。最初はSIMPATHを参考に実装して一つのソースコードに統一しようかと思ったが、解説もちゃんと書かれているクヌース先生のコードをそのまま利用することにした。これらのプログラムの簡単な解説と使い方を載せておく。DFSによる実装を以下に示す。Node構造体から経路を辿って数え上げるだけの単純なプログラムである。実行方法は以下の通り。引数の7は7×7のノードを表しており、マスで表現すれば6×6マスとなる。計算結果として、575,780,564通りの経路が探索されたことを示している。因みに7×7ノード(6×6マス)で約3分ほどの時間が掛かっており、それ以上の大きさだと現実的な時間で解くことが難しくなってくる。575780564次に、ZDDを利用したプログラムのビルド方法を示す。ビルドをする前にSGBおよびGMPを準備しておく。SIMPATHおよびSIMPATH-REDUCEについてはCWEBを利用しているので、それも入れておく。最初に、SGBライブラリを用いて格子状のグラフを作成する。gen_latticeソースコード内でグラフを下記のように作成している。board関数はチェスのような格子状のグラフを作成することができる。他にもグラフを作成する便利な関数が多数あるので、興味のある方はSGBライブラリのgb_basic.wあたりを参照して欲しい。0L);次に、SIMPATHおよびSIMPATH-REDUCEを以下のようにビルドする。simpath-reduce因みに、ctangleでC言語への変換、cweaveでTeX形式への変換を行うことができるので、以下のようにTeX形式のドキュメントも一緒に作っておくことをお勧めする。4を読んでおくことが望ましい。PDFファイルが必要なら.最後に、ZDDから経路を数え上げるプログラムをコンパイルする。count_path_mp経路を一つ一つ数えていては高速に数え上げるという点で意味がなくなってしまうので、ちゃんとメモ化再帰で数える。ZDDは高度に圧縮されているのでメモ化再帰でほとんど瞬時に数え上げることができる。上記のプログラムを統括するPythonスクリプトが以下となる。グルー言語としてもPythonは優秀だ。実行方法は以下の通り。789360053252DFSのプログラム同様、引数の8は8×8ノード(7×7マス)を表している。計算結果として、789,360,053,252通りの経路が探索されたことを示している。中間ファイルとして以下が出力される。一連の実行ファイルのログ.因みに、DFSで7×7ノード(6×6マス)を解くと3分ほどかかったが、ZDDでは0.1秒未満で完了した。ZDDで14×14ノード(13×13マス)は数分で終わることを確認したが、それ以上は途中で搭載メモリ以上に必要なメモリが大きくなるので実行していない。科学2012年5月14日月曜日テトレーション・フラクタルTweet5年ほど前、このブログで虚数のテトレーションという記事を書いたことがある。