컴퓨터 과학자, 1996년 이후 28년 만에 난제 돌파

“인도공과대학 간디나가르(IIT Gandhinagar) 연구진이 1996년 이후 약 25~28년간 미해결이던 '모든 쌍 최단경로(APSP)' 문제의 한계를 돌파했다. 새 알고리즘은 여러 규모에서 네트워크 연결을 샘플링하는 방식으로 속도를 유지하면서도 근접한 지점들에 대해 더 신뢰할 수 있는 거리 추정치를 제공한다.”

AI 요약

인도 공과대학 간디나가르(IIT Gandhinagar) 소속 컴퓨터 과학자가 1996년 이후 약 28년간 풀리지 않던 '전체 쌍 최단 경로(All-Pairs Shortest Paths, APSP)' 문제의 한계를 돌파했다. 기존 방법은 밀집 네트워크에서 입방 시간(cubic time)이 소요돼 노드 수가 두 배가 되면 연산량이 약 8배로 폭증하는 문제가 있었다. 새 알고리즘은 속도를 희생하지 않으면서도 서로 가까운 지점들에 대해 더 신뢰할 수 있는 거리 추정치를 제공하며, 그 비결은 여러 규모에서 네트워크 연결을 샘플링하는 더 영리한 방식에 있다. 이는 1996년 Dor·Halperin·Zwick(DHZ)이 먼 지점에 대해 2배 이내 근사치를 제공한 성과 이후의 진전이다.

핵심 포인트

  • 1996년 DHZ 방법 이후 약 28년 만에 APSP 문제의 기존 한계 돌파
  • 기존 방식은 밀집 네트워크에서 입방 시간 소요, 노드 두 배 시 연산량 약 8배 증가
  • 새 알고리즘은 속도 유지하면서 근접 지점에 대한 거리 추정 정확도 향상
  • 다중 규모 네트워크 연결 샘플링 기법이 핵심 돌파구

향후 전망

  • 교통·통신 네트워크, 단백질·뉴런 등 생물학적 네트워크 분석 효율성 향상 기대
  • 대규모 그래프 연산이 필요한 내비게이션·물류 시스템 등 실용 응용 확대 전망
Share

이것도 읽어보세요

댓글

이 소식에 대한 의견을 자유롭게 남겨주세요.

댓글 (0)

불러오는 중...