Zastanawiałem się, kiedy należy użyć algorytmu Prim, a kiedy Kruskala znaleźć minimalne drzewo rozpinające? Oba mają łatwą logikę, te same najgorsze przypadki, a jedyną różnicą jest implementacja, która może obejmować nieco inne struktury danych. Więc jaki jest decydujący czynnik?
Kiedy powinienem używać Kruskala w przeciwieństwie do Prim (i odwrotnie)?
Odpowiedzi:
Użyj algorytmu Prim, gdy masz wykres z dużą ilością krawędzi.
W przypadku wykresu z krawędziami V wierzchołków E algorytm Kruskala działa w czasie O (E log V), a algorytm Prim może działać w czasie zamortyzowanym O (E + V log V) , jeśli użyjesz sterty Fibonacciego .
Algorytm Prim jest znacznie szybszy w limicie, gdy masz naprawdę gęsty wykres z dużo większą liczbą krawędzi niż wierzchołków. Kruskal działa lepiej w typowych sytuacjach (rzadkie wykresy), ponieważ wykorzystuje prostsze struktury danych.
8
Powiedziałbym „typowe sytuacje” zamiast przeciętnych. Myślę, że to niejasne określenie, na przykład jaki jest „średni rozmiar” tabeli mieszającej? brak pomysłu.
—
yairchu
@SplittingField: Uważam, że porównujesz jabłka i pomarańcze. Zamortyzowana analiza jest prostym sposobem uzyskania pomiaru funkcji (że tak powiem) --- to, czy jest to najgorszy czy średni przypadek, zależy od tego, co udowodnisz. W rzeczywistości (jak teraz patrzę) artykuł na wiki używa języka, który sugeruje, że jest on używany tylko do analizy najgorszych przypadków. Teraz użycie takiej analizy oznacza, że nie można składać tak silnych obietnic dotyczących kosztu konkretnej operacji, ale do czasu wykonania algorytmu rzeczywiście stanie się to przez O (E + VlogV), nawet w najgorszym przypadku.
—
agorenst
Brzmi dobrze w teorii, ale założę się, że niewiele osób może wdrożyć stos Fibonacciego
—
Alexandru,
@tgamblin, w najgorszym przypadku mogą występować krawędzie C (V, 2). Czy zatem komplementarność czasowa algorytmu Prim nie sprowadza się do O (V ^ 2 + VlogV), tj. O (V ^ 2) w przypadku sterty fibonacciego?
—
Zielony goblin,
Jest jeszcze jeden ważny czynnik: wyjście Prims jest MST tylko wtedy, gdy wykres jest podłączony (wydaje mi się, że w innym przypadku nie ma sensu), ale wyjście Kruskala to lasy o minimalnym zasięgu (z pewnym wykorzystaniem).
—
Andrei I
Znalazłem bardzo ładny wątek w sieci, który wyjaśnia różnicę w bardzo prosty sposób: http://www.thestudentroom.co.uk/showthread.php?t=232168 .
Algorytm Kruskala rozwinie rozwiązanie od najtańszej krawędzi, dodając kolejną najtańszą krawędź, pod warunkiem, że nie utworzy cyklu.
Algorytm Prim wyhoduje rozwiązanie z losowego wierzchołka, dodając następny najtańszy wierzchołek, wierzchołek, który nie jest obecnie w rozwiązaniu, ale jest połączony z nim najtańszą krawędzią.
W załączeniu znajduje się ciekawy arkusz na ten temat.
Jeśli zaimplementujesz zarówno Kruskal, jak i Prim, w ich optymalnej formie: odpowiednio z znalezieniem związku i stertą finbonacci, zauważysz, jak Kruskal jest łatwy do wdrożenia w porównaniu z Prim.
Prim jest trudniejszy z kupą Fibonacciego głównie dlatego, że musisz utrzymywać tabelę księgową, aby rejestrować dwukierunkowe połączenie między węzłami grafowymi i węzłami sterty. Z Union Find jest odwrotnie, struktura jest prosta i może nawet produkować bezpośrednio najwięcej bez prawie żadnych dodatkowych kosztów.
Nitpick: Ostatni „slajd” w każdym powinien brzmieć „powtarzaj, aż powstanie drzewo opinające”; dopiero w MST, co jest zadaniem rekurencyjnym - skąd mam wiedzieć, że jest minimalne - dlatego na początek podążam za Primem / Kruskalem!
—
OJFord,
@OllieFord Znalazłem ten wątek, ponieważ przeszukałem prostą ilustrację algorytmów Prim i Kruskal. Algorytmy gwarantują, że znajdziesz drzewo, a to drzewo jest MST. I wiesz, że znalazłeś drzewo, gdy masz dokładnie
—
mikedu95,
V-1 krawędzie.
@ mikedu95 Masz rację, robiąc ten sam punkt, co mój poprzedni komentarz z innej perspektywy.
—
OJFord
Ale czy nie jest to warunek konieczny, aby wybrać tylko jedną wagę między wierzchołkami, nie możesz wybrać wagi 2 więcej niż raz z powyższego wykresu, musisz wybrać następną wagę np .: 3 @Snicolas
—
ani0904071
Wiem, że o to nie prosiłeś, ale jeśli masz więcej jednostek przetwarzających, zawsze powinieneś rozważyć algorytm Borůvki , ponieważ może on być łatwo zrównoleglony - stąd ma przewagę wydajności nad algorytmem Kruskala i Jarníka-Prim.
Kruskal może mieć lepszą wydajność, jeśli krawędzie można posortować w czasie liniowym lub są już posortowane.
Prim jest lepszy, jeśli liczba krawędzi do wierzchołków jest wysoka.
Najgorszym przypadkiem złożoności czasu Kruskala jest O (E log E) , ponieważ musimy uporządkować krawędzie. Prim czas złożoność najgorszy przypadek jest O (log E V) z priorytetu kolejki , a nawet lepiej, O (log E + V V) z Fibonacciego Heap . Powinniśmy użyć Kruskala, gdy wykres jest rzadki, co oznacza niewielką liczbę krawędzi, np. E = O (V), kiedy krawędzie są już posortowane lub jeśli możemy je posortować w czasie liniowym. Powinniśmy używać Prim, gdy wykres jest gęsty, tj. Liczba krawędzi jest wysoka, jak E = O (V²).
Wydaje mi się, że Prim nigdy nie jest gorszy niż Kruskal pod względem szybkości. Ponieważ E powinno wynosić co najmniej V-1, istnieje drzewo opinające. Myślę, że powodem, dla którego możemy preferować Kruskala dla rzadkiego wykresu, jest to, że jego struktura danych jest zdecydowanie prosta.
—
Yu Gu
Jednym z ważnych zastosowań algorytmu Kruskala jest klastrowanie pojedynczego łącza .
Rozważ n wierzchołków, a otrzymasz kompletny wykres. Aby uzyskać klastry ak tych n punktów. Uruchom algorytm Kruskala na pierwszych n- (k-1) krawędziach posortowanego zestawu krawędzi. Otrzymasz k-skupisko wykresu z maksimum rozstaw.
Najlepszy czas na Kruskala to O (E logV). Dla Prim za pomocą hałd możemy uzyskać O (E + V lgV). Dlatego na gęstym wykresie Prim jest znacznie lepszy.
W algorytmie kruskala mamy liczbę krawędzi i liczbę wierzchołków na danym wykresie, ale na każdej krawędzi mamy pewną wartość lub wagę, w imieniu której możemy przygotować nowy wykres, który nie musi być cykliczny lub nie może być zamknięty z żadnej strony Na przykład
wykres taki jak ten _____________ | | | | | | | __________ | | Nadaj nazwę dowolnemu wierzchołkowi a, b, c, d, e, f.