A*の考え方
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/08/01 02:02 UTC 版)
スタートノードから、あるノード n を通って、ゴールノードまでたどり着くときの最短経路を考える。このときこの最短経路のコストを f* (n) とおくと、 f* (n)= g* (n) + h* (n) と置くことが出来る。ここで g* (n) はスタートノードから n までの最小コスト、h* (n) はn からゴールノードまでの最小コストである。もし g* (n) の値と h* (n)の値を知っていれば、全体の最短経路f* (n) は容易に求まる。しかしながら実際には g* (n) と h* (n) をあらかじめ与えることは出来ない。そこで f* (n) を次のような推定値 f (n) に置き換えることを考える。 f ( n ) = g ( n ) + h ( n ) {\displaystyle f(n)=g(n)+h(n)} ここで g(n) はスタートノードから n までの最小コストの推定値、h(n) は n からゴールノードまでの最小コストの推定値である。この場合 g に関しては探索の過程で更新を加えることによりg*に近づけてゆくことができるが、 h* は、実際にゴールに辿り着くまでは誰にもわからない。そこで、 h(n) には人間が(ある程度妥当性を持つように)設計した推定値を与えることにする。このアルゴリズムを A*探索アルゴリズムといい、 h (n) をヒューリスティック関数という。
※この「A*の考え方」の解説は、「A*」の解説の一部です。
「A*の考え方」を含む「A*」の記事については、「A*」の概要を参照ください。
ウィキペディア小見出し辞書の「A*の考え方」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- A*の考え方のページへのリンク
