티스토리 뷰
A* 알고리즘은 특정상태에 이웃한 녀석들을 탐색하면서 시작 상태에서부터 목표 상태에 이르는 가장 싼 비용의 경로를 찾는 알고리즘이다.
공간을 어떻게 분할해서 하냐에 따라서 같은 A*이지만 다양한 방식으로 나올 수 있는데, 제일 간닪나 형태인 정사각형 격자 형태에서 보자면.
정사각형 격자에서는 이웃한 노드들을 탐색하기 아주 좋다.
A*는 열린 목록과 닫힌 목록 2가지의 상태 목록을 관리한다.
열린 목록엔 처음 시작점만을 가지고 시작을 하고 처음 시작점에서 이웃한 노드들을 탐색하고 가장 비용이 싼 노드로 이동한다.
그리고 열린 목록에서는 그 노드를 지우고 닫힌 목록에다가 넣는다.
그런식으로 가장 비용이 싼 노드들을 찾으면서 길을 찾게 된다.
물론 이미 열린 목록이나 닫힌 목록에 있는 노드는 또 추가하거나 하지 않는다.
그리고 여기서 비용이란 시작점에서 부터 현재 노드까지의 비용과 현재 노드에서 도착점까지의 비용을 합한 비용이다.
이때 비용은 장애물과 상관없이 구하는데, 좌,와, 위,아래로 이동시엔 10 그리고 대각선 방향으로는 14를 비용으로 포함한다.
이렇게 하지 않아도 되긴하는데 보통 정사각형 격자라고 하고 한변이 10이라고 할때 대각선방향은 200루트이니깐 약 14가된다.
그래서 10과 14를 쓴다.
A*는 맵의 크기가 크면 열린 목록이나 닫힌 목록에 엄청 많은 노드들이 들어가게되고 메모리를 엄청 많이 잡아먹으며, 상당한 시간의 cpu시간을 잡아먹는다.
특히 시작점에서 도착점까지 갈 수 없는 경로가 없는 경우에 시작점에서 인접한 모든 노드를 검색하고서야 가지 못한다는걸 알게 된다.
매우 비효율적이다.
A*는 맵이 커지면 느려질수 밖에 없으며 해결책은 검색 공간을 최적화하는 것과, 알고리즘 최적화 밖에 없다는 것이다.
정리하기 귀찮으니 좀 더 깊게 공부하면 알아보도록 하자.
