Contraction Hierarchies - 현실에서 쓰이는 길찾기 알고리즘
안녕하세요. NewCodes입니다!
이번 글에서는 현실에서 쓰이는 길찾기 알고리즘인
CH(Contraction Hierarchies)에 대해 알아보겠습니다.
해당 글을 읽기 전에
사전지식으로 다익스트라와 A* 알고리즘이 필요합니다!
CH 알고리즘이란
'적절한 지름길을 미리 만들어두고
효율적으로 탐색할 수 있게 하는 알고리즘'을 의미합니다.
그리고 CH 알고리즘은 현재 카카오맵, 티맵에서 쓰이는
CCH 알고리즘의 근간이 됩니다.
CH 알고리즘에 대해 학습하기 이전에
학습할 필요성을 알아보기 위해
우선 다익스트라와 A* 알고리즘에 대해 간단히 짚어보겠습니다.
괜찮은 다익스트라 알고리즘 있는데 왜 굳이 CH가 필요해?
다익스트라 알고리즘은 최단 경로를 찾는 데 자주 활용됩니다. 특히 게임에서 그러합니다. 하지만 수많은 데이터가 존재하는 실제 도로 네트워크에서는 활용하기에 효율적이지 않습니다. 다익스트라는 목표 방향에 있지 않은 노드를 탐색하며 비용을 갱신하는 데 시간을 허비합니다. 예를 들면 아래 그림과 같습니다.
출발지에서 도착지까지의 최단 경로를 찾기 위해 위와 같이 많은 탐색 범위를 할애해야 합니다. 직관적으로 보면 출발지 기준 왼쪽 부분은 전혀 탐색할 필요가 없는 영역입니다. 이를 탐색하지 않게 하려면 어떻게 해야 할까요?
어떻게 알고리즘에게 저 영역은 불필요한 영역이란 걸 알려줄 수 있을까요?
해결책은 휴리스틱(heuristic)이었습니다.
다익스트라에 휴리스틱을 적용하여 보완한 알고리즘이 A*입니다.
A* 알고리즘은 휴리스틱을 이용해 불필요한 노드를 방문하지 않고 효율적으로 최단 경로를 찾을 수 있습니다. 하지만 여기서도 효율성의 문제가 발생합니다. 출발지와 목적지가 전국 단위로 상당히 긴 경우, 아래 사진과 같이 여전히 많은 정점을 방문하게 됩니다.
<A* 알고리즘의 탐색 범위>
그렇다면 이러한 A*의 문제점을 어떻게 보완할 수 있을까요? 어떻게 더욱 더 적은 노드를 방문하여 최적의 경로를 찾을 수 있을까요?
해결책은 지름길(shotcut)이었습니다.
사용자가 서울에서 부산까지 향하는 최적 경로를 요청했다고 해봅시다. 이때, 서울에서 대구까지의 최적 경로를 미리 DB에 저장해 두고 이를 활용하면 더욱더 효율적인 탐색을 할 수 있습니다. 이를 활용한다면 직접 탐색해야 하는 영역은 결국 대구에서 부산까지이니까요!
그리고 서울에서 대구까지와 같은 경로를 CH 알고리즘에서는 shortcut이라고 합니다. 전처리 과정에서 이와 같은 shortcut을 많이 만들어두면 효율적인 탐색을 하는 데 도움이 됩니다.
하지만 서울에서 대구까지의 최적 경로는 실시간 교통 상황, 도로 공사, 일기 예보에 따라 유동적으로 변해야 합니다. 이러한 변수가 있을 때마다 shortcut을 갱신해야 한다면, shortcut을 차라리 안 만드는 게 더 빠를 수도 있습니다.
그래서 CH에서의 관건은 전처리 과정에서 '적절한 shortcut'을 만들어두는 것입니다. 적절한 shorcut이란 너무 길지도 짧지도 않으며, 많은 경로 탐색에서 활용될 수 있는 shortcut을 의미합니다.
적절한 지름길을 통해 탐색한다면 아래와 같이 탐색 범위를 줄일 수 있게 됩니다.
<CH 알고리즘의 탐색 범위>
길찾기 알고리즘의 속도를 향상시키기 위해서는 본질적으로 두 가지 측면을 고려할 필요가 있습니다. 바로 전처리와 쿼리입니다. 적절한 전처리를 해둔다면 광범위한 정보를 컴팩트하게 줄일 수 있습니다. 쿼리를 할 때 특정 노드들을 배제시킬 수 있다면 훨씬 더 빠르게 쿼리할 수 있습니다. 그리고 전처리를 적절히 해둔다면 쿼리 향상 속도를 기대할 수 있습니다.
다익스트라에서 A*로의 발전은 더욱더 적은 범위의 탐색, 즉 쿼리의 향상으로 이루어진 것이었습니다.
반면, A*에서 CH로의 발전은 쿼리와 더불어 전처리까지 극적으로 효율을 향상시킨 것이었습니다. 하지만 쿼리 시간이 효율적인 반면, 이전에 비해 전처리에 더욱 많은 시간을 할애해야 합니다. 물론 전처리가 아무리 길고 복잡하더라도 실제 사용자가 서비스를 이용할 때는 쿼리만 이루어지기에 사용자가 길어진 전처리를 체감할 순 없습니다.
결국 속도 향상을 위해서는 전처리와 쿼리 사이의 시소를 타야하는 것과 마찬가지입니다. 속도 향상과 유지 보수 등을 위해서는 적절한 무게중심을 잡는 것이 중요합니다.
기본 아이디어
우선 CH에서 핵심이 되는 기본 아이디어부터 살펴보겠습니다.
(a) 그림을 살펴봅시다. v에서 w로 가기 위해서는 u를 거쳐 총 7의 비용이 발생합니다. 이때, v에서 w로 향하면서 비용이 7인 shortcut을 생성할 수 있습니다.
이러한 방식으로 그래프에서 여러 개의 shortcut을 생성해두면 경로를 쿼리할 때 빠르게 정점을 탐색할 수 있습니다. 기존의 그래프에서는 v에서 w로 가기 위해서는 u를 거쳐야 했지만, shortcut을 생성해 두면 바로 w로 갈 수 있으니까요!
Contraction
shortcut을 여러 개 만들며 그래프를 전처리하는 과정을 Contraction이라고 합니다. 이 과정에서는 모든 정점을 방문하면서 shortcut 생성을 시도합니다.
우선 shortcut을 생성하기 전에 어떤 정점부터 방문할 건지 각 노드의 순서를 정해야 합니다. 이를 node ordering이라 하며, 이는 글의 마지막에서 다시 집중적으로 다루겠습니다. 지금은 node order가 임의로 정해져 있다고 가정하고 설명하겠습니다.
위 그림을 다시 살펴보겠습니다. (위 그림은 전체 그래프를 나타낸 게 아니라 이해를 돕기 위해 그래프의 일부분을 간단히 나타낸 것입니다.) 깜찍한 이모티콘 위에 보시면 node order라고 표시되어 있습니다. node order가 낮은 정점은 아래, 높은 정점은 위에 배치하여 나타낸 그래프입니다.
shotcut을 생성하기 위해서 특정 노드를 방문할 때는 node order가 낮은 순서대로 각각의 노드를 방문합니다. (위 그래프는 u를 방문한 상태를 가정한 겁니다.) 그리고 u에 연결된 간선을 탐색합니다. 탐색할 때는 node order가 높은 쪽으로만 탐색하여 shortcut 생성을 시도합니다.
Contraction을 할 때는 중요한 규칙이 있습니다. 현재 방문한 노드의 order보다 더 높은 order만을 고려하여 shortcut을 생성해야 합니다. 이러한 규칙의 효용성에 대해서는 쿼리 부분에서 더 자세히 설명드리겠습니다. 우선은 이러한 규칙이 있다라는 걸 기억해 둡시다!
그래서 위 그림은 u를 방문하여 더 높은 order를 가진 정점들을 고려해 적절히 shortcut을 만든 케이스입니다.
그런데 shortcut을 생성하지 않는 경우도 있습니다.
현재 정점 u를 방문한 상황입니다. u보다 node order가 높으면서 u와 연결된 노드는 v와 w입니다. 이때 shortcut을 생성한다 하면, 비용이 7인 shortcut이 생성됩니다. 하지만, 파란색 경로를 보면 총 비용이 6인 경로가 존재합니다.
이 때는 shortcut을 생성할 수 없습니다. 생성하고자 하는 shortcut의 비용보다 더 적은 비용의 길이 있다면, shortcut을 생성하지 않습니다. shortcut의 생성 유무와 상관없이 경로를 쿼리할 때는 최단 경로인 파란색 경로가 채택될 것이며, 이러한 경우에 shortcut을 생성하는 건 오히려 탐색 시간을 늘리게 됩니다. (쿼리에서는 양방향 다익스트라를 활용합니다. 쿼리 단계에서 더 자세히 살펴볼게요!)
그리고 위와 같이 생성하려고 했던 shortcut의 비용보다 더 적은 비용을 가진 파란색 경로를 witness path라고 합니다. shortcut을 추가할 때는 항상 더 나은 witness path가 있는지 체크해야 합니다.
이를 체크하기 위해서는 다익스트라 알고리즘을 사용할 수 있습니다. 구체적으로 어떻게 사용하는지는 다음과 같습니다.
현재 shortcut을 생성하려 방문한 노드인 u를 제외한 그래프를 준비합니다. 그러고는 v에서 출발하여 w로 도착할 때까지 다익스트라 알고리즘을 수행합니다. 이후, u를 활용한 shortcut의 비용과 다익스트라를 활용하여 산출한 비용을 비교합니다. 그리고 shortcut의 비용이 더 적을 때만 shortcut을 추가합니다.
Shortcut을 생성하는 일반적인 조건
shortcut을 추가하는 핵심을 정리해 보자면요.
(U는 u의 집합을, W는 w의 집합을 의미합니다.)
U와 W의 모든 각각의 u, w 정점에 대해
<uvw> path가 u에서 w로 가는 유일한 shortest path라면,
shortcut을 추가할 수 있습니다.
하지만, shortcut이 가장 짧은 길인지 확인하기 위해서는 매번 다익스트라 알고리즘을 사용하는 건 다소 시간이 걸릴 수 있습니다. 특히, 간선의 수가 해당 탐색 범위에 간선이 많이 참여하고 있다면 더더욱 느려질 것입니다.
물론 이를 최적화하는 방법도 있습니다. 양방향 다익스트라를 활용하여 탐색 범위를 제한해 볼 수 있습니다.
Contraction의 과정을 직접 살펴보자.
지금까지는 그래프의 일부분만 가져와서 shortcut을 생성하는 과정을 살펴봤는데요. 이제는 전체 그래프에서 어떻게 Contration이 이루어지는지 직관적으로 살펴보겠습니다.
아래 그래프는 총 8개의 노드가 존재합니다. 그리고 임의로 각각의 노드에 대한 order를 부여했습니다. (노드의 중요도를 설정하는 node ordering에 대해서는 뒤에서 자세히 다루겠습니다!!)
GIF를 보시면 노드의 order 순서대로 방문하여 shortcut 생성 프로세스를 거치는 모습을 보실 수 있습니다.
더 자세히 보고 싶으신 분은 아래 슬라이드를 살펴주세요!
위 슬라이드를 보시면서 Contraction에 대한 전반적인 과정을 시각적으로 살펴보며, 어느 조건에서 shortcut이 생성되는지 그리고 그 이유는 무엇인지에 대해서 생각해 보시면 좋습니다!!
여기서 한 가지 말씀 안 드린 점이 있습니다. 정점 u에 대한 contracion을 할 때는 모든 간선을 삭제하고, shortcut을 추가합니다.
그리고 Contraction 과정이 모두 종료되면, 해당 과정에서 생성된 shortcut들을 overlay graph에 저장합니다. overlay graph란, 원래 그래프에서 생성된 shortcut들을 추가한 그래프를 의미합니다. 그림으로 보면 아래와 같습니다.
쿼리할 때는 위 그래프를 활용합니다. 해당 그래프를 활용하는 건 쿼리에서 더 자세히 살펴보시죠!
Contration의 과정 요약
이제 마지막으로 contraction에 대한 전반적인 과정을 요약해 보겠습니다.
- 방문: 현재 처리하지 않은 노드 중 node order가 가장 낮은 노드를 선택합니다.
- 판단: 선택된 노드에서 연결된 노드 중 node order가 높은 노드를 탐색합니다. 선택된 노드를 거쳐 v에서 w로 가는 경로보다 더 빠른 길이 있는지 판단합니다.
- 처리: 더 빠른 길이 없다면 shortcut을 생성하고, 그렇지 않다면 shortcut을 생성하지 않습니다.
- 삭제: 이미 처리한 노드와 간선은 삭제합니다.
- 반복: node order에 따라 모든 정점에 대해 1~4의 과정을 반복합니다.
- 저장: 생성된 shortcut을 overlay G* 그래프에 저장합니다.
Query
드디어 쿼리 단계입니다! CH 쿼리에서는 양방향 다익스트라를 활용합니다. 이는 두 가지 검색으로 이루어져 있습니다.
정방향 검색 (forward search): upward graph에서 s(출발지)로부터 노드를 탐색하는 것
역방향 검색 (backward search): downward graph에서 t(도착지)로부터 노드를 탐색하는 것
upward graph는 node order가 높아지는 쪽의 간선만 남긴 부분 그래프를, downward graph는 node order가 낮아지는 쪽의 간선만 남긴 부분 그래프를 의미합니다.
역방향 검색을 할 때는 downward graph에서 모든 간선의 방향을 뒤집을 뒤, t에서부터 역방향 검색을 시작하게 됩니다.
정방향 검색과 역방향 검색의 탐색 공간이 서로 겹치는 부분이 생기면, 각각의 검색에서 우선순위 큐에 있는 모든 key에 대해 임시 최단 경로를 추적합니다. 그리고 모든 key가 처음 겹쳤을 때의 최단 경로보다 큰 게 확인이 되면 비로소 쿼리를 중단합니다.
위와 같이 하는 이유는 정방향 검색과 역방향 검색이 처음 만났다고 해서 최단 경로를 보장하는 건 아니기 때문입니다. 아래 그림을 살펴봅시다.
쿼리를 시작하게 되면 두 검색은 x에서 처음으로 만나게 될 것입니다. 이때, 역방향 검색 우선순위 큐에는 y가 있을 것입니다. y를 통해서 가는 최단 경로를 검색하면 5이고 이는 6보다 작은 수치입니다. 따라서, 처음 만난 x에서는 최단 경로를 보장하지 못합니다.
이후, 역방향 검색에서는 y에 방문하여 s로 가는 간선을 relax할 것입니다. 이에 따라 최단경로는 s -> y -> t로 찾아질 것입니다.
쿼리할 때 가장 중요한 규칙
쿼리할 때 각각의 검색에서 꼭 지켜야 하는 중요한 규칙이 있는데요. 바로 node order가 높은 쪽으로만 탐색하는 겁니다. 왜 높은 쪽으로만 탐색해야 할까요?
node order가 낮은 쪽으로 탐색해서는 안 되는 걸까요?
결론부터 말씀드리자면, 낮은 쪽으로도 탐색한다고 해서 최단 경로를 못 찾는 건 아닙니다. 하지만, 시간이 훨씬 더 오래 걸립니다. 그리고 굳이 낮은 쪽을 탐색할 이유가 없습니다.
왜냐하면 contraction 과정에서 shortcut을 생성한 결과물을 살펴봅시다. v -> w shorcut은 v -> u -> w를 표현한 것입니다. shortcut은 v와 w보다 order가 낮은 u를 방문하여 가는 길입니다. 그리고 우리는 contraction에서 모든 노드에 대해 다음과 같은 shortcut 생성 과정을 거쳤습니다.
정리하자면 우리는 contraction에서 '모든 각각의 노드에 대해 order가 낮은 노드를 통해 가는 shortcut 생성'을 시도했습니다. 즉, order가 낮은 쪽의 간선은 이미 전처리 과정에서 처리되었기에, 낮은 쪽은 탐색할 필요가 없어집니다.
물론, 실제 최단 경로에서는 order가 낮은 쪽 노드를 방문해야 할 수도 있습니다. 하지만 이는 역방향 검색을 통해 처리될 수 있습니다.
해당 그래프에서 최단 경로는 y를 거치는 것입니다. 최단 경로에서 낮은 order를 포함하고 있습니다. 해당 최단 경로는 역방향 검색에서 노드가 높은 쪽으로 탐색했을 때 찾아지는 경로입니다. 그러므로 낮은 쪽의 노드를 탐색하지 않아도 역방향 탐색이 이를 보완해 줍니다.
또한, shortcut의 특성상 order가 낮은 노드를 방문하지 않아도 됩니다.
아래 overlay 그래프를 살펴보시면 u에서 출발하여 z로 도착하는 상황을 가정한 겁니다. 파란색 영역은 정방향 탐색을, 빨간색 영역은 역방향 탐색을 진행한 겁니다. 또한, 점선은 이미 생성된 shortcut을 의미합니다.
여기서 유심히 보실 건 빨간색 영역입니다. z에서 v로 갈 때 shortcut이 활용되었습니다. 그리고 z에서 v로 가는 길은 z보다 order가 낮은 x를 통해서 가는 길이었습니다. 노드가 낮은 쪽으로 가는 길은 이미 shortcut이 포함하고 있기에 노드가 낮은 쪽은 탐색할 이유가 없는 것이죠.
그래서 contraction 과정에서 각 노드를 방문하여 shortcut을 생성할 때 현재 노드보다 더 높은 order를 가진 노드만을 고려했던 것입니다. 그래야 order가 낮은 노드를 통해서 가는 shortcut이 생성되니까요! 그리고 이는 쿼리에서 order가 낮은 쪽을 탐색하지 않아도 되게 하는 엄청난 시간 효율 이점을 가져오니까요!!!
shortcut unpack
쿼리에서 최단 경로를 찾았다고 해서 끝이 아닙니다. 우리가 설정했던 shortcut이 최단 경로 안에 포함되어 있다면 이를 unpack하는 과정이 필요합니다. 마치 우리가 용량이 큰 파일을 압축했다가 압축 해제를 하는 것처럼 말이죠.
unpack 과정을 위해서는 Contraction을 할 때 v -> u -> w를 v- > w로 단축한다고 하면, u에 shotcut 데이터를 저장해 둡니다.
그런 다음 unpack을 할 때 가장 order가 높은 노드에서 G* U 그래프 의 최단 경로를 양방향으로 풀기 시작합니다. 일반 Dijkstra 알고리즘에서와 같이 상위 에지 포인터를 역추적하고, 상위 에지에 바로가기 포인터가 있는 경우 상위 에지를 바로가기 에지로 바꾸고 계속해서 전체 경로를 재귀적으로 압축 해제합니다.
쿼리 정리
쿼리에서 이점은 자기 자신보다 order가 높은 노드만을 탐색하는 데 있습니다. 이로 인해 그래프 자체는 더 복잡했을지언정 탐색 공간 자체는 현저하게 줄어듭니다.
Node Ordering
어쩌면 CH에서 가장 중요한 문제일 수도 있습니다. 어떻게 노드를 정렬하느냐에 따라 생성되는 shortcut의 양상과 개수가 달라지기 때문입니다. 그리고 이는 쿼리 시간에 직접적으로 영향을 미치게 됩니다.
또한, 지름길이 너무 많으면 그래프가 dense 해져서 쿼리가 느려질 수 있습니다.
적절히 ordering하기 위해서는 휴리스틱을 활용해 볼 수 있습니다. 여기에서 가장 기본 아이디어는 contract 할만해 보이는 매력적인 노드를 추정하여 우선순위 큐에 삽입하는 것입니다.
해당 맥락에서 자주 쓰이는 휴리스틱은 Edge Difference입니다. Edge Difference란 'v로 인해 도입된 지름길의 수 - v와 인접한 간선의 개수'를 의미합니다.
Edge Difference 값이 작을수록 먼저 contract 하기 용이한 node입니다. 왜냐하면 처음에 edge difference가 큰걸 contract 하게 되면, 길이 복잡하게 얽히게 됩니다. shortcut이 많아져 쿼리할 때 고려해야 할 경로가 많아질 수 있습니다.
그래서 각 노드에 대해 edge difference 값을 계산한 후 이에 따라 우선순위 큐에 삽입하여 node ordering을 진행하게 됩니다.
위 휴리스틱만으로도 좋은 CH 알고리즘을 만들 수 있습니다. 하지만 한 가지 문제가 발생합니다. 하나의 노드가 contract 되면 그 인접 노드가 contract 할 때 영향을 줄 수 있습니다. 이전에 가졌던 값과는 다른 값을 가질 수도 있습니다.
edge difference 값을 엄격히 준수하려면 각 노드가 contract 될 때마다 다시 우선순위 큐를 갱신해야 합니다. 이때 lazy update 휴리스틱을 고려할 수 있습니다.
우선 초기 노드 순서 계산된 상황임을 가정하겠습니다. 하나의 노드를 contract 한 뒤, 우선순위 큐에서 다음으로 뽑힐 node에 대해서 다시 edge difference를 계산합니다. 여전히 해당 값이 제일 작다면 계속 진행하고, 그게 아니라면 우선순위 큐를 업데이트하고 다음 노드에 대해서도 똑같은 과정을 반복합니다.
이로 인해 전처리는 더 길어지겠지만, 쿼리 속도 향상을 기대할 수 있습니다!
실제 CH에서는 edge difference와 contracted neighbors보다 더욱 정교한 단어들을 사용한다고 합니다. 그래도 이 두 가지 개념은 Node ordering 할 때 꼭 알고 있어야 할 개념입니다!!
정리
CH(Contraction Hierarchies) 알고리즘은 '적절한 지름길을 미리 만들어두고 효율적으로 탐색할 수 있게 하는 알고리즘'을 의미합니다.
동작 과정
- 랭크 부여(Node ordering): 각 정점에 랭크를 매김.
- Contraction(단축 경로 생성): 지름길 추가 & 비용 전처리
- 정점 선택: 랭크가 낮은 순서대로 정점을 뽑음. (u: 현재 정점, s와 t: u와 인접한 정점)
- 지름길 추가: 경로 P(s, u, t)가 s에서 t로 가는 최단 경로인 경우, dist(s, u) + dist(u, t) 값을 가진 지름길을 추가함.
- Hierarchies(계층을 두고 탐색):
- u(출발지), v(도착지) 양쪽에서 시작하는 양방향 다익스트라로 랭크가 높은 쪽으로 탐색함.
CH의 단점으로는 실시간성 이슈에 빠르게 대처하기 어렵다는 점이 있습니다. 특정 도로 구간의 정체, 기상 악화 등으로 인한 이슈가 생기면 그래프의 모양이 똑같더라도 간선의 비용이 달라지기 때문에 지름길을 다시 작업해야 합니다.
이러한 단점을 보완하기 위한 알고리즘이 바로 CCH입니다!
CCH에 대해서는 다음 글에서 다뤄보겠습니다!
레퍼런스
- Geisberger, Robert, et al. “Contraction hierarchies: Faster and simpler hierarchical routing in road networks.” International Workshop on Experimental and Efficient Algorithms. Springer, Berlin, Heidelberg, 2008.
- https://jlazarsfeld.github.io/ch.150.project/
- https://tech.kakao.com/2021/05/10/kakaomap-cch/
- https://brunch.co.kr/@tmapmobility/3
'Computer Science > Algorithm' 카테고리의 다른 글
| 백준 3190번 뱀 - 자세한 풀이 (Java) (6) | 2024.05.23 |
|---|---|
| 카카오맵이 최적 경로를 결정하는 데까지 (2) | 2024.02.07 |
| 카카오맵과 티맵이 사용하는 알고리즘 - Customizable Contraction Hierarchies (2) | 2024.02.06 |
| A* 알고리즘이 도대체 뭔데?? (with java) (2) | 2024.01.20 |
| 왜 카카오맵은 더 느린 길을 최적 경로라 판단할까? (1) | 2024.01.15 |
