A* 알고리즘
A* 알고리즘은 휴리스틱 정보를 쓰는 그래프 탐색 알고리즘이다. 평가 함수 f(n)은 실제 누적 비용 g(n)과 추정 잔여 비용 h(n)을 더한 값이다. f 값이 작은 노드부터 확장하므로 유망해 보이는 길을 먼저 살핀다. A*는 다섯 가지 요소로 이루어진다. g(n)…
주요 장면
대본
정의와 핵심 식
A* 알고리즘은 휴리스틱 정보를 쓰는 그래프 탐색 알고리즘이다.
평가 함수 f(n)은 실제 누적 비용 g(n)과 추정 잔여 비용 h(n)을 더한 값이다.
f 값이 작은 노드부터 확장하므로 유망해 보이는 길을 먼저 살핀다.
구성 요소
A*는 다섯 가지 요소로 이루어진다.
g(n)은 지금까지 든 실제 비용이고, h(n)은 목표까지 남은 비용의 추정값이다.
OPEN 목록에서 f가 가장 작은 노드를 꺼내고, CLOSED 목록으로 중복 방문을 막는다.
h(n)은 실제 최소 비용을 넘지 않아야 A*가 최적해를 보장한다.
탐색 절차
A*의 탐색은 출발 노드를 OPEN 목록에 넣고, g=0, f=h로 두며 시작한다.
OPEN에서 f가 가장 작은 노드를 꺼내고, 목표이면 경로를 역추적하여 끝낸다.
목표가 아니면 노드를 CLOSED에 넣고, 인접 노드의 새 g를 계산한다.
더 나은 경로면 g, f, 부모를 갱신하여 OPEN에 넣고 같은 과정을 반복한다.
허용 가능성과 최적성
A* 최적성의 핵심 조건은 허용 가능 휴리스틱이다.
h(n)이 실제 최소 비용 h*(n)을 넘지 않으면 A*는 최적 경로를 보장한다.
h(n)을 과대평가하면 해를 빨리 찾더라도 최적성은 보장되지 않는다.
모든 일관된 휴리스틱은 허용 가능하지만, 그 역은 성립하지 않는다.
다른 알고리즘과 비교
세 알고리즘은 평가 함수 f(n)의 구성에서 차이가 난다.
다익스트라는 g(n)만 보아 범위가 넓고, 탐욕적 최선 우선 탐색은 최단 경로를 보장하지 않는다.
A*는 두 값을 합쳐 최적성과 탐색 효율의 균형을 맞춘다.
IDA*는 임계치 기반 깊이 우선 탐색이라 메모리가 적다.
정리와 확인
앞서 던진 문제의 답은 f(n)=2+3=5다.
A*의 한계는 탐색한 노드를 모두 저장하는 메모리 사용량이다.
휴리스틱의 품질에 따라 탐색 성능이 크게 달라진다.
시험에서는 1교시 용어와 4교시 8-퍼즐 응용으로 자주 출제된다.