スライドパズル
DevQuizのスライドパズルに挑戦。最初は単純な幅優先探索のコードを書いたのですが処理が全然終わりませんでした。4回回答してして得点の変遷は次の通り。
得点 | メモ |
---|---|
1.15 | 残り手数の推定による枝狩り、探索の深さの制限 |
1.72 | もう少し深いところまで探索してみる |
6.44 | 反復深化 |
17.46 | 探索順序の変更 |
最後の二つは数時間の間CPUを回しっぱなしで出した結果です。さらに時間をかければもう少し得点できそうですけど長くなるのでやめておきます。やり方によって同じ問題でも解けたり解けなかったりとばらつきがあるので、複数のやり方で解いて結果をマージするという方法もありますね。
慣れているPerlで解いたのですけど、こういう問題はC言語の方が処理が速いので向いているでしょうね。
もう少し時間が残っていますけど、ボーダーラインは超えられそうなのでここでやめておきます。