Panda Noir

JavaScript の限界を究めるブログでした。最近は幅広めに書いてます。

アルゴリズム勉強会 第三回 A*探索

久しぶりにこのシリーズ書きました。シリーズ一覧はこちらから

A*アルゴリズムとは?

「今までにかかったコスト + これから先の推定されるコスト」が最小になるノードを選びながら探索していくアルゴリズムです。

最短経路探索を考えると分かりやすいです。現在地からゴールまでの経路を考えます。

  1. まず隣接した都市を見ます
  2. 隣接都市のうちゴールまでの直線距離が短い(これが推定されるコスト)都市を選びます
  3. その都市を起点にさらに隣接都市を見ます
  4. これを繰り返してゴールまで探索します。

こうするとたとえ障害物が途中にあったとしても最短になります。

どういうときに使うのか

このアルゴリズムは「最短ルート探索」の他に「15パズルを解く」、「NLPで確率論的文法を使用したパース」などにも使えるそうです。後者は英語版wikiに書いてあったのですがサッパリわかりません。

h*関数を適切に設定すればおそらくルービックキューブも解けると思います。

実際のコード

実際にA*を使って最短経路を計算するプログラムを書いてみました。GitHubに置いたのでご覧ください。

GitHub - pandanoir/a-star: A* algorithm in JS