# ETH 취리히 연구진, 최속 흐름 알고리듬 개발 > Clean Markdown view of GeekNews topic #15608. Use the original source for factual precision when an external source URL is present. ## Metadata - GeekNews HTML: [https://news.hada.io/topic?id=15608](https://news.hada.io/topic?id=15608) - GeekNews Markdown: [https://news.hada.io/topic/15608.md](https://news.hada.io/topic/15608.md) - Type: GN+ - Author: [neo](https://news.hada.io/@neo) - Published: 2024-06-30T10:34:08+09:00 - Updated: 2024-06-30T10:34:08+09:00 - Original source: [ethz.ch](https://ethz.ch/en/news-and-events/eth-news/news/2024/06/researchers-at-eth-zurich-develop-the-fastest-possible-flow-algorithm.html) - Points: 1 - Comments: 0 ## Topic Body ##### 컴퓨터 및 정보 기술 연구 - ETH Zurich의 연구원들이 네트워크 흐름 알고리듬을 개발함 - 이 알고리듬은 모든 종류의 네트워크에서 최대 교통 흐름을 최소 비용으로 계산함 - 이 알고리듬은 이론적으로 가능한 가장 빠른 속도로 계산을 수행함 ##### 혁신적인 알고리듬의 개발 - Rasmus Kyng과 그의 팀이 개발한 이 알고리듬은 네트워크 흐름 문제를 해결하는 데 있어 획기적인 성과를 이룸 - 이 알고리듬은 유럽 교통 네트워크와 같은 복잡한 네트워크에서도 최적의 교통 흐름을 계산할 수 있음 - 이전에는 네트워크 데이터 처리보다 최적의 흐름을 계산하는 데 더 많은 시간이 걸렸으나, Kyng의 알고리듬은 이 문제를 해결함 ##### 네트워크 크기와 계산 시간의 동시 증가 - Kyng의 접근 방식은 네트워크 크기와 계산 시간이 동일한 비율로 증가하도록 함 - 2000년대 초반까지는 m1.5의 속도로 계산되었으나, Kyng의 알고리듬은 추가 계산 시간을 거의 무시할 수 있을 정도로 빠름 ##### 거의 선형 시간 알고리듬 - Kyng의 팀은 고정된 네트워크뿐만 아니라 동적으로 변화하는 네트워크에서도 최적의 흐름을 계산할 수 있는 알고리듬을 개발함 - 이 알고리듬은 분자나 뇌와 같은 매우 복잡하고 데이터가 많은 네트워크에서도 유용함 ##### 변화하는 네트워크를 위한 번개 같은 알고리듬 - Simon Meierhans는 변화하는 네트워크에서 최소 비용 최대 흐름 문제를 해결하는 새로운 알고리듬을 발표함 - 이 알고리듬은 새로운 연결이 추가되거나 제거되는 네트워크에서도 최적의 경로를 계산할 수 있음 ##### Kyng의 접근 방식의 혁신성 - Kyng의 접근 방식은 많은 작은 효율적이고 저비용의 계산 단계를 결합하여 더 빠른 계산을 가능하게 함 - 이 접근 방식은 철도 네트워크와 전력망의 장점을 결합하여 새로운 방법을 창출함 ##### 이론적 컴퓨터 과학의 전환점 - Kyng의 연구는 새로운 수학적 도구를 사용하여 알고리듬을 더욱 빠르게 만듦 - 이러한 도구는 네트워크 데이터 구조를 조직화하여 네트워크 연결의 변화를 빠르게 식별할 수 있게 함 ##### GN⁺의 의견 - Kyng의 알고리듬은 이론적 컴퓨터 과학에서 중요한 진전을 이룬 것으로 평가됨 - 이 알고리듬은 매우 큰 문제를 효율적으로 해결할 수 있는 기반을 마련함 - 변화하는 네트워크에서의 빠른 계산은 실시간 데이터 처리와 같은 다양한 응용 분야에서 유용할 것임 - 유사한 기능을 가진 다른 프로젝트로는 Google의 PageRank 알고리듬이 있음 - 새로운 기술을 채택할 때는 기존 시스템과의 호환성 및 유지 보수 비용을 고려해야 함 ## Comments _No public comments on this page._