【図解】A*アルゴリズムで最短経路問題を解く方法

本稿では，A*アルゴリズムによって最短経路を求める方法を，沢山の図を使って分かりやすく説明していきます．（厳密な説明ではないことにご注意ください）

早速，以下のような迷路でスタートとゴールを結ぶ最短経路を求めていきます．
この迷路では，一辺の長さが１の正方形が並べられており，各正方形の上を１マスずつ移動していきます．
ここでは一つの正方形を**ノード**と呼ぶことにします．
移動できる方向は，基本的に縦横斜めの８方向ですが，黒塗りのノード（障害物）には移動できません．
![1.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/3d070f04-3826-25e8-9c92-90210f82e254.png)
それぞれのノードに対して，g, h, f という３つのパラメータを個別に割り当てていきます．
g はノードとスタートとの直線距離を表しており，h はノードとゴールとの直線距離を表しています．
f は g と h の和です．

全体の流れは以下のようになります．
1. スタートから順に，各ノードの探索を始める．
2. 一度通過したノードを封鎖していく．
3. 上記 1, 2 をゴールに到達するまで繰り返す．
4. 今までの探索結果を頼りに，ゴールからスタートへ**逆走すると**最短経路が求まる．


---

まずは，スタートの周辺を探索していきます．探索済みのノードには，g, h, f の値が割り当てられます．
![2.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/5ccab69b-8a05-d10d-8402-4b460bb4e122.png)
そして，探索済みのノード（黄色）の中で，最も f の値が小さいノードに移動します．ここでは，f=6 が最小です．

---

現在のノードから，さらに周辺のノードを探索し，さっきまで自分が居たノードを封鎖します．
![3.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/bab9c88d-ef4f-3bc4-1653-550c7331bed6.png)
そして，探索済みのノード（黄色）の中で，最も f の値が小さいノードに移動します．

---

現在のノードから，さらに周辺のノードを探索し，さっきまで自分が居たノードを封鎖します．
![4.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/7997e2b0-3dd5-de65-f43b-afbc245f14bf.png)
そして，探索済みのノード（黄色）の中で，最も f の値が小さいノードに移動します．

---

現在のノードから，さらに周辺のノードを探索しようとしますが，ここでは周辺に探索できるノードが無いため，探索は一旦諦めます．さっきまで自分が居たノードを封鎖します．
![5.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/3e2b8ab6-cbb7-4293-f0c9-db3deca9ffd1.png)
そして，探索済みのノード（黄色）の中で，最も f の値が小さいノードに移動します．最も小さい f が複数あった場合は，どれか１つを適当に選びます．

---

現在のノードから，さらに周辺のノードを探索しようとしますが，ここでは周辺に探索できるノードが無いため，探索は一旦諦めます．さっきまで自分が居たノードを封鎖します．
![6.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/03b7b8cd-c245-07b6-8938-407385c7b698.png)
そして，探索済みのノード（黄色）の中で，最も f の値が小さいノードに移動します．

----

現在のノードから，さらに周辺のノードを探索しようとしますが，ここでは周辺に探索できるノードが無いため，探索は一旦諦めます．さっきまで自分が居たノードを封鎖します．
![7.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/e3e0df89-01db-50f6-3ab5-434ce7dac88a.png)
そして，探索済みのノード（黄色）の中で，最も f の値が小さいノードに移動します．最も小さい f が複数あった場合は，どれか１つを適当に選びます．

---

前と同じ処理を繰り返します．
![8.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/dbc72eae-f95a-0661-d603-92afdddea847.png)
そうすると，スタートの右側にある６つのノードが封鎖されます．
![9.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/1e140cf8-6a9c-ea30-c518-a84b5bcb88aa.png)

---

現在のノードから，さらに周辺のノードを探索し，さっきまで自分が居たノードを封鎖します．
![10.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/24fb4c40-3acf-b115-6386-f9167b2fe896.png)
そして，探索済みのノード（黄色）の中で，最も f の値が小さいノードに移動します．

---

ここから先は，探索範囲が広がっていく過程をしばらく無言で並べていきます．

![13.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/faf195d8-2de8-67d1-f8e3-2e68dc391c3e.png)

![14.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/1818f33f-2909-e35f-498a-299368bc051a.png)

![15.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/23378c96-ef57-eb91-ce04-06ed5c9f6d86.png)

![16.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/94882598-212d-dd14-19e4-62774a316353.png)

![17.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/341125e6-1736-1ece-a7b6-84a5a9800f09.png)

---

現在のノードから，さらに周辺のノードを探索した結果，ゴールを発見したのでゴールに移動し，さっきまで自分が居たノードを封鎖します．
![18.PNG](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/61057a44-9aaf-1c2a-a3e0-f0b727bf5981.png)

---

最後に，ゴールからスタートに逆走することで最短経路が得られます．
逆走するための準備として，各ノードごとに親ノードの位置を記録しておく必要があります．

![last2.jpg](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/310597/166347cb-208f-5a14-4464-8e4f246e2530.jpeg)