A* (a-star) 알고리즘 휴리스틱

A* 알고리즘은 게임 프로그래밍 해본 사람이라면 꽤나 많이 들어본 길찾기 알고리즘일것이라고 생각한다. 좌표를 이용해서 탐색할 수 있기도 해서 그런건 아닐까. 구현하기도 많이 어려운것도 아니고.

알고리즘에 대한 자세한 설명은 다른 블로그에서도 많이 하니까 넘기고. 간단히 설명하자면 A* 알고리즘에서는 출발좌표에서 시작해서 주변 좌표마다(8방위, 4방위 마음대로) 평가값을 매기고, 가장 작은 평가값을 가진쪽으로 이동하고, 거기에서 또 주변 좌표의 평가값을 매기고... 를 목표 좌표에 닿을때 까지 하는 알고리즘이다. 평가값을 구하는 평가함수를 A*에선 다음과 같은 함수를 사용한다.

g(n)은 출발 좌표부터의 현재까지의 거리(비용) h(n)은 현재 좌표에서의 목적지 까지의 예상 거리(비용) 을 나타낸다.

대부분 g(n)은 출발 좌표부터 한번 움직일때마다 1씩 올려주고, h(n)은 그냥 두 점 사이의 거리 함수를 때려 넣는다. (이 h함수를 휴리스틱 함수라고 한다) 나도 A* 쓸때마다 그냥 이렇게 구현하곤 했었다. 대부분 잘 돌아갔고. 그리고 지난학기 인공지능 시간에 A* 를 구현하는 과제가 나왔었다. 평소대로 하던대로 휴리스틱 함수를 점 사이 거리 함수로 때우고 명시된 대로 테스트 케이스를 돌려보니 3시간이 넘어도 끝나질 않았다. 테스트 케이스 파일을 열어보니, 주어진 좌표 크기는 가로 1000, 세로 1000. 중간에 장애물들이 오밀조밀 박혀있었다. 

과제 명세중에 휴리스틱을 여러개 사용할 수 있게 하라는 말을 보고, 다른 휴리스틱 함수를 쓰면 그나마 좀 몇 시간 걸리던게 몇 분 이내로 줄어들겠거니 생각했다. 볼프람 알파와 더불어 대학생활을 도와주는 일등 공신인 위키 백과에서 A* 알고리즘 항목을 쳐다보니 'Weighted A*'라고 있더라. 그냥 원래 휴리스틱 함수에 (적당한)가중치를 곱해서 지향성을 높이는 방법이었다. 

// 단순 직선거리 휴리스틱
class EuclidStrategy implements AStarHeuristicStrategy{

	public int Heuristic(int posX, int posY, int endX, int endY) {
		return (int) Math.sqrt(Math.pow(posX - endX, 2) + Math.pow(posY - endY, 2));
	}
	
}

// 단순히 가중치를 곱한 휴리스틱
class WeightedEuclidStrategy implements AStarHeuristicStrategy{
	
	private float weight = 1;
	
	public WeightedEuclidStrategy(){}
	
	public WeightedEuclidStrategy(float weight){
		this.weight = weight;
	}

	public int Heuristic(int posX, int posY, int endX, int endY) {
		float dx = Math.abs(posX - endX);
		float dy = Math.abs(posY - endY);
		
		return (int) (weight *(Math.sqrt(Math.pow(posX - endX, 2) + Math.pow(posY - endY, 2))));
	}
	
}

가중치 있는 휴리스틱을 사용하니까 대충 3초 걸렸다. 세시간 걸려서도 안 풀린게 3초 걸려서 끝났다.

좀 더 작은 테스트 케이스(20*20) 맵에서 테스트 한 결과, 그냥 직선거리 휴리스틱으로는 왠만한 좌표들은 전부 다 검사 해보는데 비해 가중치를 곱한 휴리스틱으로는 100개 좀 넘는 좌표만 검사하고 끝냈다. 1000 * 1000 맵으로 커지면서 이 격차가 벌어진것 같다. 

그냥 '느리면 공간 분할하는 쿼드트리랑 엮어서 탐색해 버리지' 라고 생각했고, 그냥 A*면 무조건 직선거리로 때려넣었는데, 이게 항상 최적은 아니었다. (게다가 쿼드트리가 이미 있으면 몰라, 없으면 그냥 가중치 곱하는거에 비해 얼마나 더 삽질을...)

왠만한 테스트 케이스는 다 통과 했고, 잘 했다고 생각한 과제였지만 점수는 많이 못 받은 과제였다.