Minimalne drzewo rozpinające
Minimalne drzewo rozpinające (ang. minimum spanning tree, w skrócie MST), inaczej drzewo rozpinające o minimalnej wadze – drzewo łączące wszystkie wierzchołki pewnego grafu spójnego mające najmniejszą możliwą sumę wag krawędzi.
Jeśli graf ma v wierzchołków, to jego drzewo rozpinające zawsze będzie miało v-1 krawędzi. Jeśli ten graf ma e krawędzi, aby utworzyć drzewo rozpinające, trzeba usunąć z grafu e-v+1 krawędzi. Liczba ta jest określana jako liczba cyklomatryczna.
Wyznaczanie minimalnego drzewa rozpinającego
Minimalne drzewo rozpinające można wyznaczyć stosując algorytm Kruskala wykorzystujący strategię zachłanną. Algorytm ten polega na dołączaniu do rozwiązania kolejno najkrótszych możliwych krawędzi, aż do otrzymania drzewa rozpinającego. Przebieg algorytmu można 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.
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: 12.
Dodano: 18 października 2016 18:30, ostatnia edycja: 30 stycznia 2019 14:10.
Zobacz też
Ten artykuł opisuje algorytm rozwiązujący problem wydawania reszty oparty na programowaniu dynamicznym. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego.
Istnieje również pewna modyfikacja tego algorytmu, która została opisana w osobnym artykule.
Algorytm Dijkstry – algorytm służący do wyznaczania najkrótszych ścieżek w grafie. Wyznacza najkrótsze ścieżki z jednego wierzchołka (zwanego wierzchołkiem źródłowym) do pozostałych wierzchołków. Algorytm wymaga, aby wagi krawędzi grafu nie były ujemne. Autorem algorytmu jest holenderski naukowiec Edsger Dijkstra.
Algorytm realizuje podejście zachłanne. W każdej iteracji wybierany jest ten spośród nieodwiedzonych wierzchołków, do którego można dotrzeć najmniejszym kosztem. Po wyznaczeniu ścieżki do konkretnego wierzchołka nie zostanie ona zmodyfikowana w trakcie wykonywania dalszej części algorytmu.
Powtarzalny algorytm najbliższego sąsiada (ang. repetitive nearest neighbour algorithm, w skrócie RNN) – algorytm służący do rozwiązywania problemu komiwojażera korzystający z algorytmu najbliższego sąsiada.
Algorytm polega na wielokrotnym wykonaniu algorytmu najbliższego sąsiada w taki sposób, aby każdy wierzchołek raz był wierzchołkiem początkowym. Następnie algorytm zwraca najlepsze spośród otrzymanych rozwiązań.
Dla grafu pełnego algorytm ma złożoność O(n3), gdzie n jest liczbą wierzchołków. W trakcie wykonywania algorytmu RNN n razy zostanie wykonany algorytm najbliższego sąsiada, który ma złożoność czasową O(n2).
Algorytm RNN nie daje gwarancji znalezienia rozwiązania optymalnego. W odróżnieniu od algorytmu najbliższego sąsiada daje jednak gwarancję, że zwróci rozwiązanie co najmniej tak dobre, jak n/2-1 innych rozwiązań (dowód i więcej informacji na ten temat znajduje się w pracy podanej w bibliografii).