A* 알고리즘 #A star algorithm #에이스타 알고리즘
-
A star 알고리즘 (python) 설명알고리즘 2022. 5. 6. 15:20
A star 알고리즘은 시작 노드부터 목표 노드까지 최단거리를 효율적으로 탐색 할 수 있는 알고리즘이다. A Star 알고리즘의 작동은 아래 그림과 같다. 시작점 (0,0) 에서 도착점 (n-1, m-1) 까지 최단거리를 탐색을 하는데 BFS 와는 다르게 모든 노드를 탐색하지 않고 거리가 가까운 노드를 중심으로 탐색을 한다. 반면 BFS 는 모든 노드를 탐색하면서 최단거리를 알아낸다. A star 알고리즘을 활용해 아래 그림과 같이 출발점이 0 인 노드에서 도착점이 6 인 노드까지의 최단거리를 구해보자. A star 알고리즘을 사용하기 위해서 휴리스틱 추정값을 사용해야 한다. 휴리스틱 추정값이란, 간단히 말해서 현재 위치의 노드에서 도착점 까지의 대강의 거리를 말한다. 위 그림을 보면 O 와 C 배열이 ..