A* algorithm 썸네일형 리스트형 A* 알고리즘(A Star Algorithm) 1. 개념 2. 시각화 3. 코드 1. 개념 최단경로를 찾는 그래프 탐색 알고리즘 중 하나입니다. 다익스트라 알고리즘과 유사하나 차이점은 각 꼭지점 x에 대해 그 꼭지점을 통과하는 최상의 경로를 추정하는 순위값인 "휴리스틱 추정값" h(x)를 매기는 방법을 이용한다는 점에서 차이가 있습니다. (h(x) 값을 정확하게 구할 수 없어도 괜찮습니다) 시작노드와 목적지 노드를 분명하게 정해 놓고, 이 두 노드간의 최단 경로를 파악합니다. 휴리스틱 추정값을 어떤 방식으로 제공하느냐에 따라 최단경로 파악 성능이 결정됩니다. A* 알고리즘은 출발 꼭지점으로 부터 목표 꼭지점까지의 최적 경로를 탐색하기 위한 것입니다. 이를 위해서는 각각의 꼭지점에 대한 평가 함수 f(n)를 정의해야 합니다. $ f(x) = g(x) .. 더보기 이전 1 다음
