[Algorithm] A* 길 찾기

A* 길찾기

A*는 출발 노드에서 현재 노드 N까지의 거리를 G, 현재 노드 N에서 목적 노드까지의 거리를 H라고 할 때 이 둘을 더한 F = G + H가 최소가 되는 노드를 우선 탐색하여 경로를 찾는 방법이다.

특징

• 다익스트라 길 찾기와 비슷하지만, 목적지가 정해져 있다는 것과, 휴리스틱 함수(추정 값)를 사용한다는 차이가 있다.
• 휴리스틱 값으로 맨허튼 거리(Manhattan Distance)를 많이 쓴다. 맨허튼 거리는 2차원 평면 공간에서 두 점 p 와 q 사이의 거리를 측정하는 방법 중 하나로, 두 점 사이의 수평 및 수직 이동 거리의 합으로 정의된다. 맨허튼 거리 = ∣p1−q1∣+∣p2−q2∣ 이다.
• 휴리스틱 함수가 적절하다면, 효율적인 알고리즘이다.
• 휴리스틱 함수가 적절하지 않으면 비효율적으로 되거나, 심하면 최단 경로를 찾지 못할 수도 있다. 실제로는 짧은데 되게 먼 거리로 착각하면 그 방향으로 가지 않을 수 있기 때문이다.

알고리즘 설명

F가 최소인 노드를 쉽게 구하기 위해 우선순위 큐를 사용한다. (다른 것두 됨!)

각 노드는 “G, H, F, 바로 이전에 들린 노드”를 갖는다.

• G : 출발 노드에서 현재 노드 N까지의 거리
• H는 휴리스틱 함수로 구한 현재 노드 N에서 목적 노드까지의 거리
• F = G + H
• 바로 이전에 들린 노드는 최단 길을 기록하기 위한 발자취이다. (되추적)

O는 열린 목록(Open List), C는 닫힌 목록(Close List)

• Open List(열린 목록): 탐색 대기 노드들
• Close List(닫힌 목록): 탐색을 마친 노드들

(1). 출발 노드를 열린 목록(우선순위 큐)에 넣는다. (2). 열린 목록에서 F가 가장 짧은 노드 N을 꺼낸다. (3). N을 닫힌 목록에 넣고 N과 인접한 노드들을 F를 계산하고 열린 목록에 넣는다. (4). 만약 이미 열린 목록에 있다면, 둘 중 더 짧은 F로 갱신해 준다. (5). 목적지에 도착할 때까지 2~4를 반복한다.