A star search algorithm

전산학 분야에 있어서, A 알고리즘(A algorithm 에이 스타 알고리듬)은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 그래프/나무 탐색 알고리즘 중 하나이다.

다익스트라 알고리즘을 확장하여 만들어진 경로 탐색 알고리즘이다. 에이스타 알고리즘 이라고 읽는다.

원리

가장 기본이 되는 식은 다음과 같다.

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

동작은 다음과 같이 된다.

1. f(x)를 오름차순 우선순위 큐에 노드로 삽입한다.
2. 우선순위 큐를 pop한다.
3. 해당 노드에서 이동할 수 있는 노드를 찾는다.
4. 그 노드들의 f(x)를 구한다.
5. 그 노드들을 우선순위 큐에 삽입한다.
6. 목표 노드에 도달할 때까지 반복한다.

의사코드는 다음과 같다.

PQ.push(start_node, g(start_node) + h(start_node))       //우선순위 큐에 시작 노드를 삽입한다.

while PQ is not empty       //우선순위 큐가 비어있지 않은 동안
    node = PQ.pop       //우선순위 큐를 pop한다.

    if node == goal_node       //만일 해당 노드가 목표 노드이면 반복문을 빠져나온다.
        break

    for next_node in (next_node_begin...next_node_end)       //해당 노드에서 이동할 수 있는 다음 노드들을 보는 동안
        PQ.push(next_node, g(node) + cost + h(next_node))       //우선순위 큐에 다음 노드를 삽입한다.

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

See also

• Algorithm
• Dijkstra's algorithm
• Q* (OpenAI)

Favorite site

• Wikipedia (en) A* 알고리즘에 대한 설명
• 초보자를 위한 A* 알고리즘 (기초개념 설명 및 소스) ¹
• A*(A star) 알고리즘 정의 및 개념
• [추천] 최단 경로 탐색 – A* 알고리즘 – GIS Developer

References

---

1. Astar-algorithm_basic.pdf ↩