철도·도로·전력…최대 수송 흐름 위한 계산 알고리즘 개발

스위스연방공대 취리히(ETH Zurich) 연구팀이 철도, 도로, 전력 등 모든 종류 네트워크에서 최소 비용으로 최대 수송 흐름을 계산하는 거의 완벽한 알고리즘을 개발했다. 계산 속도는 수학적으로 이보다 더 빠를 수 없는 속도라고 한다.

수송 흐름 알고리즘은 예를 들어 서울에서 부산까지 가능한 한 많은 상품을 가장 빠르고 저렴하게 운송할 수 있는 경로를 찾는 알고리즘이다. 이번 알고리즘은 철도나 도로를 이용한 물품 운송 뿐 아니라 물이나 인터넷 등 모든 종류 네트워크에서 최적의 수송 흐름을 고속으로 계산할 수 있다.

지금까지 많은 연구자가 수송 흐름 최적화 문제에 도전해 왔지만 네트워크가 크고 복잡해짐에 따라 필요한 계산량이 폭발적으로 증가해 일정 규모 이상 네트워크에 대해서는 계산할 수 없게 됐다.

이번 알고리즘에서는 계산량이 네트워크 크기에 거의 비례한다고 한다. 란다우 표기법으로 표현하면 네트워크 크기를 m이라고 할 때 2000년대까지는 O(m^1.5) 계산량이 필요했던 게 2004년 O(m^1.33)으로 줄었고 이번 알고리즘에서는 네트워크 크기가 커짐에 따라 O(m)에 점근한다. 네트워크를 읽어 들이는 데에는 O(m) 선형 시간이 반드시 필요하기 때문에 이보다 더 계산량을 줄이는 게 거의 불가능해 거의 완벽한 알고리즘이라고 평가받고 있다.

연구팀이 2022년 이 알고리즘을 발표했을 당시에는 연결이 유향인 고정된 정적 네트워크 그러니까 모든 도로가 일방통행인 도시와 같은 네트워크에만 적용 가능했지만 연구팀은 발표 후에도 연구를 계속해 2024년에는 시간에 따라 변화하는 네트워크나 새로운 연결이 추가되거나 삭제되는 네트워크 최적화도 가능하게 됐다.

이번 알고리즘으로 인해 최대 흐름 문제나 최소 비용 문제를 비롯한 중요한 네트워크 흐름 문제는 모두 최소 비용 흐름 문제의 특수 사례로 처리할 수 있게 됐다고 한다. 이번 초고속 알고리즘은 생물학에서의 분자나 뇌 내 네트워크 외에도 인간의 우정 등 동적이며 빠르게 변화하는 복잡하고 데이터양이 많은 네트워크 문제를 다루기 위한 중요한 단계로 평가받고 있다. 관련 내용은 이곳에서 확인할 수 있다.