A* 알고리즘 시뮬레이터 및 상세 보고서

자율주행자동차 수행평가 가이드라인

항목	상세 내용
대상 및 기간	3학년 친환경자동차과 A/B반 (2026년 5월 중)
과제 주제	A* 알고리즘의 5대 구성요소 분석 및 보고서 작성
배점 기준	모든 요소 설명 시 40점 (누락 시 요소당 -5점 감점), 기본 점수 15점

Logic 01

우선순위 큐 (Priority Queue)

A* 알고리즘의 '탐색 엔진' 역할을 수행합니다. 일반적인 큐(Queue)가 들어온 순서대로 데이터를 처리(FIFO)하는 것과 달리, 우선순위 큐는 각 데이터에 부여된 우선순위값을 기준으로 가장 '유망한' 데이터를 먼저 추출합니다.

A*에서는 f(n) 값이 가장 작은 노드가 최우선순위를 가집니다. 이를 효율적으로 구현하기 위해 주로 '최소 힙(Min-Heap)' 자료구조를 사용하며, 이는 수천 개의 후보 노드 중 최적의 노드를 찾는 시간 복잡도를 O(log n)으로 단축시켜 실시간 자율주행 연산을 가능하게 합니다.

Logic 02

평가 함수 (Evaluation Function)

알고리즘이 어떤 방향으로 나아갈지 결정하는 수학적 기준입니다. A*는 단순한 최단 거리만을 고려하는 것이 아니라, 실제 주행 거리와 예상 거리의 합을 통해 최적의 판단을 내립니다.

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

g(n): 시작 노드에서 현재 노드까지 오는데 실제로 소요된 누적 비용입니다. 도로의 상태나 경사도 등을 가중치로 포함할 수 있습니다.
h(n): 현재 노드에서 목표 노드까지 남은 것으로 예상되는 추정 비용(휴리스틱)입니다.
f(n): 이 두 값의 합으로, 알고리즘은 f(n)이 가장 낮은 경로를 선택함으로써 Dijkstra 알고리즘의 정확성과 Greedy Search의 효율성을 동시에 확보합니다.

Logic 03

휴리스틱 함수 (Heuristic Function)

휴리스틱은 '완벽한 정답'은 아니지만 '경험적으로 보아 정답에 가까운 값'을 의미합니다. 아직 가보지 않은 길에 대해 목적지까지의 거리를 미리 짐작하는 나침반 같은 존재입니다.

가장 중요한 원칙은 '허용 가능성(Admissibility)'입니다. 휴리스틱 값(h)이 실제 거리보다 절대 크지 않아야만 알고리즘이 항상 최단 경로를 찾는 것을 보장합니다. 격자형 지도에서는 상하좌우 이동 시 맨해튼 거리를, 대각선 이동이 포함된 환경에서는 유클리드 거리를 주로 사용하여 목적지 방향으로 탐색을 유도합니다.

Logic 04

노드 상태 관리 (Node State Management)

수많은 경로를 탐색하는 과정에서 중복 연산을 방지하고 체계적으로 데이터를 관리하기 위해 두 가지 핵심 리스트를 운용합니다.

Open List (열린 목록)

발견되었으나 아직 주변을 탐색하지 않은 후보 지점들입니다. 우선순위 큐에 담겨 처리 대기 중인 상태입니다.

Closed List (닫힌 목록)

이미 주변 탐색을 완료한 지점들입니다. 다시 방문할 필요가 없도록 관리하여 무한 루프를 방지하고 연산량을 줄입니다.

Logic 05

경로 복원 (Path Reconstruction)

목적지에 도달하면 역추적을 통해 최종 경로를 생성합니다. 자율주행차는 이 경로를 부드러운 곡선으로 다듬어 실제 주행에 활용합니다.