60년 전의 퍼즐! 코펜하겐 대학의 연구원들이 '단일 소스 최단 경로' 문제를 해결했습니다.

단일 소스 최단 경로 문제의 목적은 주어진 시작 노드에서 네트워크의 다른 모든 노드까지의 최단 경로를 찾는 것입니다.

네트워크는 노드와 노드 사이의 연결(에지)로 구성된 그래프로 표현됩니다.

각 가장자리에는 방향(예: 일방통행 도로를 나타내는 데 사용할 수 있음)과 해당 가장자리를 따라 이동하는 비용을 나타내는 가중치가 있습니다. 모든 간선 가중치가 음수가 아닌 경우 문제는 고전적인 Dijkstra 알고리즘을 사용하여 거의 선형 시간 내에 해결될 수 있습니다.

새로운 결과는 Dijkstra 알고리즘과 거의 동시에 이 문제를 해결하지만 음의 가장자리 가중치도 허용합니다.

이후 Wulff-Nilsen은 조합 도구에서 가장 중요한 두 가지 알고리즘인 ScaleDown 및 SPmain을 언급했습니다.

ScaleDown 알고리즘은 단계적으로 실행되며, 마지막 단계에서는 ElimNeg()를 사용하여 가격 함수 Φ2를 계산합니다. ElimNeg가 종료되면 가격 함수 ψ′, 를 반환하여 모든 가장자리 값을 음수가 아닌 값으로 만듭니다. 음수 가중치. 이는 모든 , 이 조건을 충족한다는 의미입니다(왜냐하면

알고리즘이 종료되면 모든 및 에 대해 이 적분이고 모든 에 대해 입니다.

이는 모든 , 을 의미합니다. 따라서 그래프 G*에는 음수가 아닌 가중치가 있습니다.

귀납법을 통해 이론이 에 대해 성립한다고 가정하면 알고리즘의 5번째 줄에서 ScaleDown에 대한 호출은 필요한 입력 속성을 충족합니다.

따라서 출력과 ScaleDown을 통해 을 얻을 수 있습니다.

, 만약 C가 에 있는 음수 가중치 링이면 에 있는 의 모든 값은 2n의 배수이고 ; 또한 , 이므로 은 Corollary 2.7과 일치하지 않습니다.

따라서 에 음수 가중치 사이클이 포함되어 있으면 알고리즘이 종료되지 않는다는 결론을 내릴 수 있습니다.

이를 통해 SPmain 알고리즘의 정확성을 증명할 수 있습니다.

이 시점에서 Wulff-Nilsen의 음수 가중치 SSSP 솔루션에서 가장 중요한 두 가지 알고리즘이 사실임이 입증되었습니다. 새로운 알고리즘은 선형에 가까운 시간을 보장하면서 음의 가중치를 성공적으로 도입했습니다. ​60년이 지난 지금, 답을 찾는 것은 단순한 퍼즐 그 이상입니다.

작년에 Wulff-Nilsen은 같은 분야에서 또 다른 돌파구를 마련했습니다. 시간 경로에 따라 변화하는 네트워크. 최근 수수께끼에 대한 그의 해결책은 이 작업을 기반으로 합니다.

그는 SSSP 문제를 해결하면 전기 자동차가 목적지까지의 가장 빠른 경로를 즉시 계산하는 데 도움이 될 뿐만 아니라 가장 에너지 효율적인 방식으로 그렇게 할 수 있도록 보장하는 알고리즘의 길을 열 수 있다고 믿습니다.

Wulff-Nilsen은 다음과 같이 설명했습니다. “우리 알고리즘은 이전 알고리즘에는 없는 차원인 음의 가중치를 추가합니다. 실제적인 예는 산에서 운전할 때 음의 가중치 차원을 사용하여 내비게이션 시스템이 경로를 추천할 수 있다는 것입니다. 울프-닐센은 자사의 알고리즘이 전기차 경로 계획뿐 아니라 모니터링에도 활용될 수 있다고 말했다. 금융업계에서는 추측이 나온다. 그는 “원칙적으로 이 알고리즘은 중앙은행 등 이용자에게 조기경보를 제공하고, 각종 화폐 매매를 투기하는 투기꾼에게 경고하는 용도로 사용할 수 있다”며 “지금은 많은 범죄자들이 컴퓨터를 이용해 범죄를 저지르고 있지만 우리 알고리즘은 1959년 Dijkstra가 처음으로 최단 거리 문제를 제안했을 때 그는 사람들이 이 문제를 더 이상 지속적으로 최적화해 왔다고 생각하지 못했을 것입니다. 60년 이상 계획. 퍼즐에 대한 답이 그토록 풍부한 의미를 담고 있다는 사실에 놀랄 수도 있습니다.

아마 이것이 과학의 매력이 아닐까 싶습니다.