1950년대 알고리즘 수수께끼의 탁월한 솔루션으로 찬사를 받았습니다. 날짜: 2022년 11월 14일 원천: 코펜하겐 대학교 - 과학 학부 요약: 수수께끼를 풀면 전기 자동차 배터리 소모를 줄이고 미래의 통화 투기꾼의 삶을 더 어렵게 만들 수 있습니다. 이 발견은 최고의 연구 논문상을 수상했으며 미국에서 열린 이 분야의 가장 권위 있는 회의에서 영예를 얻었습니다.
반세기 이상 동안 전 세계의 연구자들은 "단일 소스 최단 경로 문제"로 알려진 알고리즘 문제와 씨름해 왔습니다. 문제는 본질적으로 음의 가중치를 가진 연결이 있을 수 있는 네트워크의 노드와 다른 모든 노드 사이에서 가장 짧은 경로를 가장 잘 찾는 수학적 레시피를 고안하는 방법에 관한 것입니다.
복잡하게 들리나요? 혹시. 그러나 실제로 이러한 유형의 계산은 예를 들어 Google 지도가 풍경과 도시를 통해 우리를 안내하는 것처럼 우리가 길을 찾는 데 의존하는 다양한 앱과 기술에서 이미 사용되고 있습니다.
이제 코펜하겐 대학교 컴퓨터 과학과의 연구원들은 수십 년 동안 연구원과 전문가를 당황하게 만든 수수께끼인 단일 소스 최단 경로 문제를 해결하는 데 성공했습니다.
"우리는 가능한 가장 빠른 방법으로 거의 선형 시간에 문제를 해결하는 알고리즘을 발견했습니다. 1950년대부터 연구되어 전 세계적으로 가르치는 근본적인 알고리즘 문제입니다. 이것이 우리가 해결하도록 자극한 이유 중 하나였습니다. "라고 Christian Wulff-Nilsen 부교수는 미해결 알고리즘 문제를 내버려두는 것이 어렵다고 분명히 설명합니다.
전기 자동차 경로를 위한 더 빠른 계산
작년에 Wulff-Nilsen은 동일한 영역에서 시간이 지남에 따라 변화하는 네트워크에서 최단 경로를 찾는 방법을 다루는 결과를 내는 또 다른 돌파구를 마련했습니다. 최근 수수께끼에 대한 그의 해결책은 그 작업을 기반으로 합니다.
연구원은 단일 소스 최단 경로 문제를 해결하면 전기 자동차가 A에서 B까지의 가장 빠른 경로를 즉시 계산하는 데 도움이 될 뿐만 아니라 가장 에너지 효율적인 방식으로 계산하는 알고리즘의 길을 열 수 있다고 생각합니다.
"우리는 이전 알고리즘에 없는 차원을 추가하고 있습니다. 이 차원을 통해 우리가 음수 가중치라고 부르는 것을 볼 수 있습니다. 이에 대한 실질적인 예는 도로 네트워크의 언덕을 참조하는 것일 수 있습니다. 내리막길을 주행하는 동안 충전되는 전기 자동차가 있습니다."라고 Wulff-Nilsen은 설명합니다.
단일 소스 최단 경로 문제에 대한 사실
단일 소스 최단 경로 문제 의 목적은 주어진 시작 노드에서 네트워크의 다른 모든 노드까지의 최단 경로를 찾는 것입니다. 네트워크는 노드와 노드 사이의 연결(에지라고 함)로 구성된 그래프로 표시됩니다. 각 가장자리에는 방향(예: 일방통행 도로를 나타내는 데 사용할 수 있음)과 해당 가장자리를 따라 이동하는 데 드는 비용을 나타내는 가중치가 있습니다. 모든 에지 가중치가 음수가 아닌 경우 고전적인 Dijkstra 알고리즘을 사용하여 거의 선형 시간 내에 문제를 해결할 수 있습니다. 새로운 결과는 Dijkstra의 알고리즘과 거의 동일한 시간 내에 문제를 해결하지만 음수 에지 가중치도 허용합니다. "원칙적으로 이 알고리즘은 투기꾼들이 다양한 통화를 매매하기 위해 추측하는 경우 중앙 은행과 같은 행위자에게 경고하는 데 사용될 수 있습니다. 오늘날 컴퓨터를 사용하여 이런 일이 많이 발생합니다. 하지만 우리 알고리즘이 너무 빠르기 때문에 악용되기 전에 허점을 탐지하는 데 사용됩니다."라고 Christian Wulff-Nilsen은 말합니다.
연구원은 전기 자동차의 통화와 경로를 모두 계산하는 시스템이 이미 존재한다고 강조합니다. 그러나 단일 소스 최단 경로 문제를 해결함으로써 연구자들은 속도 면에서 거의 이길 수 없는 뛰어난 알고리즘을 만들 수 있었습니다. 동시에 단순성으로 인해 사회의 다양한 요구에 쉽게 적응할 수 있습니다.
미국에서 명예
문제를 해결하기 위한 노력은 눈에 띄지 않았습니다. 실제로 Christian Wulff-Nilsen과 그의 동료들은 이미 전 세계 사람들로부터 연락을 받아 그들을 축하하고 그들이 어떻게 해냈는지 더 알고 싶어했습니다.
동시에 그들의 발견을 상세히 기술한 연구 논문은 콜로라도주 덴버에서 열린 FOCS(Foundation of Computer Science) 회의에서 "최우수 논문상"을 수상했습니다. STOC와 함께 이론 컴퓨터 과학 분야에서 가장 권위 있는 컨퍼런스입니다. FOCS 회의는 2022년 10월 31일부터 11월 3일까지 진행되었습니다.
Christian Wulff-Nilsen은 "최고의 결과가 발표되는 것을 보기 위해 전 세계 사람들이 이 회의에 참석합니다."라고 말합니다.