감자보이로그

A* 알고리즘은 주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나이다. A* 알고리즘은 휴리스틱 추정값을 통해서 알고리즘을 개선할 수 있다. A* 알고리즘은 출발 꼭짓점으로부터 목표 꼭짓점까지의 최적 경로를 탐색하기 위한 것이다. 이를 위해서는 각각의 꼭짓점에 대한 평가 함수를 정의해야 한다. 이를 위한 평가 함수 $f(n)$은 다음과 같다. $f(n) = g(n) + h(n)$ $g(n)$ : 출발 꼭지점으로부터 꼭지점 n까지의 경로 가중치를 의미한다. $h(n)$ : 꼭지점 n 으로부터 목표 꼭지점까지의 추정 경로 가중치를 의미한다. → 보통 path planning에서는 h를 추정할 때 euclidean distance를 사용한다. 해당 알고리즘을 ..