カーブ時にペナルティが発生する経路探索アルゴリズム～AHC003を添えて～

これはなに？

一般的に最短経路を求める場合はダイクストラ法が用いられます。ダイクストラ法は元来たルートを意識しないことで高速に計算できる反面、現実世界において進行方向を変える場合に発生するコスト(減速や車線変更、信号待ち等)が考慮できません。今回、AtCoderのヒューリスティックコンテスト「AHC003」を題材に、カーブ時のペナルティを考慮できる経路探索アルゴリズムを考えてみたので紹介します。
コンテストページ：https://atcoder.jp/contests/ahc003

提出プログラム

こちらです。https://atcoder.jp/contests/ahc003/submissions/23029917
当該処理を行っているのは fn solve() の部分です。

ダイクストラ法を用いたカーブ考慮の問題

一般的なダイクストラ法では、下図の場合に問題が発生します。

1マス進むとコスト1かかるとして、コスト０のスタート地点から上右と来た場合と、右上と来た場合に、どちらかの進行しか保持できず、"↑"と"→"のマスのコスト値が実行順序によって大きく異なってしまいます。※移動コストが等価であれば計算を進めることで正しい値が得られますが、コストが等価で無い場合は正しくない結果になる場合があります。

今回行った工夫

今回は、下図のように直進できる所までやりきってしまい、更新可能な場合どこから進んできたかを別のgridに保存します。

移動コストが等価の場合だと有り難みがわかり難いですが、それぞれ異なる移動コストの場合、あるマスは上移動で来るのが最短だが、すぐ隣の別のマスは右移動で来るのが最短、というのをそれぞれ保持できて嬉しいです。

おわりに

AHC003では、理論値を100%とした際、一般的なダイクストラ法にカーブ時ペナルティを加えたもので93%、上記工夫を行うことで96%と、3%スコアアップしました。もちろん、そもそもの盤面推定の方が重要な問題ですが、雑な盤面推定でもそこそこのスコアが取れたので、学びを得ました。