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* 알고리즘의 탐색 과정은 다음과 같다.
#시작 노드를 열린 리스트(open list)에 추가한다.
#열린 리스트에서 f 값이 가장 낮은 노드를 선택하여 현재 노드로 설정한다.
#현재 노드가 목표 노드라면 경로를 반환하고 탐색을 종료한다.
#현재 노드를 열린 리스트에서 제거하고, 닫힌 리스트(closed list)에 추가한다.
#현재 노드의 이웃 노드를 모두 검사한다.
##이웃이 닫힌 리스트에 있다면 무시한다.
##이웃이 열린 리스트에 없다면, g, h, f 값을 계산하고 부모를 현재 노드로 설정하여 열린 리스트에 추가한다.
##이웃이 열린 리스트에 이미 있다면, 더 낮은 g 값을 통해 접근할 수 있는지 확인하고, 그렇다면 부모를 갱신하고 g, f 값을 업데이트한다.
#열린 리스트가 빌 때까지 반복한다. 경로를 찾지 못하면 실패로 종료한다.
==휴리스틱 함수==
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.
==각주==
[[분류:그래프 이론]]
[[분류:알고리즘]]