一部の問題は解くのに利用したパラメータがハードコードされている値と違うことがありますが、一応5000問全部解きました。
全体: https://github.com/methane/gdd11/tree/master/slide
Cythonコード: https://github.com/methane/gdd11/blob/master/slide/_slide.pyx
幅優先とか反復深化とか何種類かのソルバがあって、いちいち説明する気はないんだけど、工夫したところだけ紹介。
反復深化は、深さを1ずつ増やせば最短解が見つかるんだけど、別に最短解じゃなくてもいいからある程度良い解をそこそこの時間で求めたい場合はもっと大きい単位で深さを増やしても良い。
同じ状態を何度も探索しないようにしたいんだけど、探索した状態をメモるとメモリが収まらないので、1GBのビットマップを用意して、ハッシュ値を 8G で割った余りのビットを使って管理している。衝突した状態は割り切る。
これでも 8589934592 ビットしか無いので、全探索しているとすぐにビットが埋まって衝突だらけになるんだけど、これを使う場合は探索の範囲をランダムに絞って十分に疎になるようにしている。解が見つからなかったら再探索するという割り切り。
探索プログラムは perf record でプロファイル取って、ボトルネックになってる部分は高速なCコードを吐くようなCythonプログラムにして、それ以外はPythonのオブジェクトをそのまま使って楽をできた。GCも循環参照はつくらないようにしたら参照カウント方式なのでメモリ使用量が安定していて、OOM Killerの心配しないで長時間実行することができた。
Cython で不利なのは、Pythonランタイムを使ってるので小粒度な並列が難しいところ。例えば深さ優先だと、分岐のそれぞれを別スレッドで探索するみたいなのは今回は割り切った。今回は割りきってプログラムを複数個実行して問題単位で並列実行していたから、例えば上記の1GBのビットマップが4並列だと4GBのメモリを使用してしまう。
一応 C++ の string とか vector とかは簡単に使えるようになってるから、探索のコア部分がPythonオブジェクトを一切使わないようにしてGILを解放するコードを Cython で書くこともできるんだけど、今回はたまたまメモリを8GB積んだ遊んでるサーバーマシンを会社に借りることができたのでそこまでの最適化には手を付けていない。
