너무 느린 A* 알고리즘
기존 서비스에서는 A* 알고리즘을 탐색 알고리즘으로 사용하고 있었습니다.
다익스트라 알고리즘은 확장 가능한 정점을 우선순위 큐에 넣고, 그중 가장 작은 비용의 정점을 꺼내서 검토하는 것을 반복하며, 목적지에 도달하면 종료합니다. 새로운 정점을 검토할 때마다 큐 삭제가, 확장할 때마다 큐 삽입이 발생합니다. 일반적인 경우 삽입/삭제는 보통 O(log n) 의 복잡도를 가지며, 큐의 크기 n 은 탐색 범위에 비례하기 때문에 A* 에서는 휴리스틱한 방법을 추가해 최대한 탐색 범위를 줄입니다.
가장 대표적인 휴릭스틱은 정점에서 도착지까지의 직선거리입니다. 목적지 방향으로 가는 게 최단 경로일 확률이 높기 때문에 이런 곳을 우선적으로 가보면 탐색 범위를 꽤나 많이 줄일 수 있습니다. PathFinding.js에서 두 알고리즘을 시각화해보면 꽤 유의미한 성능 향상이 있다는 것을 알 수 있습니다.
카카오의 지도서비스 이야기
댓글 0