제가 주로 하는 분야가 지도자료를 처리하는 겁니다.

그중 가장 실생활에 관련이 많은 최단경로(길찾기)에 대해서 소개하려고 합니다.

여기서

최단 경로 알고리즘은

그래프(Graph)에서 두 노드(정점)를 잇는

간선들의 가중치 합이 최소가 되는 경로를 찾는 방법입니다

라고 쓰면 아무도 안 읽을 것이고 ㅎㅎ

길게 설명하는 대신 그림으로 대~~~충 설명하겠습니다.

길찾는 것이 쉬운게 아니었구나 하고

느끼실 수 있으시면 좋겠습니다.

순서는

교과서에서 나오는 알고리즘부터

카카오/티맵 지도에서 실제로 사용하는 알고리즘까지

입니다.

밑의 그림들에서

노란색은 두 지점 간의 최단경로를 찾을 때

여기가 맞나 하고 중간에 계산해보는 지점들입니다.

당연히 이 지점이 많을수록 찾는 속도가 느려집니다.

최단경로 알고리즘은 이 지점을 줄이고자 하는 노력으로 보시면 됩니다.

[다익스트라 (Dijkstra) 알고리즘 - 50만 개 계산]

최단경로 알고리즘으로 교과서에 나오는 것은

다익스트라 (Dijkstra) 알고리즘입니다.

대용량 자료를 다루는 실무에서는 못씁니다.

노란색 영역을 보시면 알겠지만

뭐 저기까지 찾나 하는 지점들이 너무 많습니다.

매 순간 가장 최선이라고 생각되는 선택을 하는 문제 해결 방식인데

Greedy 방식이라고 합니다.

참고로 다익스트라 알고리즘은 나온지 60년이 넘어가는데

이것을 뛰어넘는 알고리즘이 작년에 나왔습니다.

[컴퓨터 과학 혁신, 다익스트라 알고리즘 60년 지배 깨뜨리다]

https://kitpa.org/news/360

관심있으신 분들은 보셔도 좋을 것 같습니다.

[양방향 다익스트라(Bidirectional Dijkstra) 알고리즘 - 22만 개 계산]

다익스트라 알고리즘을

양쪽에서 찾는 방식으로 개선한 알고리즘입니다

개선은 했지만

그래도 역시 최단경로 알고리즘에서는 무식한 방법입니다. -_-

[A* 알고리즘 - 5만 개 계산]

실제 서비스 혹은 게임에서 사용하는 알고리즘의 출발점입니다.

지도자료가 작으면 그럭저럭 쓸만 합니다.

A* 알고리즘은

Pruning(가지치기)을 과감하게 도입하여

다익스트라 알고리즘에 비교해

계산량을 대폭 줄이고 효율성을 높인 알고리즘입니다.

이런 방식을 Heuristic 방식이라고 합니다.

이 방식은 별거 아닙니다.

그냥 경험상으로

여기는 맞는 것 같아 혹은

여기는 아닌 것 같아 하는

규칙을 만들어서

계산량을 줄이는 겁니다.

최단경로에서는

저 노란색을 줄이고자 하는 규칙을 만드는 겁니다.

일반적으로 두 지점 간 직선거리를 기준으로 규칙을 만듭니다.

[양방향 A* 알고리즘 - 2.5만 개 계산]

A* 알고리즘을

양쪽에서 찾는 방식으로 개선한 알고리즘입니다

[CH (Contraction Hierarchies) 알고리즘 - 600 개 계산]

실제로 카카오맵/티맵에서 서비스하는 알고리즘에 해당합니다.

이 알고리즘은 지름길 알고리즘 이라고도 하는데

간단히 말하면

효율적인 지름길을 미리 계산해서 만들어 놓고

지름길을 통해 필요한 곳만 찾는 알고리즘입니다.

뭐가 지름길일까 결정하는 것이 이 알고리즘의 핵심입니다.

이것을 최적화라고 하는데

이 계열 알고리즘의 성능이 여기서 좌우됩니다.

[카카오맵이 빠르게 길을 찾아주는 방법: CCH를 이용한 개편기]

https://tech.kakao.com/posts/436

[네비 개발자여, 번개처럼 빠른 경로탐색엔진을 만들라]

https://brunch.co.kr/@tmapmobility/3

실제 개발자들이 이 알고리즘을 어떻게 적용했는지 설명하고 있는 문서입니다.

참 CCH 알고리즘은 CH 알고리즘을

실시간 도로상황을 반영할 수 있도록 개선한 알고리즘이고,

같은 계열이라고 보시면 됩니다.

역시 관심있는 분들은 보셨으면 합니다.

개발자들은 아시겠지만

서비스를 제공하기 위해서는

알고리즘 외에 신경써야 할 것이 더 많습니다.

그런 것 하라고 개발자들이 있는거죠...

다른 분들은 패스하시면 됩니다. -_-

그리고 여기까지 읽으신 분들 존경합니다. ㅎㅎ

긴 글 읽어주셔서 감사합니다.