컴퓨터 및 정보 기술 연구
- ETH Zurich의 연구원들이 네트워크 흐름 알고리듬을 개발함
- 이 알고리듬은 모든 종류의 네트워크에서 최대 교통 흐름을 최소 비용으로 계산함
- 이 알고리듬은 이론적으로 가능한 가장 빠른 속도로 계산을 수행함
혁신적인 알고리듬의 개발
- Rasmus Kyng과 그의 팀이 개발한 이 알고리듬은 네트워크 흐름 문제를 해결하는 데 있어 획기적인 성과를 이룸
- 이 알고리듬은 유럽 교통 네트워크와 같은 복잡한 네트워크에서도 최적의 교통 흐름을 계산할 수 있음
- 이전에는 네트워크 데이터 처리보다 최적의 흐름을 계산하는 데 더 많은 시간이 걸렸으나, Kyng의 알고리듬은 이 문제를 해결함
네트워크 크기와 계산 시간의 동시 증가
- Kyng의 접근 방식은 네트워크 크기와 계산 시간이 동일한 비율로 증가하도록 함
- 2000년대 초반까지는 m1.5의 속도로 계산되었으나, Kyng의 알고리듬은 추가 계산 시간을 거의 무시할 수 있을 정도로 빠름
거의 선형 시간 알고리듬
- Kyng의 팀은 고정된 네트워크뿐만 아니라 동적으로 변화하는 네트워크에서도 최적의 흐름을 계산할 수 있는 알고리듬을 개발함
- 이 알고리듬은 분자나 뇌와 같은 매우 복잡하고 데이터가 많은 네트워크에서도 유용함
변화하는 네트워크를 위한 번개 같은 알고리듬
- Simon Meierhans는 변화하는 네트워크에서 최소 비용 최대 흐름 문제를 해결하는 새로운 알고리듬을 발표함
- 이 알고리듬은 새로운 연결이 추가되거나 제거되는 네트워크에서도 최적의 경로를 계산할 수 있음
Kyng의 접근 방식의 혁신성
- Kyng의 접근 방식은 많은 작은 효율적이고 저비용의 계산 단계를 결합하여 더 빠른 계산을 가능하게 함
- 이 접근 방식은 철도 네트워크와 전력망의 장점을 결합하여 새로운 방법을 창출함
이론적 컴퓨터 과학의 전환점
- Kyng의 연구는 새로운 수학적 도구를 사용하여 알고리듬을 더욱 빠르게 만듦
- 이러한 도구는 네트워크 데이터 구조를 조직화하여 네트워크 연결의 변화를 빠르게 식별할 수 있게 함
GN⁺의 의견
- Kyng의 알고리듬은 이론적 컴퓨터 과학에서 중요한 진전을 이룬 것으로 평가됨
- 이 알고리듬은 매우 큰 문제를 효율적으로 해결할 수 있는 기반을 마련함
- 변화하는 네트워크에서의 빠른 계산은 실시간 데이터 처리와 같은 다양한 응용 분야에서 유용할 것임
- 유사한 기능을 가진 다른 프로젝트로는 Google의 PageRank 알고리듬이 있음
- 새로운 기술을 채택할 때는 기존 시스템과의 호환성 및 유지 보수 비용을 고려해야 함