A* 알고리즘

작성일 | In

이 알고리즘은 출발점부터 도착점까지의 최단 경로(정확히는 최단 경로에 근접한 결과)를 알아내는 알고리즘입니다.

아래와 같은 8 * 4 크기의 맵으로 예시를 들어 설명하겠습니다. 빨간 칸은 장애물, s는 start 즉 시작점이고 e는 end 즉 도착점입니다. 그림의 왼쪽과 위에 있는 숫자들은 좌표를 나타냅니다. (스크린 좌표계이며 0부터 시작합니다.)


경로를 찾기 위해서는, 당연하겠지만 탐색을 합니다. 탐색을 하기 전에, 알고리즘 구현에 쓰이는 함수들과 필요한 자료구조와 알고리즘에 대해 간략히 알아보도록 하겠습니다.

먼저, A* 알고리즘은 휴리스틱 기반의 탐색을 합니다. 휴리스틱 기법에 대해 간단히 말하면, 체계적이고 합리적인 판단이 굳이 필요하지 않을 경우 경험에 기반하거나 어림짐작을 통해 판단을 하는 방법입니다. 완전한 최적해를 보장하지는 않지만 대개 최적해에 근접한 답을 구해줍니다. A* 알고리즘에서는 두 가지의 함수를 결합해 휴리스틱 추정 값을 구합니다.

추정 값(가중치)를 F라는 함수로 구하고, F라는 함수는 G라는 함수와 H라는 함수의 합입니다. G함수는 시작점으로부터 새로운 노드(위 그림에서는 사각형)까지의 이동 비용이고, H함수는 다음으로 갈 노드부터 도착점까지의 예상 이동 비용입니다.

G함수의 값은 현재 노드의 F값과 새로운 노드로 가는데 드는 비용으로 결정됩니다. 새로운 노드로 가는데 드는 비용은 계산을 간단하게 하기 위해 가로/세로 이동시에는 10, 대각선 이동시에는 14를 적용할 것입니다. H함수의 값은 계산은 마찬가지로 간단하게 하기 위해 새로운 노드부터 도착점까지 장애물을 무시한 채로 가로/세로 이동 비용에 10을 곱한 값을 적용할 것입니다. (Manhattan Distance라고 합니다.)

G함수의 값은 scoreG[ ][ ], H함수의 값은 scoreH[ ][ ], F함수의 값은 scoreF[ ][ ] 배열에 저장한다고 가정합시다. 좌표는 C++ STL의 pair를 사용할 것이며 typedef 구문을 이용해 pair<int, int>를 dot으로 칭할 것입니다.

H, G, F함수를 구현해봅시다.

1
2
3
4
5
6
7
8
9
10
11
12
13
 void h(dot end, dot next){
     int x = abs(end.first - next.first);
     int y = abs(end.second - next.second);
     scoreH[next.second][next.first] = (x + y) * 10;
 }

 void g(dot now, dot next, int plus){ //plus는 10 또는 14
     scoreG[next.second][next.first] = scoreF[now.second][now.first] + plus;
 }

 void f(dot next){
     scoreF[next.second][next.first] = scoreG[next.second][next.first] + scoreH[next.second][next.first];
 }

원래의 A* 알고리즘은 Open List(열린 목록)과 Close List(닫힌 목록)을 사용하여 노드들을 관리하지만 Close List만 사용해도 무방하기 때문에 닫힌 목록만을 사용할 것입니다. 장애물이나 이미 경로가 확정된 노드는 닫힌 목록에 삽입하여 다시 탐색하는 일이 없도록 방지해주는 기능을 수행합니다. 닫힌 목록은 C++ STL에 있는 자료구조 set을 쓸 것입니다. 전에 구현했던 코드는 vector 컨테이너를 사용했지만, vector 컨테이너는 탐색에 O(n)이 소요되는 반면, set은 탐색에 O(log n)이 소요되기 때문에 속도 향상을 위해 set을 쓸 것입니다.
그리고, 휴리스틱 추정 값이 가장 낮은 노드를 찾을 때에는 우선순위 큐(priority_queue)라는 자료구조를 사용할 것입니다. 우선순위 큐는 최소 값을 찾을 때 O(log n)이 소요됩니다.


이제 이 사진에서 탐색을 해봅시다.
S(0, 3)에서 탐색을 시작합니다. S의 g, h, f값은 모두 0입니다.
먼저 (0, 3)을 닫힌 목록에 넣읍시다. 그 뒤, (0, 3)과 인접한 8개의 노드(대각선 포함)의 f값을 알아볼 것입니다. 하지만 인접한 노드는 벽을 제외하면 3개이기 때문에 3개의 f값만 구하면 됩니다.

(1, 3)은 g값이 10 (이전 노드의 f값 + 10), h값은 90, f값은 100입니다. (1, 3)의 가중치를 100으로 정한 뒤, 우선순위 큐에 넣어줍시다.
(0, 2)는 g값이 10 (이전 노드의 f값 + 10), h값은 90, f값은 100입니다. (0, 2)의 가중치도 100으로 정한 뒤, 우선순위 큐에 넣어줍시다.
(1, 2)는 g값이 14, h값은 80, f값은 94입니다. (1, 2의 가중치를 94로 정한 뒤, 우선순위 큐에 넣어줍니다.

(0, 3)에서 갈 수 있는 모든 노드에 대한 탐색이 끝났습니다. 3개의 노드 중, 가중치가 가장 작은 (1, 2)를 닫힌 목록에 넣고 (1, 2)에서 탐색을 계속합니다. 마지막으로 우선순위 큐를 비우고 scoreF, scoreG, scoreH배열을 초기화합니다.

이제 (1, 2)에서 탐색을 진행하겠습니다. 8방향으로 탐색을 하지만, 이미 닫힌 목록에 추가된 (0, 3)과 (1, 2)를 제외하고 탐색합니다. G+H 형태로 나타내면 다음 사진처럼 결과가 나옵니다.


f값이 가장 작은 (2, 1)로 이동합니다.

이런 식으로 주변 노드들의 f값을 구한 뒤, 가장 작은 노드를 선택을 하면서 탐색을 합니다.

휴리스틱 방식을 사용하기 때문에 완벽한 최적해를 보장하지는 않지만, 처음에 말했듯이 최적해에 인접한 결과를 냅니다.
dijkstra나 BFS, floyd-warshall과 같은 알고리즘보다 훨씬 빠르면서 최적해에 인접한 결과를 내기 때문에 스타크래프트를 비롯한 게임에서 많이 사용이 됩니다.

데모 프로그램은 아래 소스코드이며, 구성은 a_star.h 라는 헤더 파일과 그 헤더 파일의 사용 예제인 a_star_use_header.cpp 파일입니다. a_star.h의 사용 방법은 a_star.h를 include한 뒤, a_star(map, map_x, map_y start, end)와 같이 함수를 호출하면 경로를 출력합니다. map_x는 가로 칸 수, map_y는 세로 칸 수이고, start와 end는 pair<int, int> 형(dot형)입니다.
위 헤더 파일을 이용하면 지도는 사용 범위가 좁더라도 선언할 때에는 항상 101*101 사이즈로 선언해야 합니다. 이동 가능한 칸은 *, 불가능한 칸은 $로 쓰시면 됩니다.

데모 프로그램을 활용하기 보다는 직접 구현해보시기를 권장합니다.

–a_star.h–

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;

typedef pair<int, int> dot;
typedef pair<int, dot> weight;

dot a, b;
priority_queue< weight, vector<weight>, greater<weight> > pq;
vector<dot> ans;
//vector<dot> closed;
set<dot> closed;
int scoreF[101][101];
int scoreG[101][101];
int scoreH[101][101];

void h(dot end, dot next){ //맨해튼 거리 사용
	int x=abs(end.first - next.first);
	int y=abs(end.second - next.second);
	scoreH[next.second][next.first] = (x + y) * 10;
}

void g(dot now, dot next, int plus){
	scoreG[next.second][next.first] = scoreF[now.second][now.first] + plus;
}

void f(dot next){
	scoreF[next.second][next.first] = scoreG[next.second][next.first] + scoreH[next.second][next.first];
}

void a_star(char map[101][101], int map_x, int map_y, dot a, dot b){
	if(map_x < 1 || map_x > 100 || map_y < 1 || map_y > 100){
		printf("x, y의 범위는 1이상 100이하 입니다.\n");
		return;
	}

	memset(scoreF, 9999, sizeof(scoreF));
	memset(scoreG, 9999, sizeof(scoreG));
	memset(scoreH, 9999, sizeof(scoreH));

	pq.push(make_pair(0, a));
	ans.push_back(a); //시작 노드 저장

	for(int i=0; i<map_y; i++){
		for(int j=0; j<map_x; j++){
			if(map[i][j] == '$') closed.insert(make_pair(j, i));
		}
	}

	dot now; //현재 노드 저장
	while(ans.back() != b){
		dot now = pq.top().second;
		closed.insert(now); //현재 노드를 닫힌 목록에 삽입
		pq.pop();

		pq = priority_queue< weight, vector<weight>, greater<weight> >(); //우선순위큐 초기화
		ans.push_back(now);

		memset(scoreG, 9999, sizeof(scoreG));
		memset(scoreH, 9999, sizeof(scoreH));

		int dx[8]={0, 1, 1, 1, 0, -1, -1, -1};
		int dy[8]={1, 1, 0, -1, -1, -1, 0, 1};

		for(int i=0; i<8; i++){
			int x = now.first + dx[i], y = now.second + dy[i];
			if(x < 0 || y < 0) continue;

			auto p = closed.find(make_pair(x, y));
			if(p != closed.end()) continue;

			h(b, make_pair(x, y));
			if(dx[i] == 0 || dy[i] == 0) g(now, make_pair(x, y), 10);
			else g(now, make_pair(x, y), 14);

			memset(scoreF, 9999, sizeof(scoreF));
			f(make_pair(x, y));

			weight pushed = make_pair(scoreF[y][x], make_pair(x, y));
			pq.push(pushed);
		}
	}
	for(int i=0; i<ans.size(); i++){
		printf("%d %d\n", ans[i].first, ans[i].second);
	}
}

–a_star_use_header.cpp–

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include "a_star.h"
typedef pair<int, int> dot;

int main(){
    const int map_x=8;  //가로 칸 수
    const int map_y=4;  //세로 칸 수
    char map[101][101]={  //지도(무조건 101*101로 선언해야 합니다.)
        "$**$****",
        "*$***$**",
        "*****$**",
        "*****$**"
    };
    dot a=make_pair(0, 3), b=make_pair(7, 0);
    a_star(map, map_x, map_y, a, b);
}