A* 알고리즘

A* 알고리즘(A* algorithm)은 그래프 탐색과 경로 탐색에 사용되는 휴리스틱 기반 최적화 알고리즘이다.

개요

A* 알고리즘은 1968년 피터 하트(Peter Hart), 넬슨 나일스(Nils Nilsson), 버트 라파엘(Bertram Raphael)이 개발하였다. 최단 경로 문제를 해결하기 위해 사용되며, 다익스트라 알고리즘과 유사하지만, 휴리스틱 함수를 추가적으로 활용하여 더 빠르게 목표 지점에 도달할 수 있도록 설계되었다.

작동 원리

A* 알고리즘은 다음 함수를 최소화하는 경로를 탐색한다.

• f(n) = g(n) + h(n)
  • g(n): 시작 노드로부터 현재 노드 n까지의 실제 경로 비용
  • h(n): 현재 노드 n에서 목표 노드까지의 추정 경로 비용(휴리스틱)

우선순위 큐를 사용하여 f(n)가 가장 낮은 노드를 우선적으로 확장하며, h(n)이 실제 비용을 과소평가하지 않는다면 최적의 경로를 보장할 수 있다.

과정

A* 알고리즘의 탐색 과정은 다음과 같다.

1. 시작 노드를 열린 리스트(open list)에 추가한다.
2. 열린 리스트에서 f 값이 가장 낮은 노드를 선택하여 현재 노드로 설정한다.
3. 현재 노드가 목표 노드라면 경로를 반환하고 탐색을 종료한다.
4. 현재 노드를 열린 리스트에서 제거하고, 닫힌 리스트(closed list)에 추가한다.
5. 현재 노드의 이웃 노드를 모두 검사한다.
   1. 이웃이 닫힌 리스트에 있다면 무시한다.
   2. 이웃이 열린 리스트에 없다면, g, h, f 값을 계산하고 부모를 현재 노드로 설정하여 열린 리스트에 추가한다.
   3. 이웃이 열린 리스트에 이미 있다면, 더 낮은 g 값을 통해 접근할 수 있는지 확인하고, 그렇다면 부모를 갱신하고 g, f 값을 업데이트한다.
6. 열린 리스트가 빌 때까지 반복한다. 경로를 찾지 못하면 실패로 종료한다.

휴리스틱 함수

A* 알고리즘에서 휴리스틱 함수 h(n)의 품질은 알고리즘의 성능에 큰 영향을 미친다. 일반적으로 다음과 같은 휴리스틱이 사용된다.

• 맨해튼 거리(Manhattan Distance): 격자 기반 지도에서 직선 이동만 가능한 경우
• 유클리드 거리(Euclidean Distance): 2차원 평면 상에서 대각선 이동이 가능한 경우
• 체비쇼프 거리(Chebyshev Distance): 대각선 이동이 비용이 동일한 경우

특징

• 최적성: 휴리스틱이 과소평가(Admissible)된다면 최적 경로를 찾을 수 있다.
• 완전성: 유한한 그래프에서는 항상 해를 찾거나 해가 없음을 판단할 수 있다.
• 성능: 휴리스틱의 정확성에 따라 탐색 속도가 크게 달라진다.
• 다익스트라 알고리즘은 h(n)=0인 경우 A* 알고리즘의 특수한 형태로 볼 수 있다.

응용

• 로봇 경로 계획
• 비디오 게임 AI 경로 탐색
• 네비게이션 시스템
• 퍼즐 문제 해결(예: 8퍼즐, 15퍼즐)

같이 보기

• 다익스트라 알고리즘
• BFS
• DFS
• 휴리스틱 함수
• 경로 탐색 알고리즘

참고 문헌

• Peter E. Hart, Nils J. Nilsson, and Bertram Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths," IEEE Transactions on Systems Science and Cybernetics, 1968.