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

「가중 방향 그래프 G=(V,E)에서 각 모서리의 가중치는 실수입니다. 또한 소스라고 하는 V의 정점도 제공됩니다.

소스에서 다른 모든 정점까지의 최단 경로 길이는 단일 소스 최단 경로(SSSP) 문제입니다. 전 세계 연구자들은 반세기 이상 이 문제를 해결하기 위해 열심히 노력해 왔습니다. 이제 코펜하겐 대학교 컴퓨터 과학과 연구팀이 마침내 알고리즘 퍼즐을 성공적으로 풀었습니다.

음의 가중치 SSSP 알고리즘: 빠르고 효율적

논문 링크: https://arxiv.org/abs/2203.03456

한 인터뷰에서 연구원 Christian Wulff -Nilsen은 다음과 같이 말했습니다. 그들의 솔루션은 30년 이상 존재했던 Õ(

n

(4/3) log W) 작동 시간 제약을 돌파한 최초의 음수 가중치를 갖는 SSSP 조합 알고리즘입니다. SSSP에는 Dijkstra 알고리즘(Dijkstra 알고리즘)과 Bellman-Ford 알고리즘(Bellman-Ford 알고리즘)이라는 두 가지 기본 알고리즘이 있으며 둘 다 고유한 제한 사항이 있습니다.

Dijkstra 알고리즘은 작동 시간이 가장 짧고 거의 선형 시간 O(

m

+ n log n)에 도달할 수 있지만 음의 가중치 가장자리를 계산할 수는 없습니다. Bellman-Ford 알고리즘은 음의 가중치 모서리를 계산할 수 있지만 작업 시간이 너무 길어서 O(

mn

)에 도달합니다. 현재 음의 가중치 모서리를 해결하기 위한 최첨단 SSSP 알고리즘은 복잡한 연속 최적화와 동적 대수 및 그래픽 알고리즘에 의존합니다. 이는 이후 세대의 학자들이 계속해서 알고리즘을 최적화하더라도 계산 시간에는 여전히 Õ(n(4/3) log W)이 필요하다는 사실로 이어집니다. 이러한 계산 시간 제약은 30년 동안 존재해 왔습니다. 이러한 한계에 직면한 Wulff-Nilsen은 두 가지 질문을 제기했습니다.

1) 음수 가중치 에지 알고리즘의 작동이 선형에 가까운 시간을 달성할 수 있습니까?

2) 간단한 도구로 이것이 가능합니까?

시간과 품질이 모두 필요한 방법이 있나요?

말하지 마세요. 실제로 존재합니다.

Wulff-Nilsen이 제안한 알고리즘은 이미지 스케일링 알고리즘으로, 간단한 이미지 분해 알고리즘인 Low Diameter Decomposition을 통해 향상되었습니다. 일반적으로 이 분해 알고리즘은 음수 가중치가 없는 가장자리의 그래프 분해에만 사용되며, 본 연구의 기여 중 하나는 음수 가중치 가장자리 이미지에 적용하여 음수 가중치 가장자리 SSSP 재귀 스케일링 알고리즘을 강화하는 것입니다.

파생 과정Wulff-Nilsen은 Johnson의 가격 알고리즘을 기반으로 합니다. 제안: 이미지

G

= (

V, E,

w)에서 Φ를 임의의 함수로 둡니다: V→Z. w(Φ)를 가중치 함수로 둡니다.

정의: , : . 이미지 G = (V, E,w) 및 이미지 G' = (V, E,w'), if: 1) 이미지 G의 최단 거리는 이미지의 최단 거리 G'와 같고 그 반대도 마찬가지입니다. 2) G에는 G'에 음의 가중치가 포함된 경우에만 음의 가중치 링이 포함됩니다. 그러면 G 이미지는 G' 이미지와 같습니다.

Corollary 2.7 임의의 이미지 와 가격 함수 Φ를 고려해보세요. 인유, v ∈ V,

. 그리고 어느 반지에서든 C,

. 따라서 G과 은 동일합니다. , , 인 경우 G과 G'은 동일합니다.

이 알고리즘의 목적은 음의 가중치 주기가 없다는 가정 하에 가격 함수 Φ를 계산할 때 GΦ의 모든 간선 가중치를 음수가 아닌 값으로 만드는 것입니다. 그런 다음 에서 Dijkstra의 알고리즘을 실행할 수 있습니다.

이후 Wulff-Nilsen은 자신의 알고리즘 프레임워크를 소개하기 시작했습니다. ㅋㅋㅋ s는 최단 경로 트리를 출력합니다. 러닝타임은 O(

m

+ n log n) 입니다.

G가 DAG(방향성 비순환 그래프)인 경우 에 음수가 아닌 가중치 가장자리가 있도록 가격 함수 Φ를 계산하는 것은 간단합니다. v1, ..., vn을 반복하고 설정하면 됩니다. Φ(vi) 들어오는 모든 가장자리 가중치가 음수가 아니도록 합니다.

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

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

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

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

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

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

). 이는 ScaleDown 출력의 정확성을 증명합니다.

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

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

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

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

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

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

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

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

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

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

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

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

위 내용은 60년 전의 퍼즐! 코펜하겐 대학의 연구원들이 '단일 소스 최단 경로' 문제를 해결했습니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!