A* 알고리즘에서 어떤 휴리스틱 함수를 사용해야할까

내가 만든 길찾기에서는 그냥 피타고라스 정리로 휴리스틱을 사용했는데 검색해보니 다양한 방법들이 있다는 것을 알게 되었다.

 

A* 의 성능에는 휴리스틱이 많은 영향을 끼치므로 좋은 휴리스틱을 사용해야한다.

휴리스틱 정확도가 낮을 수록 최단거리를 얻을 수 있지만 A*의 전체 속도가 느려지고,

휴리스틱 정확도가 높을 수록 A*의 전체 속도가  빨라지지만 최단거리를 포기해야한다. (출처)

따라서 속도와 정확도의 균형이 중요하다.

---

두 점 좌표 a(x1, y1, z1), b(x2, y2, z2)이고

a와 b의 휴리스틱 거리값이 distance라고 친다.

1. 맨하탄 방식

    distance= fabs(x2 - x1) + fabs(y2 - y1)

 

    목표까지 도달하는 가로와 세로의 길이만을 고려한다. 장애물은 고려하지 않는다.

 

2. 피타고라스 정리

    distance = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1)* (y2 - y1))

 

    이차원 공간에서 두 점 사이의 대각선 거리를 나타낸다.

 

3. 유클리디안 거리 공식

    피타고라스 정리의 다차원 버전이다.

    맨하탄 방식보다 더 정확하지만, 더 넓은 영역을 탐색하기 위해 속도가 비교적 느리다.

 

   distance = 1 / (1 + sqrt(pow((x2 - x1), 2.0f) + pow((y2 - y1), 2.0f) + pow(y1 - y2, 2.0f)));

 

    루트를 씌워서 나온 값에 1을 더하고 역수를 취하면 0~1 사이의 값이 나온다.

    거리가 가까울 수록 1이 되고 멀 수록 0이 된다.

 

---

+ 가중치 A* (Weighted A*)

휴리스틱 함수에 가중치(ε)를 곱하는 방식이다. 한 블로그에서 알게 된 방식이다.

 

일반 A* 공식 : F = G + H

가중치 A* 공식 : F = G + εH

 

가중치를 어떻게 산정하는지 찾아봤는데 딱히 정해진 공식은 없는 것 같다. 

 

이 그림(출처)을 보면 가중치가 1에 가까울수록 최단 거리를 구할 수 있지만 더 많은 노드를 탐색하므로 시간이 더 걸릴 것이라고 추측할 수 있다. 따라서 빠르게 찾는 것이 더 중요한 경우 가중치를 높이고 느리더라도 최단거리를 찾는 것이 더 중요한 경우 가중치를 낮추면 된다.

---

휴리스틱 함수 중 어떤 방식을 써야할까?

이 글에 따르면 이동방향이 4방향이나 6방향인 경우 맨하탄 방식, 8방향인 경우 피타고라스 방식, 모든 방향이 가능한 경우 유클리디안 방식이 좋다고 한다.