A* 알고리즘
A* 알고리즘은 시작점부터 목표까지의 실제 이동 비용과 남은 예상 비용을 합쳐 탐색 순서를 정한다 그래프 알고리즘의 휴리스틱 최단 경로 탐색 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘...
| 분류 | 알고리즘 · 그래프 알고리즘 · 휴리스틱 최단 경로 탐색 |
|---|---|
| 문제 | 시작점부터 목표까지의 실제 이동 비용과 남은 예상 비용을 합쳐 탐색 순서를 정한다 |
| 입력 | 최적성에는 휴리스틱의 허용성 및 탐색 구현에 맞는 일관성·재방문 처리 조건이 중요하다 |
| 핵심 단계 | 열린 집합에서 f=g+h가 가장 작은 정점을 선택하고 이웃을 완화한다 |
| 시간 복잡도 | 휴리스틱 의존 |
| 공간·구현 | 시간·메모리는 휴리스틱과 그래프에 따라 다르며 최악에는 지수적 탐색 가능 |
| 관련 분야 | 그래프, 자료구조 |
| 참고 문헌 | MIT Algorithms |
**A* 알고리즘**은 시작점부터 목표까지의 실제 이동 비용과 남은 예상 비용을 합쳐 탐색 순서를 정한다 그래프 알고리즘의 휴리스틱 최단 경로 탐색 분야에 속한다. 그래프의 정점·간선에 대한 관계를 계산하며, 간선의 방향·가중치와 허용하는 입력 구조에 따라 결과의 의미가 달라진다. 이 알고리즘의 전제는 최적성에는 휴리스틱의 허용성 및 탐색 구현에 맞는 일관성·재방문 처리 조건이 중요하다.[1]
핵심 절차는 열린 집합에서 f=g+h가 가장 작은 정점을 선택하고 이웃을 완화한다. h가 실제 남은 최단 비용을 초과하지 않는 허용적 휴리스틱이면 적절한 조건에서 최적 경로를 구할 수 있다. 구현에서는 각 정점 또는 간선에 기록된 상태가 어떤 의미를 갖는지 불변식을 정의하고, 탐색·갱신 과정에서 해당 상태를 일관되게 유지해야 한다.
계산 비용은 시간·메모리는 휴리스틱과 그래프에 따라 다르며 최악에는 지수적 탐색 가능 정점 수를 V, 간선 수를 E라고 나타낼 때 휴리스틱 의존의 시간 특성을 가진다. 저장 공간은 그래프의 표현 방식, 큐·스택·우선순위 큐 및 결과 배열의 선택에 영향을 받으므로 실제 적용 시 구현 구조를 함께 분석한다.
게임 지도·로봇 경로 계획에 널리 쓰인다. h=0이면 사실상 다익스트라식 탐색 순서가 된다. 대표적인 변형 알고리즘 및 자료구조의 선택은 결과의 최적성, 음수 가중치나 사이클의 허용 여부, 희소·밀집 그래프 여부에 따라 달라진다. 동점 처리와 비연결 그래프 등의 경계 사례까지 정의해야 구현 결과가 명확해진다.[2]