A*로 바꾸면 다익스트라보다 빨라질까? 경로 탐색 선택법

세 줄 요약

A*는 목적지까지 남은 비용을 추정하지만, 그 추정이 탐색을 충분히 줄여야 빨라진다.
CCH는 연결 구조를 미리 처리하고 비용을 갱신해 반복 경로 조회에서 탐색량을 줄이는 방식이다.
알고리즘 선택에는 조회 횟수, 그래프 구조, 준비 시간과 메모리가 함께 들어간다.

A*라는 이름만으로 검색이 빨라지지는 않는다

다익스트라를 A*로 바꾸면 목적지를 향해 더 똑똑하게 찾으니 무조건 빠를까? ArcadeDB가 10월 13일 공개한 도로망 비교에는 반대 사례가 나온다. 플로리다의 탤러해시에서 코럴게이블스까지 같은 경로를 찾는 데 다익스트라는 99ms, A*는 121ms가 걸렸다.

Apple M5 Pro에서 같은 메모리 내 그래프를 대상으로 세 번 실행한 중앙값이다. 비교 대상은 교차점 약 107만 개, 도로 구간 약 271만 개다. 가까운 목적지에서는 A*가 유리했지만 긴 경로에서는 추정 계산의 부담을 만회하지 못했다.

같은 측정의 CCH는 0.039ms였다. 다만 그 숫자 앞에는 계층 준비 6.6초와 뷰·계층 합계 306MB가 있다. 요청 한 번의 시간과 서비스를 준비하는 비용을 나눠 읽어야 한다.

최단 경로가 필요하면 추정값을 마음대로 키울 수 없다

A*는 현재까지 든 비용에 목적지까지 남았을 것으로 예상되는 비용을 더해 탐색 순서를 정한다. 이 예상값이 휴리스틱이다. NetworkX의 A* 문서도 남은 비용을 과대 추정하면 결과가 최단 경로가 아닐 수 있다고 명시한다.

실무에서는 먼저 최적화할 비용을 정해야 한다. 거리를 최소화할지, 이동 시간을 최소화할지에 따라 간선의 값과 추정식이 달라진다. 직선거리 숫자를 이동 시간에 그대로 더하면 서로 다른 단위를 섞는 셈이다.

추정이 거의 도움을 주지 못하면 넓은 영역을 여전히 탐색하면서 추정 계산까지 수행하게 된다. 반대로 탐색 범위를 줄이겠다고 실제보다 큰 값을 쓰면 정확성 조건을 벗어날 수 있다. 성능 측정에서는 실행 시간과 함께 반환 경로의 총비용도 비교해야 한다.

CCH는 연결 구조와 통행 비용을 따로 준비한다

CCH(Customizable Contraction Hierarchies)는 요청이 올 때 할 일을 미리 줄인다. 정점에 순서를 부여하고 경로를 보존하는 지름길 간선을 만들어, 조회 때 계층의 일부만 따라가도록 한다. Dibbelt·Strasser·Wagner의 논문은 이를 연결 구조를 이용한 전처리, 비용에 맞춘 갱신, 실제 조회의 세 단계로 설명한다.

이 구분 때문에 도로 연결은 같고 정체로 통행 시간만 달라지는 경우에도 준비한 구조를 활용할 수 있다. 논문은 건물과 유닛 종류에 따라 이동 비용이 달라지는 게임 지도도 적용 상황으로 든다. ‘미리 계산한다’는 말이 곧 비용을 영원히 고정한다는 뜻은 아니다.

ArcadeDB에서는 26.10.2부터 CCH를 사용할 수 있다. 공식 사용 문서에 따르면 계층이 아직 준비되지 않았거나 현재 데이터와 맞지 않으면 다익스트라로 계산한다. CCH 함수를 호출했다는 사실만으로 모든 요청이 계층을 사용했다고 볼 수 없다.

조회 횟수와 필요한 답부터 고른다

필요한 결과	먼저 비교할 방법
가중치 없이 가장 적은 단계로 이동한다	너비 우선 탐색 기반 최단 경로다.
비음수 비용의 경로를 가끔 조회한다	다익스트라가 출발점이다.
목적지까지 유용한 하한 추정값이 있다	A*의 탐색 감소와 계산 비용을 비교한다.
같은 도로형 네트워크를 반복 조회한다	CCH의 준비·갱신 비용을 포함해 평가한다.
한 출발점에서 모든 정점까지 거리가 필요하다	단일 출발점 다익스트라를 검토한다.

연결이 일부 정점에 지나치게 몰린 소셜 그래프는 도로망과 다르다. ArcadeDB는 계층이 크게 불어날 그래프를 UNSUITABLE로 표시하고 다익스트라로 처리한다. 상태와 fallbacks를 함께 읽으면 예상보다 느린 요청이 어느 경로로 계산됐는지 좁힐 수 있다.

도입 비교에서는 실제로 자주 묻는 출발지·목적지와 비용 변경 주기를 유지하는 편이 유용하다. 드문 조회를 위해 큰 구조를 만들 필요가 있는지, 반복 조회의 절약이 준비와 갱신 비용을 넘어서는지를 판단해야 한다. A*는 추정의 효과를, CCH는 사전 준비를 얼마나 자주 재사용할 수 있는지를 보고 선택하는 방식이다.