Algorytm Kruskala
(2) Reprezentacja problemu minimalnego drzewa rozpinającego za pomocą matroidu (kliknij ilustrację, aby powiększyć)
Algorytm Kruskala – algorytm wyznaczający minimalne drzewo rozpinające. Algorytm ten wykorzystuje strategię zachłanną, zawsze zwraca rozwiązanie optymalne.
Działanie algorytmu
Algorytm polega na dołączaniu do rozwiązania kolejno najkrótszych możliwych krawędzi, aż do otrzymania drzewa rozpinającego. Algorytm ten można bardziej formalnie zapisać następująco:
- Posortuj krawędzie rosnąco według ich wag, umieść je w kolejce.
- Pobierz z kolejki krawędź o najmniejszej wadze, usuń ją z kolejki.
- Jeśli wierzchołki łączone przez tę krawędź należą do różnych drzew (wówczas dołączenie krawędzi nie spowoduje utworzenia cyklu), dołącz krawędź do rozwiązania.
- Jeśli liczba krawędzi dołączonych do rozwiązania wynosi v-1 (v jest liczbą wierzchołków), zakończ działanie algorytmu. W przeciwnym razie przejdź do punktu 2.
Główna pętla algorytmu wykona się maksymalnie e razy (e jest liczbą krawędzi). W trakcie każdego przebiegu pętli trzeba jednak sprawdzić, czy daną krawędź można dołączyć do rozwiązania. Złożoność obliczeniowa algorytmu zależy od sposobu implementacji sprawdzania tego warunku, a także od sposobu sortowania kolejki krawędzi.
Aby sprawdzać, czy wierzchołki należą do różnych drzew, możemy wykorzystać zbiory wierzchołków. Na początku każdy wierzchołek będzie w osobnym zbiorze. Za każdym razem przed dołączeniem krawędzi sprawdzamy, czy wierzchołki znajdują się w różnych zbiorach. Jeśli tak, krawędź dołączamy do rozwiązania, a te dwa zbiory scalamy.
Zwracanie rozwiązań optymalnych
Algorytm Kruskala (pomimo, że jako algorytm zachłanny zalicza się do heurystyk) zawsze zwraca rozwiązanie optymalne. Problem wyznaczania minimalnego drzewa rozpinającego można przedstawić za pomocą matroidu – przykład jest pokazany na rysunku (2). Udowodniono, że w takim przypadku podejście zachłanne daje gwarancję znalezienia rozwiązania optymalnego. Pełen dowód jest dostępny w książce [1].
Bibliografia
- T.H. Cormen, Ch.E. Leiserson, R.L. Rivest, C. Stein, Wprowadzenie do algorytmów, Wydawnictwo Naukowe PWN, Warszawa, 2012, ISBN 9788301169114.
Liczba głosów: 1.
- Algorytm Kruskala
Dodano: 5 kwietnia 2017 12:16, ostatnia edycja: 24 kwietnia 2020 19:28.
Zobacz też
Matroid – struktura matematyczna składająca się z niepustego zbioru elementów E i takiej rodziny jego podzbiorów I, że spełnione są następujące warunki:
- Jeśli jakiś zbiór należy do I, to wszystkie jego podzbiory także należą do I.
- Jeśli weźmiemy dowolne dwa zbiory należące do I o różnej liczbie elementów, to jesteśmy w stanie dodać do mniejszego z nich taki element z większego (spośród tych, które nie należą do mniejszego), że utworzony w ten sposób zbiór także będzie należał do I.
Drugi warunek, zwany własnością wymiany, formalnie może być zapisany jako:
$$⋀↙{A,B∊I}↙{ |A|>|B| }⋁↙{t∊(A-B)} B∪\{t\} ∈ I$$Co istotne, rodzina zbiorów I nie musi zawierać wszystkich możliwych podzbiorów zbioru E. Ważne tylko, aby była spełniona własność wymiany. Przykładowo, dla E={a,b,c,d} prawidłową rodziną I, może być zarówno { {a,b}, {b,c}, {a}, {b}, {c}, ∅}, jak i { {a}, {b}, {c}, {d}, ∅}. Trywialnym przypadkiem poprawnego matroidu jest taki, w którym rodzina I zawiera jedynie zbiór pusty.
Ten artykuł opisuje pewną modyfikację algorytmu opartego na programowaniu dynamicznym rozwiązującego problem wydawania reszty. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego. Algorytm zaproponował J.W. Wright w pracy The Change-Making Problem (link w bibliografii).
2-opt, algorytm 2-optymalny – algorytm lokalnej optymalizacji wykorzystywany przy rozwiązywaniu problemu komiwojażera. Jest to szczególny przypadek algorytmu k-optymalnego.
Algorytm 2-opt nie służy do wyznaczania trasy, a jedynie do ulepszania jej. Samą trasę można wyznaczyć np. za pomocą algorytmu najbliższego sąsiada. Algorytm może być wykorzystany do ulepszenia algorytmu genetycznego – w ten sposób powstanie algorytm memetyczny.