[algorithm] Dijkstra의 알고리즘이 감소 키를 사용하는 이유는 무엇입니까?

Program / 글쓴이

Dijkstra의 알고리즘은 다음과 같이 가르쳐졌습니다.

while pqueue is not empty:
    distance, node = pqueue.delete_min()
    if node has been visited:
        continue
    else:
        mark node as visited
    if node == target:
        break
    for each neighbor of node:
         pqueue.insert(distance + distance_to_neighbor, neighbor)

그러나 나는 알고리즘에 대해 약간의 독서를 해왔고, 많은 버전에서 삽입과는 반대로 감소 키를 사용하는 것으로 보입니다.

그 이유는 무엇이며 두 접근 방식의 차이점은 무엇입니까?

답변

노드를 다시 삽입하는 대신 감소 키를 사용하는 이유는 우선 순위 대기열의 노드 수를 작게 유지하여 우선 순위 대기열에서 빼는 총 수를 줄이고 각 우선 순위 대기열 균형의 비용을 낮게 유지하기 위해서입니다.

노드를 새로운 우선 순위로 우선 순위 대기열에 다시 삽입하는 Dijkstra 알고리즘의 구현에서 그래프의 m 개 에지 각각에 대한 우선 순위 대기열에 하나의 노드가 추가됩니다. 즉, 우선 순위 대기열에는 m 개의 대기열에 넣기 작업과 m 개의 대기열에서 빼기 작업이있어 ​​총 런타임이 O (m T e + m T d )가됩니다. 여기서 T e 는 우선 순위 대기열에 추가하는 데 필요한 시간이고 T d 는 우선 순위 대기열에서 대기열을 빼는 데 필요한 시간입니다.

감소 키를 지원하는 Dijkstra의 알고리즘 구현에서 노드를 보유하는 우선 순위 대기열은 n 개의 노드로 시작하고 알고리즘의 각 단계에서 하나의 노드를 제거합니다. 이는 힙 큐에서 빼는 총 수가 n임을 의미합니다. 각 노드에는 잠재적으로 각 에지에 대해 한 번 호출되는 감소 키가 있으므로 수행 된 감소 키의 총 수는 최대 m입니다. 이것은 (n T e + n T d + m T k ) 의 런타임을 제공하며 , 여기서 T k 는 감소 키를 호출하는 데 필요한 시간입니다.

그렇다면 이것이 런타임에 어떤 영향을 미칩니 까? 사용하는 우선 순위 대기열에 따라 다릅니다. 다음은 다양한 우선 순위 대기열과 다양한 Dijkstra 알고리즘 구현의 전체 런타임을 보여주는 빠른 표입니다.

Queue          |  T_e   |  T_d   |  T_k   | w/o Dec-Key |   w/Dec-Key
---------------+--------+--------+--------+-------------+---------------
Binary Heap    |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Binomial Heap  |O(log N)|O(log N)|O(log N)| O(M log N)  |   O(M log N)
Fibonacci Heap |  O(1)  |O(log N)|  O(1)  | O(M log N)  | O(M + N log N)

보시다시피 대부분의 우선 순위 대기열 유형에서 점근 적 런타임에는 실제로 차이가 없으며 키 감소 버전이 훨씬 더 잘할 가능성은 없습니다. 그러나 우선 순위 대기열의 피보나치 힙 구현 을 사용하는 경우 실제로 Dijkstra의 알고리즘은 감소 키를 사용할 때 점근 적으로 더 효율적입니다.

간단히 말해서, 감소 키와 좋은 우선 순위 대기열을 사용하면 대기열에 추가 및 대기열에서 빼기를 계속하면 가능한 것 이상으로 Dijkstra의 점근 적 런타임을 삭제할 수 있습니다.

이 점 외에도 Gabow의 최단 경로 알고리즘과 같은 일부 고급 알고리즘은 Dijkstra의 알고리즘을 서브 루틴으로 사용하고 감소 키 구현에 크게 의존합니다. 그들은 유효한 거리의 범위를 미리 알고 있다면 그 사실을 기반으로 매우 효율적인 우선 순위 대기열을 만들 수 있다는 사실을 사용합니다.

도움이 되었기를 바랍니다!

답변

2007 년에는 감소 키 버전과 삽입 버전 사용의 실행 시간 차이를 연구 한 논문이있었습니다. 참조 http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf를

그들의 기본적인 결론은 대부분의 그래프에 감소 키를 사용하지 않는 것입니다. 특히 희소 그래프의 경우 비 감소 키가 감소 키 버전보다 훨씬 빠릅니다. 자세한 내용은 논문을 참조하십시오.

답변

Dijkstra를 구현하는 방법에는 두 가지가 있습니다. 하나는 감소 키를 지원하는 힙을 사용하고 다른 하나는이를 지원하지 않는 힙을 사용합니다.

둘 다 일반적으로 유효하지만 일반적으로 후자가 선호됩니다. 다음에서는 ‘m’을 사용하여 가장자리 수를 나타내고 ‘n’을 사용하여 그래프의 정점 수를 나타냅니다.

최악의 경우 가장 복잡한 복잡성을 원한다면 감소 키를 지원하는 피보나치 힙을 사용하면됩니다. 좋은 O (m + nlogn)을 얻을 수 있습니다.

평균적인 경우에 관심이 있다면 바이너리 힙도 사용할 수 있습니다. O (m + nlog (m / n) logn)을 얻게됩니다. 증거는 여기 , 페이지 99/100입니다. 그래프가 조밀하면 (m >> n),이 그래프와 이전 그래프는 모두 O (m) 경향이 있습니다.

실제 그래프에서 실행하면 어떻게되는지 알고 싶다면 Mark Meketon이 그의 답변에서 제안한 것처럼 이 문서를 확인할 수 있습니다 .

실험 결과가 보여주는 것은 “단순한”힙이 대부분의 경우 최상의 결과를 제공한다는 것입니다.

실제로 감소 키를 사용하는 구현 중에서 Dijkstra는 간단한 이진 힙 또는 페어링 힙을 사용할 때 피보나치 힙을 사용할 때보 다 더 잘 수행됩니다. 이는 피보나치 힙이 더 큰 상수 인자를 포함하고 실제 감소 키 연산 수는 최악의 경우가 예측하는 것보다 훨씬 적기 때문입니다.

비슷한 이유로 키 감소 작업을 지원할 필요가없는 힙은 더 적은 상수 요소를 가지며 실제로 가장 잘 수행됩니다. 특히 그래프가 희소 한 경우.

답변