- @ThothChildren
- 2018.8.8
- PV 388
A*探索アルゴリズム
ー 概要 ー
A*探索アルゴリズムは候補のノードのうち「それまでのコスト」+「ゴールまでの推定コスト」が最小になると思われるノードを繰り返し選択していき効率的に最短経路を探索するアルゴリズム.ダイクストラの一般化であり、「ゴールまでの推定コスト」を0にしているのがダイクストラ法.「ゴールまでの推定コスト」は自身で決める必要があり、その質に探索の効率が大きく左右される.
この章を学ぶ前に必要な知識
条件
- ヒューリスティック関数を決めておく
効果
- グラフより最短経路を求められる
ポイント
- 次のノードを選択するときには最小のコストとなるノードを選択
- コストの計算では、「そのノードまでのコスト」と「この後の推定コスト(ヒューリスティック関数で求める)」
- ヒューリステック関数の設計の良し悪しで探索効率が変わる
- 最小のコストが求められることが保障されている
- ダイクストラ法を一般化したもので、ダイクストラ法はA*探索でhの関数を常に0を返す関数としたもの
解 説
A*探索アルゴリズムは候補のノードのうち「それまでのコスト」+「ゴールまでの推定コスト」が最小になると思われるノードを繰り返し選択していき効率的に最短経路を探索するアルゴリズム.
ダイクストラの一般化であり、「ゴールまでの推定コスト」を0にしているのがダイクストラ法.
「ゴールまでの推定コスト」は自身で決める必要があり、その質に探索の効率が大きく左右される.これをヒューリスティック関数h(x)と呼ぶ.例えば二次元のグラフ上ではゴールまでのユークリッド距離やマンハッタン距離などを用いると大方筋の良い評価関数となる.
常に最小のコストを見つけ出すことができる. | A*探索アルゴリズムとは |
Wikipedia より
A*のアニメーションgif | |
A*はよく以下のように表記される.
$$f(n) = g(n) + h(n)$$
このとき\(f(n)\)はノードの推定コスト、\(g(n)\)はスタートノードからそのノードまでの最小コスト、\(h(n)\)はそのノードからゴールのどまでの推定コストを表す. | A*の表記のされ方 |
A*探索アルゴリズム処理のながれ概要
1. 候補となるノードを入れたOpenリストと計算を終えているCloseリストを用意
2. スタートノードをOpenリストに加える.
3. 「Openリストが空」か「Openリストの最小コストのノードにゴールがある」なら終了.
4. 最小コストのノードを取り出して、その隣接するノードを先のコスト計算式で更新.
5.3からを終わるまで繰り返す. | A*の探索アルゴリズム |
この章を学んで新たに学べる
Comments