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

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