|
[A* 알고리즘을 사용한 길찾기] - 우종하(deepseas(AT)sogang.ac.kr)
- 소스코드
[Down]
A* 알고리즘의 개요 A*(에이 스타) 알고리즘은 1968년에 만들어진 것으로, 탐색을 수행하는데 있어 매우 효과적인 알고리즘이며 다양한 종류의 문제들을 해결하는데 사용되어 왔다. A* 알고리즘은 출발지점에서 목표지점까지 가장 비용이 낮은(보통 가장 짧은) 경로를 찾는데, 다음과 같이 'f = g + h' 계산값을 사용하여 다음으로 이동할 경로를 결정한다. g는 goal(목표)로서, 시작노드로부터 이 노드까지 오는 데 드는 비용이다. 시작노드에서 이 위치까지 오는 경로들은 여러 개가 있을 수 있는데, 이 노드는 그 경로들 중 특정한 하나를 의미한다. h는 heuristic(휴리스틱)으로, 이 노드에서 목표까지 가는데 드는 '추정된' 비용이다. 이때 h는 휴리스틱을 의미하며, 휴리스틱이란 '경험에 기초한 추측'을 뜻한다. 이것이 '추측된' 비용인 이유는 목표까지의 실제 비용을 아직은 알지 못하기 때문이다. 휴리스틱을 계산하는데 여러 가지 방법이 있을 수 있지만, 일반적으로 현재 위치에서 목표까지의 일직선 거리값을 사용한다. f는 fitness(적합도)로서, g와 h의 합이고 이 노드를 거쳐 가는 경로의 비용에 대한 최선의 추측을 의미한다. f값이 낮을수록 이 경로가 최단 경로일 가능성이 크다. 현재위치에서 다음의 어떤 노드로 이동할 것인가를 결정하는 방법은 다음과 같다. 현재위치에 연결된 다음 노드가 여러개일 경우, 각각의 다음 노드마다 시작위치에서 다음 노드까지의 거리와 그 노드에서 목표까지의 추정된 휴리스틱 값을 더한 f값들을 계산하여, f값이 가장 작은 노드쪽으로 이동하는 것이 목표까지의 가장 짧은 경로가 될 가능성이 높다. 이렇게 f값이 가장 작은 노드들을 선택하여 탐색을 수행하다 목표노드에 도착하면 탐색을 종료한다.
A* 알고리즘의 예 아래 그림과 같이 A* 알고리즘을 사용하여 Arad에서 Bucharest까지의 가장 짧은 경로를 구하는 예를 살펴보자
위의 그림은 각 도시들의 위치를 나타낸 지도이다. 각 도시를 연결하는 선의 숫자는 도시사이의 거리를 뜻한다. 오른쪽 표는 각 도시에서부터 Bucharest까지의 직선거리를 나타내는데 여기서는 휴리스틱 값으로 쓰이고 있다.
처음 Arad에서 갈 수 있는 도시는 위의 그림처럼 Sibiu, Timisoara, Zerind 세 도시가 있는데, 각각 'f = g + h' 식을 사용하여 f값을 구해보자. Sibiu의 경우 g는 Arad에서 Sibiu까지의 거리이므로 140이고, h는 Bucharest까지의 직선거리를 휴리스틱으로 사용하므로 표에서와 같이 253이다. 그러므로 f = 140 + 253 = 393이 된다. 마찬가지로 나머지 도시의 f값은 각각 447, 449가 되는데, 이 중 f값, 즉 현재까지의 거리와 현재위치에서 목표까지의 거리가 가장 작을 것 같은 값이 가장 작은 도시는 Sibiu이므로 그 쪽으로 이동을 하는 것이 가장 유리할 것이다. 이렇게 f값이 가장 작은 경로를 따라 탐색을 수행하면 Bucharest까지의 가장 짧은 경로를 구할 수 있다.
A* 알고리즘을 사용한 길찾기 방법 여러 가지 탐색 알고리즘 중 가장 효율적인 A* 알고리즘은 여러 문제해결을 위해 사용되는데, 특히 게임에서와 같이 여러 장애물이 있는 맵상에서 목표위치까지의 경로를 구하는데 효과적으로 사용되어 진다. 길찾기 문제에서 하나의 상태(노드)는 게임세계에서 유닛이 차지하고 있는 특정한 위치로 구성되며, 인접한 상태는 유닛이 직접 이동할 수 있는 인접한 위치로 구성된다. 현재 상태에서 아직 조사하지 않은 상태들 중 가장 유망한 상태를 조사하는 과정을 반복한다. 이때 그 상태가 목표이면 길찾기는 끝나고, 그렇지 않으면 그 상태의 인접한 상태를 조사해 나간다. 좀 더 구체적으로 살펴보면 다음과 같다. A* 알고리즘은 두 종류의 상태 목록을 관리한다. 하나는 아직 조사하지 않은 상태들을 담은 '열린목록(Open List)'이고, 또 하나는 이미 조사한 상태들을 담은 '닫힌목록(Closed List)'이다. 알고리즘의 시작에서 닫힌 목록은 비어 있으며, 열린 목록은 오직 시작 상태(유닛의 처음 위치)만을 가지고 있다. 각각의 반복에서 알고리즘은 열린 목록의 상태들 중 가장 유망한 것을 가져온다(이때 열린 목록에서는 제거된다). 그 상태가 목표가 아니면 이웃한 위치들로 확장을 한다. 이웃 위치들이 새로운 것이면 열린 목록에 넣고, 이미 열린 목록에 있고 그것의 경로가 이전 것보다 비용이 더 싸면 그 위치의 정보를 갱신한다. 반대로, 만일 그 위치들이 이미 닫힌 목록에 있는 것이면 이미 조사를 마친 것이므로 그냥 무시한다. 목표에 도달하기 전에 열린 목록이 비이게 되면 시작 위치로부터 목표에 도달하는 경로가 존재하지 않는 것이다.
A* 알고리즘을 사용한 길찾기의 예 다음과 같이 장애물이 있는 맵상에서 실제로 A* 알고리즘을 사용하여 목표까지의 가장 짧은 경로를 찾는 예를 살펴보자. 초록색은 시작위치, 빨강색은 목표 위치이고, 파란색은 장애물로서 지나갈 수 없는 위치이다.
처음 시작위치에서 이웃노들들로 확장하며 각 노드마다 f값을 계산한다. 사각형 가운데의 그림은 이 상태에서 이전 상태를 가르키는 것으로 직선방향의 상태가 바로 이전의 지나왔던 상태이다. 각 상태마다 이전 상태의 위치정보도 저장하고 있어야 한다.
열린 상태들 중(녹색테두리) f값이 가장 작은 상태로 이동한다.
아래나 위나 f값이 똑같으므로 어느쪽으로 확장해도 상관없지만 여기선 밑으로 이동하였다. 그런 다음 인접한 상태들의 f값을 계산한다. 위의 세 상태는 이미 열린상태에 있으므로 값이 바뀌었나만 살펴보고, 밑의 두 상태는 새로운 상태이미로 f값을 계산한 후 열린상태에 집어넣는다.
이런 방식으로 f값이 가장 작은 상태들로 계속 확장을 해 나간다. 파란색 테두리는 닫힌 상태를 가르키는 것으로 이미 지나왔던 상태들을 의미한다. 그림과 같이 결국 목표상태에 도달하였다.
목표상태에 도달한 다음에는 상태마다 저장되어 있는 이전 상태의 경로를 따라 시작위치부터 목표위치까지의 경로를 구한다. 이 경로가 목표까지의 가장 짧은 경로가 되고 알고리즘은 종료된다.
[참고자료] - Game Programming Gems
1권, 정보문화사, p.340 ~ p.351
|
[1] |
