A * 알고리즘

1. 다익스크라 알고리즘의 확장, A* 알고리즘의 개념

- 시작점에서부터 현재 정점까지의 최단거리와 현재 정점에서 목표점까지의 추정잔여 거리를 활용해 최단거리 구하는 알고리즘

 

2. A * 알고리즘 개념도 및 계산 원리

가. A * 알고리즘 개념도

 

나. A* 알고리즘 계산 방식

비용 함수	g(n)	시작 노드에서 현재 노드 n까지 거리
	h(n)	현재 노드 n에서 목표 노드까지 예상거리
	f(n)	g(n) + f(n), 총 예상 비용
계산 방식	1	시작 노드를 리스트에 넣고 탐색 시작
	2	리스트에서 f(n)이 가장 작은 노드 꺼냄
	3	현재 노드가 목표 노드면 경로 반환
	4	이웃 노드의 g(n), h(n), f(n) 계산
	5	더 나은 경로의 f(n) 리스트에 추가
	6	리스트에 더 이상 더 나은 f(n) 없을 때까지 반복

 

 

3. A*, Dijkstra, BFS 비교

항목	BFS	Dijkstra	A*
탐색 기준	거리 순 탐색	누적 거리 탐색	누적 거리, 추정 거리 탐색
속도	느림	중간	빠름
대표 사례	트리 탐색	네트워크 경로 계산	AI 로봇, 네비게이션
메모리 효율	좋은	중간	낮음
조건	간선 가중치 동일	가중치 >= 0	가중치 + 휴리스틱