アルゴリズムとプログラミング
A*アルゴリズムについての説明として最も正しいものはどれか。
ア.全経路を探索した後に最短経路を返す総当たりアルゴリズムである
イ.重みなしグラフでのみ有効な探索アルゴリズムである
ウ.ランダムなノードを選択して探索する確率的アルゴリズムである
エ.ヒューリスティック関数h(n)を利用してゴールに近いノードを優先的に探索する最良優先探索アルゴリズムである正解
解説
A*は「カーナビの賢い経路案内」そのもの。普通のダイクストラは「これまでの距離だけ」で判断するが、A*は「これまでの距離(g)＋ゴールまでの推定距離(h)」を合計したf=g+hで判断する。地図上で目的地の方向にある道を優先して案内することで、余計な道を探索せずに最短経路を速く見つけられる！
なぜ エ が正解か
A*アルゴリズムの核心：評価関数 f(n) = g(n) + h(n)①g(n)：スタートからノードnまでの実際のコスト②h(n)：ノードnからゴールまでの推定コスト（ヒューリスティック関数）③f値が最小のノードを優先探索（最良優先探索）。h(n)が許容的ヒューリスティック（実際のコストを超えない推定）なら最適解を保証。ダイクストラはh(n)=0のA*の特殊ケースと見なせる。
出典: AI生成問題（学習用）