AI 요약
인도 공과대학 간디나가르(IIT Gandhinagar) 소속 컴퓨터 과학자가 1996년 이후 약 28년간 풀리지 않던 '전체 쌍 최단 경로(All-Pairs Shortest Paths, APSP)' 문제의 한계를 돌파했다. 기존 방법은 밀집 네트워크에서 입방 시간(cubic time)이 소요돼 노드 수가 두 배가 되면 연산량이 약 8배로 폭증하는 문제가 있었다. 새 알고리즘은 속도를 희생하지 않으면서도 서로 가까운 지점들에 대해 더 신뢰할 수 있는 거리 추정치를 제공하며, 그 비결은 여러 규모에서 네트워크 연결을 샘플링하는 더 영리한 방식에 있다. 이는 1996년 Dor·Halperin·Zwick(DHZ)이 먼 지점에 대해 2배 이내 근사치를 제공한 성과 이후의 진전이다.
핵심 포인트
- 1996년 DHZ 방법 이후 약 28년 만에 APSP 문제의 기존 한계 돌파
- 기존 방식은 밀집 네트워크에서 입방 시간 소요, 노드 두 배 시 연산량 약 8배 증가
- 새 알고리즘은 속도 유지하면서 근접 지점에 대한 거리 추정 정확도 향상
- 다중 규모 네트워크 연결 샘플링 기법이 핵심 돌파구
향후 전망
- 교통·통신 네트워크, 단백질·뉴런 등 생물학적 네트워크 분석 효율성 향상 기대
- 대규모 그래프 연산이 필요한 내비게이션·물류 시스템 등 실용 응용 확대 전망
출처:ScienceDaily
