paizaの国際プログラミング選手権のやつ

どれ

のやつですね。開始3日で最適解に到達したようです。やったことをずらずらと書きます。

解法

15パズルの最適解の求め方自体は割りと文献が多くて調べやすいです。時間制限なしだとPattern Databaseを使ったIDA*(反復深化A*)もしくは両側探索、ステップ数制限なしだとgreedyが良いですが、今回は時間制限ありでできるだけステップ数を短くしろということなので、
Pattern Database + 幅優先ビームサーチ
でやりました。ビームサーチだと時間制限に合わせてビーム幅を変えて調整しやすいです。
幅優先ビームサーチはビーム内に収まっている状態をすべて遷移させて、それをソートしてビーム幅分の上位をとって収めるというのを繰り返すやつです。15パズルの場合は最良優先ビームサーチより良いみたいなのがどこかに書いてありました。
Pattern Databaseはパズルを数個ずつのパーツにわけ、各パーツ+空き分の移動ステップ数を前計算しておいて、それを合計して距離とするやつです。A*の場合は距離としての制約を満たすようにしないといけないですが、ビームサーチの場合は関係無いです。

実装

具体的には、5+5+5のパーツに分けたものでPattern Databaseを構築(1パーツあたり16^6=2^24要素の距離配列)して、この合計をスコアとしてスコアの小さい方を優先させる幅優先ビームサーチを実装しました。同じ状態に来られると困るので、直前2ステップのみに関してHashMapをつくって除くようにしました。

高速化としては、次のようなことをしました。高速化するたびにビーム幅が広げられます。
・ビットボード化・・はデフォ。
・JavaのHashSet/HashMapは挿入のたびにEntryをつくることとboxingにより激重仕様なので、IntOpenHashSetみたいなのを適当に改造したものを使いました(http://codenav.org/code.html?project=/com/carrotsearch/hppc/0.4.3&path=/Source%20Packages/com.carrotsearch.hppc/IntOpenHashSet.java). これで1.5倍の速度に。
・状態には操作履歴を格納しますが、1手あたり2bitで十分なので小さいlong配列にパッキングしました。これで1.2倍。
・Pattern Databaseの距離の種類はそんなに多くないのでint配列からbyte配列にしました。これで1.1倍。
・同様にビーム内の状態の距離の種類もそんなに多くないのでバケツソートにしました。これでちょっぴり。

この解法の前には上1行揃えて左1列揃えて残り8個を全探索みたいなことをやってました。上の解法にかえていくらか最適化したら40を切れたので(https://twitter.com/uwitenpen/status/588969437291630593) みたいに煽ったのですが、それ以上高速化してもスコアが下がらないので若干焦ってました。

所感

• もっと難しい問題出してもいいのよ
• 多言語対応が大変そうだなぁと思った
• 図らずもwriterの人と会ってしまった