久しぶりにこのシリーズ書きました。シリーズ一覧はこちらから。
A*アルゴリズムとは？
「今までにかかったコスト + これから先の推定されるコスト」が最小になるノードを選びながら探索していくアルゴリズムです。
最短経路探索を考えると分かりやすいです。現在地からゴールまでの経路を考えます。
- まず隣接した都市を見ます
- 隣接都市のうちゴールまでの直線距離が短い(これが推定されるコスト)都市を選びます
- その都市を起点にさらに隣接都市を見ます
- これを繰り返してゴールまで探索します。
こうするとたとえ障害物が途中にあったとしても最短になります。
どういうときに使うのか
このアルゴリズムは「最短ルート探索」の他に「15パズルを解く」、「NLPで確率論的文法を使用したパース」などにも使えるそうです。後者は英語版wikiに書いてあったのですがサッパリわかりません。
h*関数を適切に設定すればおそらくルービックキューブも解けると思います。
実際のコード
実際にA*を使って最短経路を計算するプログラムを書いてみました。GitHubに置いたのでご覧ください。
