Algorytm Kruskala

Minimalne drzewo rozpinające, tworzenie (1) Przykładowe wykonania algorytmu Kruskala
Matroid MST (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:

  1. Posortuj krawędzie rosnąco według ich wag, umieść je w kolejce.
  2. Pobierz z kolejki krawędź o najmniejszej wadze, usuń ją z kolejki.
  3. 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.
  4. 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.
Ocena: +1 Tak Nie
Liczba głosów: 1.

Dodano: 5 kwietnia 2017 12:16, ostatnia edycja: 24 kwietnia 2020 19:28.

REKLAMA

Zobacz też

Algorytm genetyczny – jedna z metaheurystyk inspirowanych biologiczną ewolucją.

Pojęcie algorytmu genetycznego nie jest powiązane z żadnym konkretnym problemem obliczeniowym, algorytm ten może być wykorzystywany do rozwiązywania różnych problemów. Algorytm genetyczny nie próbuje rozwiązywać problemu w sposób analityczny, ale próbuje uzyskać jak najlepsze rozwiązania poprzez wybieranie jak najlepszych cech rozwiązań z określonej puli. Implementując algorytm genetyczny należy przedstawić potencjalne rozwiązanie problemu w postaci jakiejś struktury danych, a następnie zdefiniować operacje krzyżowania, mutacji i selekcji. Zakładamy, że z każdym kolejnym pokoleniem rozwiązania występujące w populacji będą coraz lepsze.

→ Czytaj całość

Algorytm Edmondsa-Karpa – algorytm wyszukiwania maksymalnego przepływu w sieci przepływowej. Jest to przypadek szczególny algorytmu Forda-Fulkersona.

W algorytmie Edmondsa-Karpa ścieżka powiększająca wyznaczana jest za pomocą przeszukiwania grafu wszerz. Dzięki temu w każdej iteracji algorytmu dołączana jest zawsze najkrótsza (pod względem liczby krawędzi) ścieżka powiększająca. W metodzie Forda-Fulkersona sposób wyznaczania ścieżki powiększającej jest dowolny.

→ Czytaj całość

Algorytm memetyczny – algorytm będący połączeniem algorytmu genetycznego i metod lokalnej optymalizacji. Czasami określany również jako hybrydowy algorytm ewolucyjny.

→ Czytaj całość
Polityka prywatnościKontakt