카카오맵과 티맵이 사용하는 알고리즘 - Customizable Contraction Hierarchies

CCH(Customizable Contraction Hierarchies)

 

 

안녕하세요! NewCodes입니다!

 

 

저번 포스팅에서는 최단 경로 알고리즘 중의 하나인 CH 알고리즘(Contraction Hierarcies)에 대해 다뤘습니다. 해당 알고리즘의 가장 큰 특징을 요약해드리자면요. 전처리 단계에서 '지름길'을 추가하여 쿼리에서 비약적인 속도를 향상시킬 수 있다는 것입니다. 

 

 

CH는 기존의 다익스트라, A* 알고리즘보다 비약적인 속도 향상을 가져온 건 사실입니다. 하지만, 실시간으로 빠르게 변하는 교통 상황 정보를 처리하는 데는 무리가 있었습니다. 그 이유는 다음과 같습니다. 

 

특정 도로 구간의 정체, 기상 악화 등으로 인한 각종 이슈가 생기면 다시 전처리 작업을 해야 합니다. 그래프의 모양이 똑같더라도 간선의 비용이 달라지기 때문에 지름길을 생성하는 전처리를 다시 진행해야 합니다.

 

CH는 전처리에서 지름길을 새롭게 생성할 때 해당 지름길의 비용까지 업데이트하기 때문이죠!

 

 

그리고, 이러한 단점을 보완하기 위해서 나온 알고리즘이 바로 CCH(Customizable Contraction Hierarchies)입니다!

 

 

CCH 알고리즘은 CH를 기반으로 새로운 가중치(weight)에 빠르게 대처할 수 있는 최단 경로 알고리즘입니다. 쉽게 말하자면, CH를 조금 더 유연하게 커스텀하는 과정이 추가된 알고리즘이 바로 CCH입니다. 

 

 

---

CH와 CCH의 차이점

CH에서는 '지름길 생성'과 '간선 비용 처리'를 동시에 진행했지만, CCH에서는 이를 두 단계로 나누어서 진행한다는 차이점이 있습니다. 

 

우선 간선 비용을 고려하지 않고 그래프 형태만을 통해 지름길을 생성합니다. 그러고 나서 지름길을 포함한 각 간선마다의 비용을 전처리합니다. CCH에서도 마찬가지로 contract를 하기 전에 각 노드에 랭크를 부여(Node Ordering)하는 과정이 이루어집니다. 

 

해당 포스팅에서는 Node Ordering에 대해서는 마지막에 다루겠습니다. 

 

 

---

Contraction 

전처리 단계이자 지름길을 생성하는 과정인 contraction 과정을 살펴보겠습니다. 해당 단계는 Metric-Independent-Preprocessing이라고도 합니다. 이는 간선의 비용과는 독립적으로 전처리를 하겠다는 의미입니다.

 

기존 CH에서는 shortcut보다 더 빠른 길(witness path)이 있는지 체크하고 shortcut을 추가했습니다. 반면, CCH는 contraction 단계에서 cost를 고려하지 않습니다. 이에 따라 CH에서보다 shortcut이 더 많이 생성될 수 있습니다. 

 

단, shortcut을 추가할 때는 현재 방문한 정점의 rank보다 더 높은 rank를 가진 정점만을 고려하는 건 동일합니다.

 

CCH의 contracion에서 가장 중요한 특징을 한 문장으로 요약하자면요.

 

 

 arc의 cost와는 독립적이지만, map의 topology에는 의존적입니다.

 

 

 

그렇기에 지도에서 도로 건설 등으로 인해 고유한 정보가 변경되었을 때는 해당 contraction 과정을 업데이트해야 합니다. 

 

 

Contraction의 동작과정

1. 주변 상위 랭크 노드 탐색

2. cost에 상관없이 모든 노드 사이에 지름길 추가

 

contraction이 끝나면 그래프는 chordal(현모양)한 특성을 가집니다. 해당 특성은 비용 전처리에서 유용하게 사용됩니다.

 

그리고, shortcut cost는 무한대 값으로 설정하고 향후 업데이트를 진행합니다.

 

 

---

Metric Customization 

contraction에서 열심히 shortcut을 만들어두었다면, 이제는 비용을 업데이트해야겠죠! Metric Customization은 비용을 업데이트하는 단계입니다. 이를 Metric-Dependent-Customization이라고도 합니다. 

 

Metric Customization은 실시간 교통정보, 유고정보 등 간선의 비용(cost metric)이 변화함에 따라 주기적으로 업데이트가 필요한 작업입니다. 

 

 

 

Metric Customization의 단계

Customization은 두 단계로 이루어져 있습니다. 각 단계에 대해서 자세히 알아보겠습니다.

 

첫 번째는 Basic Customization입니다. 낮은 rank의 노드부터 가장 높은 노드까지 순회하며 shortcut의 비용을 업데이트합니다.

 

두 번째는 Perfect Customization입니다. 높은 rank의 노드부터 가장 낮은 노드까지 순회하며 추가적인 변경이 필요한 비용에 대해 업데이트하고, 필요 없는 간선을 삭제합니다.

 

첫 번째와 두 번째 모두 Customization을 진행할 때 삼각형을 이용합니다. 

2015 Customizable Contraction Hierarchies

 

 

위와 같이 세 개의 인접한 간선으로 연결된 집합을 triangle라고 합니다. 앞선 전처리 단계에서 생성된 그래프에서 노드의 rank와 연결성을 이용하여 노드의 관계를 3가지로 구분할 수 있습니다. 

 

y -> z: lower triangle

x -> z: middle triangle

x -> y: upper triangle

 

해당 triangle을 잘 이용하여 비용을 업데이트하는 과정을 살펴보겠습니다. 

 

 

 

Basic Customization

lower triangles 데이터를 이용하여 shortcut의 cost 업데이트합니다. 

 

CH처럼 낮은 rank를 가진 노드를 통해서 가는 길을 갱신합니다. 이처럼 랭크가 낮은 쪽으로 가는 경우를 비용 전처리 단계에서 진행해야 실제 쿼리에서는 rank가 높아지는 쪽으로만 탐색할 수 있습니다.

 

랭크가 낮은 정점부터 높은 정점까지 오름차순으로 순회하며 아크의 lower triangles를 업데이트합니다. 예를 들어, x -> y에 대해 처리할 때 C(x, y) = min(C(x, y), C(x, z) + C(z, y))를 계산합니다. 

 

Perfect Customization

 

middle triangles, upper triangles 데이터를 이용하여 간선(shortcut, 일반 간선)을 업데이트합니다.

 

업데이트되는 cost를 가진 간선은 경로탐색 대상에서 삭제해도 무방합니다. 이미 triangles 내에서 해당 cost보다 더 낮은 cost로 경로 탐색이 가능하기 때문입니다.

 

따라서 해당 단계에서는 업데이트되는 cost를 가진 간선을 삭제합니다. 이를 통해 쿼리 단계에서의 속도 향상을 기대할 수 있습니다.

 

 

---

Query

 

비용 전처리 단계에서 랭크가 낮은 정점을 통해 가는 간선은 업데이트 되었기에 랭크가 높아지는 쪽으로만 탐색해도 됩니다. 

 

쿼리는 CH에서와 마찬가지로 상위 랭크로 향하게 하는 양방향 다익스트라를 이용할 수 있습니다. 하지만, Elimination Tree라는 개념을 이용하면 우선순위 큐 없이도 탐색할 수 있습니다.

 

Elinimation Tree란 CCH 그래프에서 각 정점마다 상위 랭크인 이웃중 랭크가 가장 작은 정점으로만 가는 간선만 남겨두어 트리 형태로 만든 것을 의미합니다. 

 

 

---

정리

 

동작 과정

1. Node Ordering: Nested Dissection(Graph를 blanced하게 partitioning)
2. Metric-Independent-Preprocessing: topology(맵데이터) 변경될 때마다 shortcut을 만드는 작업.
3. Metric-Dependent-Preprocessing: shortcut의 가중치 업데이트하는 작업.
4. Query: Graph에서 경로 탐색

 

특징

1. 비용에 상관없이 그래프의 연결 관계가 같다면 항상 같은 지름길이 생김.
2. 일부 비용이 바뀐다고 해도 해당 부분과 연관된 일부 지름길의 비용만 수정하기에 굉장히 빠름.
3. 비용 값만 따로 저장할 수 있음.

 

장점

• 빠른 쿼리 (우선순위 큐 사용x)
• 거리와 거의 상관없는 균일한 쿼리 성능
• 빠른 간선 가중치 업데이트

 

단점

• 긴 전처리 시간
• 간선 수 증가로 인한 메모리 증가
• 길찾기 옵션별 가중치 전처리로 인한 메모리 증가
• 효율적인 1:N 탐색 불가

 

 

Perfect Customization

• Middle, upper를 이용해 shortcut 업데이트를 수행함.
• basic과는 반대로 high rank부터 순회함.
• shortcut 뿐만 아니라 일반 arc에도 데이터를 업데이트함.

 

 

경로 쿼리

1. CH처럼 양방향 다익스트라를 사용하여 출도착 지점으로부터 상위 랭크로 향하는 아크로만 탐색함.
2. Elimination Tree 이용하면 우선순위 큐 없이도 탐색 가능함 (CCH 그래프에서 각 정점마다 상위 랭크인 이웃 중 랭크가 가장 작은 정점으로 가는 아크만을 남겨두어 트리 형태로 만든 것)