Dlaczego algorytm Dijkstry używa klawisza zmniejszania?


95

Nauczyłem się, że algorytm Dijkstry był następujący

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)

Ale czytałem trochę na temat algorytmu i wiele wersji, które widzę, używa klawisza zmniejszania zamiast wstawiania.

Dlaczego tak jest i jakie są różnice między tymi dwoma podejściami?


14
Downvoter - Czy możesz wyjaśnić, co jest nie tak w tym pytaniu? Myślę, że jest to całkowicie sprawiedliwe i wiele osób (w tym ja) po raz pierwszy zapoznało się z wersją Dijkstry OP, a nie z wersją z klawiszem zmniejszania.
templatetypedef

Odpowiedzi:


71

Powodem używania klawisza zmniejszania zamiast ponownego wstawiania węzłów jest utrzymanie małej liczby węzłów w kolejce priorytetowej, dzięki czemu całkowita liczba usuwanych z kolejki priorytetowych jest niewielka, a koszt salda każdej kolejki priorytetowej jest niski.

W implementacji algorytmu Dijkstry, który ponownie wstawia węzły do ​​kolejki priorytetowej z ich nowymi priorytetami, jeden węzeł jest dodawany do kolejki priorytetów dla każdej z m krawędzi na grafie. Oznacza to, że w kolejce priorytetowej istnieją operacje m enqueue i m dequeue, co daje całkowity czas wykonania O (m T e + m T d ), gdzie T e to czas wymagany do umieszczenia w kolejce priorytetowej, a T d to czas potrzebny do usunięcia z kolejki priorytetowej.

W implementacji algorytmu Dijkstry, który obsługuje klawisz zmniejszania, kolejka priorytetowa, w której znajdują się węzły, zaczyna się od n węzłów i na każdym kroku algorytmu usuwa jeden węzeł. Oznacza to, że całkowita liczba usunięć z kolejki sterty wynosi n. Każdy węzeł będzie miał wywoływany klawisz zmniejszania potencjalnie raz dla każdej krawędzi prowadzącej do niego, więc całkowita liczba wykonanych klawiszy zmniejszania wynosi co najwyżej m. Daje to czas działania (n T e + n T d + m T k ), gdzie T k jest czasem wymaganym do wywołania klawisza zmniejszania.

Jaki to ma wpływ na środowisko wykonawcze? To zależy od używanej kolejki priorytetowej. Oto krótka tabela, która przedstawia różne kolejki priorytetowe i ogólne czasy wykonywania różnych implementacji algorytmów Dijkstry:

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)

Jak widać, w przypadku większości typów kolejek priorytetowych tak naprawdę nie ma różnicy w asymptotycznym czasie wykonywania, a wersja z klawiszem zmniejszania prawdopodobnie nie będzie działać dużo lepiej. Jeśli jednak użyjesz implementacji kolejki priorytetowej stosu Fibonacciego , to rzeczywiście algorytm Dijkstry będzie asymptotycznie bardziej wydajny przy użyciu klawisza zmniejszania.

Krótko mówiąc, użycie klawisza zmniejszania oraz dobrej kolejki priorytetowej może obniżyć asymptotyczny czas działania Dijkstry poza to, co jest możliwe, jeśli nadal będziesz wykonywać kolejki i dekolejki.

Oprócz tego niektóre bardziej zaawansowane algorytmy, takie jak algorytm najkrótszych ścieżek Gabowa, używają algorytmu Dijkstry jako procedury podrzędnej i polegają w dużej mierze na implementacji klawisza zmniejszania. Korzystają z faktu, że znając zakres prawidłowych odległości z wyprzedzeniem, możesz zbudować super wydajną kolejkę priorytetów na podstawie tego faktu.

Mam nadzieję że to pomoże!


1
+1: Zapomniałem wyjaśnić stos. Jedno zastrzeżenie, ponieważ sterta wersji wstawiania ma węzeł na krawędź, tj. O (m), czy jej czasy dostępu nie powinny wynosić O (log m), dając całkowity czas wykonania O (m log · m)? Mam na myśli, że na normalnym wykresie m nie jest większe niż n ^ 2, więc to redukuje się do O (m log n), ale na wykresie, na którym dwa węzły mogą być połączone wieloma krawędziami o różnych wagach, m jest nieograniczone (oczywiście , możemy twierdzić, że minimalna ścieżka między dwoma węzłami wykorzystuje tylko minimalne krawędzie i zredukować to do normalnego wykresu, ale bez przerwy jest to interesujące).
rampion

2
@ rampion - Masz rację, ale ponieważ wydaje mi się, że ogólnie zakłada się, że równoległe krawędzie zostały zredukowane przed uruchomieniem algorytmu, nie sądzę, aby O (log n) kontra O (log m) miało duże znaczenie. Zwykle zakłada się, że m to O (n ^ 2).
templatetypedef

28

W 2007 roku ukazała się praca, w której badano różnice w czasie wykonania między wersją z klawiszem zmniejszającym a wersją z wkładką. Zobacz http://www.cs.utexas.edu/users/shaikat/papers/TR-07-54.pdf

Ich podstawowym wnioskiem nie było użycie klawisza zmniejszania dla większości wykresów. Zwłaszcza w przypadku rzadkich wykresów klawisz bez zmniejszania jest znacznie szybszy niż wersja z klawiszem zmniejszania. Zobacz artykuł, aby uzyskać więcej informacji.


7
cs.sunysb.edu/~rezaul/papers/TR-07-54.pdf to działający link do tego dokumentu.
eleanora

OSTRZEŻENIE: w połączonym artykule jest błąd. Strona 16, funkcja B.2: if k < d[u]powinna być if k <= d[u].
Xeverous

2

Istnieją dwa sposoby implementacji Dijkstry: jeden używa sterty obsługującej klawisz zmniejszania, a drugi sterty, która tego nie obsługuje.

Oba są ogólnie ważne, ale to drugie jest zwykle preferowane. W dalszej części użyję „m” do oznaczenia liczby krawędzi, a „n” do oznaczenia liczby wierzchołków naszego wykresu:

Jeśli chcesz uzyskać najlepszą możliwą złożoność w najgorszym przypadku, wybierz stertę Fibonacciego, która obsługuje klawisz zmniejszania: otrzymasz ładne O (m + nlogn).

Jeśli zależy Ci na przeciętnym przypadku, możesz również użyć stosu binarnego: otrzymasz O (m + nlog (m / n) logn). Dowód jest tutaj , strony 99/100. Jeśli wykres jest gęsty (m >> n), zarówno ten, jak i poprzedni mają tendencję do O (m).

Jeśli chcesz wiedzieć, co się stanie, jeśli uruchomisz je na prawdziwych wykresach, możesz zapoznać się z tym artykułem, jak zasugerował Mark Meketon w swojej odpowiedzi.

Wyniki eksperymentów pokażą, że w większości przypadków najlepsze wyniki da „prostsza” sterta.

W rzeczywistości, wśród implementacji, które używają klawisza zmniejszania, Dijkstra działa lepiej, gdy używa prostej sterty binarnej lub sterty parowania, niż gdy używa sterty Fibonacciego. Dzieje się tak, ponieważ sterty Fibonacciego obejmują większe stałe współczynniki, a rzeczywista liczba operacji klawiszem zmniejszania jest zwykle znacznie mniejsza niż przewiduje to najgorszy przypadek.

Z podobnych powodów sterta, która nie musi obsługiwać operacji klawiszem zmniejszania, ma jeszcze mniej stałych współczynników i faktycznie działa najlepiej. Zwłaszcza jeśli wykres jest rzadki.

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.