[Algorithm][Path Planning] A* 구현하기

순서 생략

 

A*는 기본적으로 Open Queue와 Close Queue가 있다.

알기 쉽게,
Open Queue = 내가 곧 가봐야 할 길
Close Queue = 가봤던 길
이라고 생각하자.

PathPlanning 비교 글처럼

다른 탐색들과 같이 같이 생각해 보면

Open Queue
Explore -> 많이 들어갈수록 시간이 늦어지고 다 탐색해야 함
-> 하지만 Priority Queue로 구현하면 Enqueue는 하지만 모두 열 필요는 없다.

Close Queue
Path Planning -> 마지막에 지나온 경로를 역추적하여 경로 확정

 

아래 순서를 보자.

Heuristic은 다양한 방법이 있는데 간단히 거리로 하였다. (생각대로...)
대각선은 대충 값을 넣은 것이므로 큰 의미를 부여하진 말자.
G가 제일 중요하다 ( Dijksta에서의 가중치와 같다 )

 

---

 

+) 가중치 F가 더 작은 (경로를 이동하는데 더 적은 소모값이 드는)
start->2 가 cur이 된다.

---

 

---

 

+) 가중치가 제일 적은, 미리 Queue에 등록된
start->1 이 cur가 된다.

---

 

---

** 제일 중요한 페이지 

 

여기만 알면 나머지는 똑같이 진행하면 된다.

Description에서 추가로 설명하자면

case1. 이미 왔다간 길인경우 (Close Queue)

가중치가 없는 BFS 같은 경우는 close Queue를 따로 만들지 않고 그냥 도착하면 끝낸다.
Dijkstra의 경우에는 가중치는 있지만 Greedy는 아니기 때문에 가중치를 비교해봐야 한다.
A*는 이미 도착을 해봤던 길이라면 무시해도 된다.

case2. 가봐야 할 길인경우 (Open Queue)

아직 가보지 않았기 때문에 F 값이 변할 수 있으므로 비교해서 교체해야 한다.

case3. 마무리

BFS의 경우 next가 goal인 경우 그냥 끝내면 되지만
Dijkstra나 A*의 경우 어떤 길이 더 효과적인지 모르기에 goal까지 도착했을 때
결과 값을 비교해 보아야 한다.