컴퓨터 과학의 상징적 문제인 최단 경로 찾기에 있어, 기존의 속도 한계(정렬 장벽)를 돌파하는 새로운 알고리즘이 개발됐다. 이 혁신적인 방법과 연구의 뒷이야기를 살펴본다.
어려운 문제를 풀고 싶을 때는, 체계적으로 접근하면 도움이 된다. 예를 들어, 문제를 여러 조각으로 나누고, 쉬운 것부터 먼저 해결할 수도 있다. 하지만 이런 정렬(sorting) 방식에는 대가가 따른다. 조각을 순서대로 정렬하는 데 너무 많은 시간을 쓸 수도 있기 때문이다.
이런 딜레마는 컴퓨터 과학에서 가장 상징적인 문제 중 하나, 즉 하나의 네트워크 내에서 특정 시작점에서 다른 모든 지점으로 가는 최단 경로를 찾는 문제에서 특히 중요하다. 이는 이사할 때마다 필요한 문제, 즉 새 집에서 직장, 체육관, 슈퍼마켓까지의 최적 경로를 알아내야 하는 문제와 비슷하다.
“최단 경로 문제는 전 세계 누구나 공감할 수 있는 아름다운 문제입니다.”라고 코펜하겐 대학의 컴퓨터 과학자 미켈 토럽은 말했다.
직관적으로 가까운 목적지의 최단 경로를 가장 쉽게 찾을 수 있다고 생각할 수 있다. 따라서 최단 경로 문제에 대한 가장 빠른 알고리즘을 설계하려면 가까운 점부터 그다음 가까운 점 순서로 찾는 것이 합리적으로 보인다. 하지만 그렇게 하려면 반복적으로 가장 가까운 점이 어디인지 계속 알아내야 하고, 거리에 따라 점들을 정렬하게 된다. 이 방법을 따르는 모든 알고리즘은 근본적인 속도 한계, 즉 정렬 장벽(sorting barrier)에 부딪히게 된다. 정렬에 필요한 시간보다 더 빠를 수는 없다.
40년 전, 최단 경로 알고리즘을 개발하던 연구자들은 이 “정렬 장벽”에 봉착했다. 그런데 최근, 한 연구팀이 이 장벽을 뛰어넘는 새로운 알고리즘을 개발했다. 이 알고리즘은 정렬을 사용하지 않으며, 그 어떤 정렬에 의존하는 알고리즘보다도 빠르다.
“저자들은 이 장벽을 깰 수 있다고 대담하게 생각했습니다.”라고 프린스턴 대학의 컴퓨터 과학자 로버트 타잔이 말했다. “정말 놀라운 결과입니다.”
최단 경로 문제를 수학적으로 분석하기 위해 연구자들은 그래프(graph)라는 언어를 사용한다. 그래프는 점(노드)과 그것들을 연결하는 선(간선)으로 이루어진 네트워크다. 각 간선에는 가중치(weight)라고 불리는 숫자가 붙어 있는데, 그 구간의 거리나 이동에 필요한 시간을 나타낼 수 있다. 두 노드 사이에는 여러 경로가 있을 수 있고, 가중치 합이 가장 작은 경로가 최단 경로다. 주어진 그래프와 특정 "출발 노드(source node)"에 대해, 알고리즘의 목표는 다른 모든 노드까지의 최단 경로를 찾는 것이다.
가장 유명한 최단 경로 알고리즘인 다익스트라 알고리즘은 1956년 선구적 컴퓨터 과학자 에츠허르 다익스트라가 고안했다. 이 알고리즘은 출발 지점에서 시작해 한 단계씩 외부로 확장해나간다. 가까운 노드까지의 최단 경로를 알면, 더 먼 노드로 가는 최단 경로를 찾는 데 도움이 되기 때문에 효과적이다. 그러나 결국 최단 경로를 거리순으로 정렬된 목록으로 만들기 때문에, 정렬 장벽이 실행 속도의 근본적 한계가 된다.
Mark Belan, Samuel Velasco/Quanta Magazine
1984년, 타잔과 또 다른 연구자는 다익스트라의 원래 알고리즘을 개선해 이 속도 한계에 도달했다. 이를 넘어서는 개선은 정렬을 피하는 알고리즘에서만 가능했다.
1990년대 후반과 2000년대 초, 토럽과 동료 연구자들이 정렬 장벽을 깬 알고리즘을 개발했지만 가중치에 대해 특정가정이 필요했다. 그들의 기법을 임의의 가중치에 적용하는 방법은 알려지지 않았고, 더이상 길이 없는 것으로 보였다.
“오랫동안 연구가 멈췄습니다.”라고 칭화대학교의 컴퓨터 과학자 란 두안은 말한다. “많은 사람들이 더 나은 방법은 없다고 믿었습니다.”
두안은 그중 한 명이 아니었다. 그는 모든 그래프에서 정렬 장벽을 뛰어넘는 최단 경로 알고리즘을 언젠가 만들고 싶다는 꿈을 오랫동안 품어왔다. 그러다 결국 지난해 가을, 그는 마침내 해냈다.
두안이 정렬 장벽에 관심을 가진 것은 지금으로부터 거의 20년 전, 미시간대 대학원 시절로 거슬러 올라간다. 그의 지도교수는 특정 경우에 정렬 장벽을 깰 수 있는 방법을 연구한 인물 중 한 명이었다. 하지만 실제로 유망한 접근법을 생각해낸 것은 2021년이 되어서였다.
핵심은 알고리즘이 매 단계마다 어디로 나아갈지를 결정하는 방식에 있었다. 다익스트라 알고리즘은 이미 탐색한 영역의 경계선, 즉 그 “프런티어(frontier)”에 연결된 모든 노드들을 훑으며 어디로 갈지 정한다. 초반에는 시간이 거의 걸리지 않지만, 진행될수록 점점 느려진다.
두안은 프런티어에 있는 이웃 노드들을 클러스터(집단)로 묶어, 각 집단에서 단 하나의 노드만 고려하는 구조를 구상했다. 살펴볼 노드 수가 적어지면, 매번 탐색 속도가 빨라질 수 있다. 게다가 반드시 가장 가까운 노드만 고르지 않아도 되니, 정렬 장벽에 걸리지 않는다. 하지만 클러스터링 접근법이 오히려 알고리즘을 더 느리게 만들 위험도 있어, 이를 실제로 빠르게 작동하도록 만드는 것이 관건이었다.
두안은 다음 해 내내 이 기본 아이디어를 발전시켰고, 2022년 가을쯤에는 기술적 난관을 넘을 수 있다는 낙관이 생겼다. 세 명의 대학원생을 팀에 합류시켜 세부를 조율했고, 몇 달 후 부분적 성공을 거뒀다. 임의의 가중치에 대해서도 정렬 장벽을 깨는 알고리즘, 단 이른바 비방향 그래프(undirected graph)에 한해서였다.
비방향 그래프는 모든 간선을 양방향으로 오갈 수 있다. 컴퓨터 과학자들은 보통 일방통행 경로가 존재하는 더 넓은 범위의 그래프(방향 그래프)에 더 관심을 갖지만, 방향 그래프는 더욱 다루기 어렵다.
“가령, A에서 B로는 쉽게 갈 수 있지만, B에서 A로는 매우 어렵게 되는 경우가 있습니다.”라고 스탠퍼드대 컴퓨터과학 대학원생 샤오 마오는 말했다. “그런 경우가 문제를 어렵게 만듭니다.”
2023년 여름, 마오는 캘리포니아에서 열린 한 학회에서 두안이 비방향 그래프 알고리즘에 대해 강연하는 것을 들었다. 그는 예전부터 두안의 연구를 존경해왔기에, 다가가 대화를 나누었다.
“실제로 그를 처음 만났습니다.” 마오는 회상했다. “아주 흥분되는 경험이었죠.”
학회 이후 마오는 틈틈이 이 문제를 고민했고, 두안과 동료들은 방향 그래프에도 동작할 수 있는 새로운 방법을 모색하고 있었다. 그들은 최단 경로 문제의 또 다른 고전 알고리즘인 벨만-포드(Bellman-Ford) 알고리즘에서 영감을 얻었다. 이 알고리즘은 결과를 정렬하지 않는다. 언뜻 보기에, 벨만-포드 알고리즘은 다익스트라에 비해 훨씬 느려 보였기에 현명치 않은 전략처럼 보일 수 있었다.
“연구를 할 때는 항상 유망해 보이는 길을 따릅니다.”라고 토럽이 말했다. “그런데 벨만-포드를 선택한다는 건 거의 가장 바보 같은 길로 보이기도 하죠.”
하지만 두안의 연구팀은 벨만-포드 알고리즘을 한 번에 몇 단계만 실행하도록 하여 느림을 피했다. 이 선택적 벨만-포드 활용 덕분에, 그들의 알고리즘은 미래에 탐색할 만한 가치가 큰 노드를 미리 파악할 수 있었다. 이런 노드는 도로망에서 주요 간선이 만나는 교차로와 같다.
“그런 노드를 반드시 지나야만 다른 여러 곳으로 가는 최단 경로에 도달할 수 있습니다.” 토럽은 설명했다.
2024년 3월, 마오는 또 다른 유망한 방법을 생각해냈다. 팀의 기존 접근 일부는 무작위성(randomness)을 활용했다. 무작위 알고리즘은 여러 문제를 효율적으로 해결할 수 있지만, 연구자들은 여전히 비무작위적 방식(nonrandom approach)을 선호한다. 마오는 무작위성을 사용하지 않고 최단 경로 문제를 푸는 새 방식을 고안했다. 그는 팀에 합류했고, 이들은 단체 채팅과 화상 통화로 수개월간 힘을 모아 아이디어들을 통합했다. 마침내 가을에, 두안은 자신이 2018년에 다른 그래프 문제의 정렬 장벽을 깬 알고리즘(영문)에서 썼던 기법을 여기에 적용할 수 있음을 깨달았다. 그것이 양방향, 단방향 그래프 모두에서 다익스트라보다 빠른 알고리즘에 필요한 마지막 퍼즐 조각이었다.
완성된 알고리즘은 다익스트라처럼 소스에서 바깥쪽으로 그래프를 계층별로 탐색한다. 하지만 매 단계마다 모든 프런티어를 다루는 대신, 벨만-포드 알고리즘으로 영향력 있는 노드를 식별하고, 이 노드에서 다른 노드들로 전진해 최단 경로를 찾은 뒤, 나중에 나머지 프런티어 노드들을 처리한다. 각 계층 내 노드를 거리순으로 찾지 않기 때문에 정렬 장벽 문제가 걸리지 않는다. 그래프를 적절히 분할하면, 최고 성능의 다익스트라 알고리즘보다 아주 조금 더 빠르다. 훨씬 더 복잡해, 여러 요소가 정교하게 맞물려야 하지만, 흥미롭게도 이들 요소 중에는 고급 수학이 거의 쓰이지 않는다.
“이런 것이 꼭 50년 전쯤 발견됐을 수도 있는데, 아니었다는 점이 그만큼 더 인상적입니다.”라고 토럽은 감탄했다.
두안과 연구진은 앞으로 알고리즘을 더 간소화해 속도를 더 높일 수 있을지 탐구해볼 계획이다. 정렬 장벽이 사라진 지금, 새 알고리즘의 실행 시간은 컴퓨터 과학자들이 아는 어떤 근본적 한계에도 근접하지 않는다.
“저는 낙관론자라서, 혹시라도 더 줄일 수 있을지 놀랍지 않을 겁니다.” 타잔은 말했다. “이것이 마지막 단계라고 결코 생각하지 않습니다.”
