A* 알고리즘

왜 배우는가: A* 알고리즘은 경로 탐색과 퍼즐 문제에서 최적해를 효율적으로 찾는 대표적 휴리스틱 탐색 기법이다. 인공지능 기초 과목의 핵심 주제로, 1교시 용어 문제와 4교시 응용(8-퍼즐) 문제에 반복해서 출제된다. 평가 함수 f(n)=g(n)+h(n)과 허용 가능성(admissibility) 조건을 이해해야 답안을 정확히 쓸 수 있다.

출제 이력: 제90회 4교시 3번, 제87회 1교시 2번

1. 한 줄 정의와 핵심 키워드

A* 알고리즘은 평가 함수 f(n)=g(n)+h(n)의 값이 작은 노드부터 방문하여 출발 노드에서 목표 노드까지의 최적 경로를 찾는 휴리스틱 그래프 탐색 알고리즘이다.

• 휴리스틱 함수(heuristic function)
• 평가 함수 f(n)
• 실제 경로 비용 g(n)
• 추정 잔여 비용 h(n)
• 허용 가능 휴리스틱(admissible heuristic)
• 최선 우선 탐색(best first search)
• OPEN 리스트와 CLOSED 리스트

2. 개념 풀이

쉬운 말로 하면 A* 알고리즘은 "지금까지 온 거리와 앞으로 남은 거리를 더해 가장 유망해 보이는 길부터 가 보는 방법"이다. 갈림길마다 목적지까지 대략 몇 칸 남았는지 짐작하고, 그 짐작을 이용해 다음에 확인할 곳을 고른다.

정식 정의는 다음과 같다. 출발 노드 s에서 노드 n까지의 실제 경로 가중치를 g(n), 노드 n에서 목표 노드까지의 추정 경로 가중치를 h(n)이라 하면, 노드 n을 통과하는 최적 경로의 추정치는 다음 식으로 주어진다.

$f(n)=g(n)+h(n)$

여기서 f(n)은 평가 함수, g(n)은 실제 누적 비용(단위는 경로 가중치), h(n)은 휴리스틱 추정값이다. 알고리즘은 OPEN 리스트에서 f(n)이 가장 작은 노드를 꺼내 확장한다. 이 점에서 A* 알고리즘은 최선 우선 탐색(best first search)의 한 예이며, 너비 우선 탐색과 비슷한 방식으로 분류된다.

h(n)이 실제 최소 비용을 넘지 않으면 허용 가능 휴리스틱(admissible heuristic)이라 한다. 즉 모든 노드 n에 대해 h(n)≤h*(n)을 만족해야 한다. 여기서 h*(n)은 n에서 목표까지의 실제 최소 비용이다. 이 조건을 만족하면 A* 알고리즘은 최적해를 보장한다. 조건이 깨지면 빠르게 해를 찾을 수는 있어도 최적성은 보장되지 않는다.

3. 등장 배경과 필요성

그래프 탐색의 기본 방법인 다익스트라(Dijkstra) 알고리즘은 목표 방향에 대한 정보가 없어서 출발 노드 주변을 넓게 탐색한다. 노드 수가 많아지면 탐색 비용이 급증한다. 이 한계를 줄이기 위해 목표까지의 거리를 짐작하는 휴리스틱 정보를 함께 쓰는 방법이 필요해졌다.

A* 알고리즘은 1968년 피터 하트(Peter Hart), 닐스 닐슨(Nils Nilsson), 버트램 라팰(Bertram Raphael)이 처음 기술하였다. 당시 이름은 A 알고리즘이었고, 적절한 휴리스틱을 쓰면 최적이 된다는 점이 드러나 A* 알고리즘이라 불리게 되었다. 이후 경로 탐색, 로봇 경로 계획, 게임 AI, 퍼즐 문제 해법 등 상태공간 탐색 전반에 널리 쓰인다.

이 알고리즘이 필요한 이유는 두 가지다. 첫째, 목표 방향 정보를 활용해 탐색 노드 수를 줄인다. 둘째, 허용 가능 휴리스틱을 쓰면 최적해를 보장하면서도 완전 탐색보다 효율적이다. 따라서 문제 크기가 커도 실용적인 최적 해를 얻을 수 있다.

{"type":"flow","title":"A* 탐색 기본 흐름","tip":"4~5줄, f=g+h와 OPEN 선택을 반드시 쓴다","nodes":[{"id":"a","label":"시작 노드 등록","sub":"OPEN에 출발 노드"},{"id":"b","label":"f(n) 최소 노드 선택","sub":"f=g+h"},{"id":"c","label":"목표 여부 판정","sub":"목표면 경로 반환"},{"id":"d","label":"이웃 노드 확장","sub":"g, h, f 계산"}],"edges":[{"from":"a","to":"b","label":""},{"from":"b","to":"c","label":""},{"from":"c","to":"d","label":"아니오"},{"from":"d","to":"b","label":"OPEN 갱신","arrow":true}]}

4. 구성요소·원리·절차

A* 알고리즘은 출발 꼭짓점에서 목표 꼭짓점까지 최단 경로를 찾는 그래프 탐색 알고리즘이다. 각 꼭짓점 n에 대해 평가 함수를 정의하고, 그 값이 작은 꼭짓점부터 방문한다.

평가 함수는 다음과 같다.

$f(n)=g(n)+h(n)$

• g(n): 출발 꼭짓점에서 꼭짓점 n까지의 실제 경로 가중치(누적 비용)
• h(n): 꼭짓점 n에서 목표 꼭짓점까지의 추정 경로 가중치(휴리스틱 추정값)
• f(n): 꼭짓점 n을 거쳐 목표에 이르는 총 비용의 추정값

구성요소 표

원리. 휴리스틱 h(n)이 실제 최소 비용 h^(n)을 넘지 않으면 A는 최적 해를 찾는다. 이 조건을 허용 가능성(admissibility)이라 한다. 허용 가능한 휴리스틱은 목표 비용을 과대평가하지 않으며 하한(lower bound) 역할을 한다. 일관성(consistency)을 만족하면 확장된 노드를 다시 열 필요가 없어진다.

h(n)이 실제 비용을 넘지 않을 때 A*는 최적 경로를 보장한다

절차

• 출발 노드를 OPEN에 넣고 g=0, f=h로 둔다.
• OPEN에서 f(n)이 가장 작은 노드 n을 꺼낸다.
• n이 목표이면 경로를 역추적하여 종료한다.
• n을 CLOSED에 넣고 인접 노드 m을 확인한다.
• 새 g(m)을 계산해 더 나은 경로이면 g, f, 부모를 갱신하고 OPEN에 넣는다.
• OPEN이 빌 때까지 2~5를 반복한다.

도식

5. 관련 법령·기준·표준

A*는 법령이나 국가 표준으로 규정된 알고리즘이 아니다. 따라서 조문 번호에 해당하는 기준은 없다. 다만 알고리즘 판단의 기준이 되는 개념 규정과 수치가 있다.

기준 표

해설. 허용 가능성과 일관성이 A*의 최적성 조건이다. 맨해튼 거리는 타일을 서로 독립으로 움직일 수 있다고 완화한 문제의 해이므로 허용 가능한 휴리스틱이다. 상태 수 362,880개는 두 그래프로 나뉘므로 실제 도달 가능한 상태는 그 절반이다.

개정 연혁. 알고리즘 명칭은 1968년 하트(Hart), 닐슨(Nilsson), 라팰(Raphael)의 논문에서 A 알고리즘으로 처음 기술되었다. 적절한 휴리스틱을 쓰면 최적이 되어 A*로 불린다. 국내 법령 개정 사항은 없다.

6. 유형과 비교

A* 알고리즘은 탐색 전략에 따라 여러 알고리즘과 구분된다. 가장 가까운 비교 대상은 다익스트라 알고리즘과 탐욕적 최선 우선 탐색이며, 두 알고리즘과의 차이는 평가 함수 f(n)의 구성으로 설명한다. A* 알고리즘은 다익스트라와 유사하지만 휴리스틱 추정값을 쓴다는 점이 다르다.