【えーすたーあるごりずむ】
A*アルゴリズム とは？
最終更新:
💡 「ここまで＋あとどれくらい？」で次の候補を選ぶ
現在までの経路コストとゴールまでの推定コストを足して、次に調べる候補を選ぶ経路探索アルゴリズム。評価値と最短経路を得るための条件を説明します。
📌 このページのポイント
- f(n)=g(n)+h(n)の小さい探索候補を優先する
- gは現在までの経路コスト、hはゴールまでの推定コスト
- 最短経路を得るには推定値と探索方法の条件が必要
- 推定を全て0にすると、一様コスト探索と同じ選び方になる
ひよこ A*は、ゴールに近い場所から調べるの？
ペンギン先生 近さの見積もりだけではなく、ここまでの経路コストgと、ゴールまでの推定コストhを足すんだ。探索待ちの候補の中でf=g+hが小さいものを優先して調べるよ。
ひよこ どんなふうに足すの？
ペンギン先生 候補Aがg=3、h=4ならf=7。候補Bがg=5、h=1ならf=6だから、この二つならBを先に調べる。ゴールに着くまでの合計を見積もっているんだ。fは推定値で、最終的な経路コストとは区別しよう。
ひよこ ゴールまでの推定はどう作るの？
ひよこ いつでも最短経路が見つかって、速くなる？
もっと詳しく知りたい人へ
ヒューリスティックの「一貫性」とは？
隣接する地点nとn′について、h(n)が移動コストc(n,n′)+h(n′)を超えず、ゴールのhが0になる条件です。移動に伴って残りの見積もりが不自然に大きく減ることを防ぎます。調べ済みの地点を再展開しないA*のグラフ探索で、最適性を保つために使われます。過大評価しないだけの見積もりと区別してください。
📖 おまけ：英語の意味
「A* search」 ＝ A*（エースター）探索
💬 A*の「*」はスターと読みます。経路探索では距離だけでなく、所要時間などをコストとして扱うこともできます。