A* 알고리즘

지금까지 BFS, Dijksta 와 같이 써먹어왔던 알고리즘은 '모든' 길을 탐색해야 한다는 사실이 있다..
 
따라서, 모든 지점이 탐색된다는 불편함이 존재한다. 길찾기를 할 때는 목적지만 보는게 더 좋기 때문!
 
그래서 이를 개선한 알고리즘이 바로 A* 알고리즘이다.
 
A* 알고리즘에서 새로운 개념이 등장하는데 그것은 휴리스틱이다.
 
휴리스틱은 길을 어림잡아 매긴 수치이다.

파란색이 길이고, 빨간색이 벽이고 녹색이 도착지점이다.
 
여기서 휴리스틱은 3이다.. 내가 갈 수 있는 길인지 판단하지 않고 그냥 나와 목적지까지의 거리를 가중치로 부여하는것.
 
그래서 현재 거리와 (G) 휴리스틱(H)가 더해진 값 F로 계산을 진행한다. (F = G + H)
 
이렇게 아무 의미 없이 탐색을 하는 다익스트라와 달리 이 휴리스틱이 추가되어서 목적지와의 관계가 선명해진 
알고리즘이 바로 A* 알고리즘이다.
 
 
이제 A* 알고리즘을 구현해보자.
 
 
 
좌표와 가중치를 가지고 있는 구조체를 하나 만들고 

 
구조체를 넣는 우선순위 큐를 가지고 있는다..
 
전에는 반복문을 통해서 모든 예약 리스트 중 Distance를 비교해서 가장 작은 아이를 가져왔다면, 이제는 우선순위 큐를 사용해서 반복문을 사용하지 않고 가볍고 빠르게 가져올 수 있다. 우선순위 큐가 빠른것은 저번에 증명된 사실 Log(N)의 시간복잡도를 가지고 있다.
 
그래서 일단 처음에는 시작점이 0이니까 G는 0이고 H만 계산한 값을 우선순위 큐에 넣는다.

이제 BFS 혹은 다익스트라와 거의 동일하다. 
 
예약(우선순위 큐) 에서 꺼내서 내가 갈수있는길을 또 예약하고 꺼내고 예약하고... 

이제 비용 계산을 하는데, 이것도 다익스트라에서 맞닥드린 문제와 같이 처음 가는 비용이 작아서 그쪽으로 갔는데? 최종적으로는 다른 길이 더 비용이 작을수도 있기에 체크를 해 준다.
(하지만 이 타일맵에서는 한칸당 가는 비용이 1이니 결국 휴리스틱 수치로만 판단이 되기때문에
경로에따라서 G가 바뀌지 않아 별 의미가 없음)
 
예약 리스트에 비용을 넣고, 우선순위 큐에도 구조체를 넣는다. 
 

내가 만약 정 가운데에 있다고 치면은 일단 상하좌우 모두 큐에 들어가지만 우선순위 큐에 따라서 최저비용으로 빨간색 지점이 다음 Dequeue로 나올것.