機械学習この記事では、最短経路探索などでよく使われている「A*アルゴリズム」について紹介します。
A*アルゴリズムは、 Peter E, Hartらによって提案された経路探索アルゴリズムです。
各頂点$n$からゴールまでの距離の推定値$h^*(n)$を知っていた場合に対して最短経路問題を効率的に解くことができます。
このアルゴリズムでは、スタートノードからあるノード$n$を通ってゴールノードまでたどり着くときの最短経路を考えます。
A*アルゴリズムの大まかな処理の流れは以下の通りです。
① スタートノード$S$、ゴールノード$G$、Openリスト、Closeリストを用意する。
② $S$をOpenリストに追加する。
・$S$の推定コスト$f^*(S)$を以下の計算式で求める。
$f^*(S)=g^*(S)+h^*(S)=0+h^*(S)=h^*(S)$
③ Openリストが空なら探索失敗として終了する。そうでなければ、Openリストから最小の$f^*(n)$を持つノードを抽出し、これを親ノード$n$とする。
・親ノード$n$がゴールノード$G$と同じ($n=G$)なら探索処理を終了して手順⑥へ進む。そうでなければ親ノード$n$をOpenリストから削除してCloseリストに追加する。
・親ノード$n$に隣接する移動可能な全てのノードを子ノード$m$とする。
④ 全ての子ノード$m$の仮推定コスト$f'(m)$を以下の計算式から求める。
$f'(m)=g^*(n)+h^*(m)+COST(n,m)$
($g^*(n)=f^*(n)-h^*(n)$)
・状態と仮推定コスト$f'(m)$の値に応じて、各子ノード$m$に対して(a)～(d)のいずれかの操作を行う。
(a)「子ノード$m$状態がNone」の場合
・$f^*(m)=f'(m)$とする。
・子ノード$m$をOpenリストに追加する。
・子ノード$m$の親を$n$として記録する。
(b)「子ノード$m$状態がOpen」かつ「$f'(m)<f^*(m)$」の場合
・$f^*(m)=f'(m)$に置き換える。
・子ノード$m$の親を$n$として記録する。
(c)「子ノード$m$状態がClose」かつ「$f'(m)<f^*(m)$」の場合
・$f'(m)<f^*(m)$なら$f^*(m)=f'(m)$に置き換える。
・子ノード$m$をCloseリストから削除してOpenリストに追加する。
・子ノード$m$の親を$n$として記録する。
(d)上記以外の場合は何もしない。
⑤ ③以降を繰り返す。
⑥ 探索終了後、ゴールノード$G$から記録しておいた親ノード$n$を順次辿ると最短経路が得られる。
ノード$n$：親ノード
ノード$m$：子ノード(親ノード$n$に隣接している移動可能なノード)
$h^*(m)$：親ノード$n$からゴールノードまでの推定最小コスト(最短距離)
$g^*(n)$：スタートノードから親ノード$n$までの推定最小コスト(最短距離)
$COST(n,m)$：親ノード$n$から子ノード$m$へ移動するときのコスト(距離)
$f^*(m)$：スタートノードから子ノード$m$を経由してゴールノードに到達するまでの推定最小コスト(最短距離)
$f'(m)$：$f^*(m)$の候補値で$f'(m)=g^*(n)+h^*(m)+COST(n,m)$で算出
ステータス：ノードの状態（初期状態：None、計算中：Open、計算済：Close）
Openリスト：状態がOpen(計算中)のノードを格納するリスト
Closeリスト：状態がClose(計算済み)のノードを格納するリスト
<
h2>A*アルゴリズムの計算例
今回の計算例では、各推定値を以下の値で計算します。
$h^*(m)$：子ノード$m$からゴールノード$G$までのマンハッタン距離
$g^*(n)$：スタートノード$S$から親ノード$n$までのマンハッタン距離
$COST(n,m)$：1
$f'(m)$：$f'(m)=g^*(n)+h^*(m)+COST(n,m)=g^*(n)+h^*(m)+1$
$f^*(m)$：子ノード$m$が複数ある場合、それぞれの$f'(m)$の中で最も小さい値
(子ノード$m$が1の場合は$f^*(m)=f'(m)$)
今回の数値例では、以下のような縦横5マスの地図を対象として$S$～$G$の最短経路を求めます。
（斜め移動は可能：8方向移動、障：障害物で移動不可）
元地図から各ノードの「状態と推定コストを記録するマップ」と「親ノードの位置を記録するマップ」を用意します。
「状態と推定コストを記録するマップ」がスタートノード$S$、 ゴールノード$G$、Openリスト、Closeリストに相当します。
スタートノード$S$の状態をNoneからOpenにします。(Openリストに追加)
スタートノード$S$の親ノードの位置を記録します。($S$に親ノードはないのでNull)
$f'(S)$を計算します。(Sは1つしかないので$f^*(S)=f'(S)$となる)
\begin{eqnarray}
g^(S)&=&0\
h^(S)&=&5\
f^(S)&=&f'(S)=g^(S)+h^*(S)+1=0+5+1=6
\end{eqnarray}
$g^*(S)$はスタート地点なので0となります。
$h^*(S)$は障害物は無視したスタートノード(S)とゴールノード(G)のマンハッタン距離なので5となります。
よって、$f^*(S)$は6になります。($S$の推定コスト6をマップに記録)
マップにはOpen状態のノード(スタートノードS)があります。(=Openリストは空でない)
よって、探索は続行します。
Open状態のノードはスタートノード$S$しかないため、これを親ノード$n$に設定します。
$n\neq G$なので、探索終了せず親ノード$S$の状態をCloseにします。(Closeリストに追加)
親ノード$S$に隣接する移動可能な全てのノードを子ノード$m$に選びます。
全ての子ノード$m$の仮推定コスト$f'(m)$を計算します。($m$は5つあるので$f'(m)$も5つ計算)
\begin{eqnarray}
h^(S)&=&5\
g^(n)&=&g^(S)=f^(S)-h^(S)=6-5=1\
f'(m)&=&g^(n)+h^(m)+1=h^(m)+2
\end{eqnarray}
上式より子ノード$m$からゴールノードまでのマンハッタン距離を計算すれば$f'(m)$が求まります。
（例：子ノード$(0,0)$の場合、$m$～$G$のマンハッタン距離は7なので推定コストは9となります。
5つの子ノード$m$の状態はNoneなので、$f*(m)=f'(m)$とし ます。($f^*(m)$の値はマップに記録)
また、5つの子ノード$m$の状態をOpenにします。(Openリストに追加)
5つの子ノード$m$の親ノード$S$をマップに記録します。
マップにはOpen状態のノードが5つあります。(=Openリストは空でない)
よって、探索は続行します。
状態がOpenで推定コスト$f^*(n)$が最小なノードを次の親ノード$n$に設定します。
親ノードの条件を満たすノードは$(2,0), (0,0)$の2つあります。
どちらを選んでもいいですが、今回はノード$(2,0)$を親ノードにして計算します。
親ノード$(2,0)$は$G$と同じではないので、探索は終了せず親ノード$(2,0)$の状態をCloseにします。(Closeリストに追加)
親ノード$(2,0)$に隣接する障害物以外のノードを子ノードに選びます。
$f'(m)$を計算します。(子ノード$m$は3つあるので$f'(m)$を3つ計算する)
\begin{eqnarray}
h^(S)&=&5\
g^(n)&=&f^(n)-h^(n)=7-5=2\
f'(m)&=&g^(n)+h^(m)+1=h^*(m)+3
\end{eqnarray}
よって、2つの子ノード$m$からゴールノードまでのマンハッタン距離を計算すれば$f'(m)$も求まります。
（例：子ノード$(1,0)$～ゴールノード$G$のマンハッタン距離は6なのでこのノードの推定コスト$f'(m)$は9(=6+3)となります。
3つの子ノード$m$のうち、$(3,0),(3,1)$の状態はNoneなので、$f*(m)=f'(m)$とします。($f^*(m)$の値はマップに記録)
$(3,0),(3,1)$の状態をOpenにします。(Openリストに追加)
$(3,0),(3,1)$の親ノード$S$をマップに記録します。
残り1つの子ノード$(1,0)$の状態はOpenで仮推定コスト$f'(m)$は9です。
前回の計算結果より$f^*(m)$は8なので$f'(m)>f^*(m)$となります。
よって$(1,0)$に関しては何も操作を行いません。
以後、「3.次の親ノード$n$と子ノード$n$を決定」→「 次の子ノード$m$を探索」を繰り返していきます。
すると、何回か繰り返すうちに親ノード$n$がゴールノード$m$に到達します。（探索終了）
その時のマップは以下のようになります。
親ノードを記録したマップを用いて、ゴールノード$G$から親ノード$n$を辿っていきます。
(ゴールノード$(4,3)$の親ノードは$(4,2)$、$(4,2)$の親ノードは$(3,1)$・・・)
すると、最終的にスタートノード$S$までたどりつきます。これが最短経路の各座標となります。
以上で、A*アルゴリズムの説明は終わりとなります。
<
blockquote>
【参考文献】
・A-star Shortest Path Algorithm (C++ recipe)
・よくわかるA*(A-star)アルゴリズム (Unity2Dのサンプルコードつき)
・A* (A-star, エースター) 探索アルゴリズムのメモ
コメント