15 Slide Puzzle

コンペ形式

レナとミナミの国際プログラミング選手権
【幼なじみ or 許嫁】国際プログラミング選手権を制したコード7選+α
こちらに参加しました。

プログラム

自分のコードは以下になります。→Ideone

説明

小問題にわけて一度に行う探索の深さを少なくしています。最適解からはそのぶん遠ざかります。探索にはIDA*アルゴリズムを用い、各小問題ごとに固有の部分はラムダ式などを用いて与えています。

所感

１位のひとはPatternDatabase(PDB)を実装したそうです。自分は、PDBを実装した場合データサイズが4GBを超えると見積もって避けたのですが、１位のひとのソースコードを読むと予め求めておくのではなくオンラインに求めながらキャッシュしていくタイプのようです。このやり方で十分に速度がでるのか自分で実装して確かめてみたいと思います。