A* (A star) 알고리즘

 

 

Compare the algorithms

 

 

A* 알고리즘이란 ? 

주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다. 다익스트라 알고리즘과 유사하나, 차이점은 각 꼭짓점 x에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위값인 휴리스틱(heuristics) h(x) 을 이용한다는 것이다. 각각의 꼭짓점에 대한 평가 함수는 다음과 같이 정의된다.

$$ f(x) = g(x) + h(x) $$

• g(n) : 출발 꼭짓점으로부터 꼭짓점 n까지의 경로 가중치 (시작 ~ n 노드 까지 부하량)
• h(n) : 꼭짓점 n으로부터 목표 꼭짓점까지의 추정 경로 가중치 (n ~ 목표 노드 까지 추정 부하량)

 

 

 

 

Heuristics

1. Heuristics for grid maps

• square grid 4방향 : Manhattan distance
• square grid 8방향 : Diagonal distance
• square grid 모든 방향 : Euclidean distance
• hexagon grid 6방향 : Manhattan distance adapted to hexagonal grids

 

2. Euclidean distance, squared

$$ \textrm{Euclidean distance}=\sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2} $$

유클리드 거리는 제곱근(square root)을 포함한다. 그에 따라 많은 A* 알고리즘 관련 페이지에서 유클리드 거리를 사용할 때, 자원이 많이 드는 제곱근(=실수) 대신 거리를 제곱하여(=정수) 사용한다.

 

하지만, 그러지 말자. A* 알고리즘의 평가 함수는 f=g+h 이기 때문에 g와 h의 scale은 동일해야한다. h를 제곱수로 사용하면 먼 거리에서 g의 기여가 낮아지고, A*는 Greedy Best-First-Search가 된다. 해당 문제를 해결하기 위해 h의 scale을 축소할 수도 있지만, 그러면 짧은 거리에서 h의 기여가 낮아지고 A*는 Dijkstra가 된다.

 

프로파일링 후 제곱근의 영향이 크게 나타난다면, 유클리드 거리를 fast square root approximation 하여 사용하거나, 유클리드 거리의 근사치로서 diagonal distance를 사용한다.

3. Speed or Accuracy ? 

you don’t really need the best path between two points.

• Speed or accuracy?
• Don’t follow the shortest path!

 

 

 

 

Weighted A* 이란?

A*를 더 빠르게 하기위해 휴리스틱에 어떠한 상수 요소를 곱하는 것을 Weighted A* 라고 한다.

$$ f(x) = g(x) + w * h(x) $$

w는 1보다 크게 설정하며, 동적 \( w(x) \)으로 사용할 수도 있다. 목표 지점에 가까워질수록 가중치가 작아지는 pxWU, 목표 지점에 커질수록 가중치가 커지는 pxWD 등이 있다. 

• 다양한 Weighted A* 을 테스트 해볼 수 있는 interactive demo

 

 

 

 

의사코드

state list : Open list (조사하지 않은 상태) & Close list (조사를 마친 상태)

# 우선순위 큐에 시작 노드를 삽입한다.
pq.enqueue(start_node, g(start_node) + h(start_node))

# 우선순위 큐가 비어있지 않은 동안
while pq is not empty:
    # 우선순위 큐에서 pop한다
    node = pq.dequeue
    
    # 만약 해당 노드가 목표 노드면 반복문 탈출
    if node == goal_node:
        break
        
    # 해당 노드에서 이동할 수 있는 다음 노드들을 보는 동안
    # 우선순위 큐에 다음 노드를 삽입한다
    for next_node in (next_node_begin ... next_node_end):
        pq.enqueue(next_node, g(node) + cost + h(next_node))

# 시작 노드에서 목표 노드까지의 거리를 출력한다.
return goal_node_dist

 

 

 

 

Reference

• Introduction to the A* Algorithm A* 를 비롯한 알고리즘 interactive demo/코드 포함글
• Amit’s A* Pages
• 위키백과 A* 알고리즘

 

이해를 위해 읽어보면 좋은 글

• (유튜브) 아무거나 물어보살: A* (에이스타) 알고리즘이 궁금해요. 궁금하면 못참지!
• (유튜브) [길찾기 알고리즘] A*냐 JPS냐 ... 그것이 문제로다!ㅣ지피직스 알고리즘.zip EP.1
• 파이썬 A* 최단경로 찾기 알고리즘
• A* (a-star) 알고리즘 휴리스틱 (Weighted A*)