Drzewa Przemiennych Minimalnych: Dwa Głodne Algorytmy, Jedna Optymalna Odpowiedź

Najtańszy sposób połączenia wszystkiego

Rozpatrując dany zbiór węzłów i składowe krawędzi między niektórymi z nich, minimalne drzewo rozpinające (MST) to podzbiór krawędzi, który łączy każdy węzeł w jedno drzewo – bez cykli, bez oddzielonych części – przy najmniejszej możliwej całkowitej wadze krawędzi. Odpowiada na pytanie, które pojawia się stale w inżynierii: jak rozbudować sieć energetyczną, ułożyć rury, przewodzić kablami lub połączyć zbiór miast drogami, przy najmniejszym możliwym zużyciu materiału, jednocześnie zapewniając, że każdy punkt jest dostępny z każdego innego? Drzewo rozpinające dla n węzłów zawsze ma dokładnie n-1 krawędzi – mniej niż to i coś jest odłączone, więcej niż to i występuje zbędny cykl – więc problem MST polega na tym, wybrać które n-1 krawędzi zachować, spośród wszystkich dostępnych.

Algorytm Kruskala: sortowanie, a następnie przyjmowanie elementów w sposób naiwny

Algorytm Kruskala (1956) jest zaskakująco prosty: posortuj wszystkie krawędzie grafu według wagi, a następnie przejdź przez nie od najtańszej do najbardziej drogiej, dodając każdą krawędź do rosnącego lasu, o ile nie spowoduje to powstania pętli. To pojedyncze globalne prawo – zawsze wybieraj najtańszą krawędź, która nie tworzy pętli – jest wystarczające, aby zagwarantować optymalną odpowiedź, co jest naprawdę zaskakującym faktem, biorąc pod uwagę, jak mało operacji z wyglądania na to poszukiwań wykonuje algorytm.

posortuj wszystkie krawędzie według wagi rosnąco dla każdej krawędzi (u, v) w tej kolejności: jeśli find(u) != find(v): # u i v należą do różnych komponentów union(u, v) # scal je dodaj krawędź (u, v) do MST # zatrzymaj się, gdy dodano n-1 krawędzi

sort all edges by weight ascending
for each edge (u, v) in that order:
    if find(u) != find(v):       # u and v are in different components
        union(u, v)               # merge them
        add edge (u, v) to the MST
# stop once n-1 edges have been added

Algorytm Przegościwa: wzrost jednego drzewa z nasiona

Algorytm Przegościwa (1957, choć rdzeń pomysł ten sięga Jarnika w 1930 roku) podejmuje inne ścieżki do tej samej optymalnej odpowiedzi: zaczyna się od dowolnego pojedynczego węzła i powtarzalnie rozszerza aktualne drzewo o najtańszy brzeg, który łączy węzeł już znajdujący się w drzewie z węzłem jeszcze nie znajdującym się w nim. Tam, gdzie Kruskal myśli globalnie o każdym brzegu w całym grafie naraz, Przegościwo rośnie pojedynczą, połączoną grudę na zewnątrz, jeden brzeg naraz i nigdy nie musi martwić się o przypadkowe stworzenie pętli – przez konstrukcję każdy dodany brzeg łączy nowy węzeł, więc pętla jest strukturalnie niemożliwa.

Zacznij od dowolnego pojedynczego węzła w drzewie, rozmieszczaj priorytetową kolejkę (waga, brzeg) dla każdego brzegu wychodzącego z aktualnego drzewa, ponoć, gdy drzewo ma mniej niż n węzłów: wyciągnij najtańszy (waga, brzeg), którego odległy koniec jeszcze nie znajduje się w drzewie dodaj ten brzeg i jego odległy koniec do drzewa rozmieszczaj wszystkie brzegi wychodzące z nowo dodanego węzła W przypadku stosowania kopca binarnego jako priorytetowej kolejki, algorytm Przegościwa działa w czasie O(E log V); z kopcem Fibonacciego poprawia się do O(E + V log V), co ma znaczenie dla bardzo gęstych grafów. W praktyce Przegościwo ma tendencję do bycia lepszym wyborem dla gęstych grafów (wiele brzegów w stosunku do węzłów), ponieważ nigdy nie musi sortować brzegów, które nigdy nie dotkną, podczas gdy Kruskal ma tendencję do preferowania w przypadku rzadkich grafów, ponieważ sortowanie krótkiej listy brzegów jest tanie, a operacje Union-Find są minimalne.

start with any single node in the tree
maintain a priority queue of (weight, edge) for every edge leaving the current tree
while the tree has fewer than n nodes:
    pop the cheapest (weight, edge) whose far endpoint is not yet in the tree
    add that edge and its far endpoint to the tree
    push all edges leaving the newly added node

Dlaczego oba algorytmy gwarantują optymalność: właściwość cięcia

Oba algorytmy opierają się na tym samym teoretycznym twierdzeniu, właściwości cięcia: dla każdego sposobu podziału węzłów grafu na dwie niepuste grupy, najtańszy element przechodzący między tymi grupami musi należeć do drzewa minimalnego obwodu (zakładając różne wagi krawędzi, dla uproszczenia). Kruszkal wykorzystuje to implikacyjnie zawsze wybierając globalnie najtańszą bezpieczną krawędź; Prim wykorzystuje to wyrazściej na każdym kroku, wybierając najtańszą krawędź przechodzącą między "węzłami już w drzewie" a "węzłami jeszcze nie w drzewie". Ponieważ każda pojedyncza dodana przez algorytm krawędź spełnia właściwość cięcia, argument indukcyjny pokazuje, że zbiór krawędzi ostateczny musi być prawidłowym drzewem minimalnym obwodu – trafne decyzje, podejmowane poprawnie, łańcuchowo tworzą globalnie optymalną strukturę, co jest niezwykłe; większość problemów optymalizacji grafowych nie pozwala na rozwiązanie wyłącznie oparte na algorytmach przybliżonych.

Gdzie pojawiają się drzewa minimalne kosztów poza schematami wiringowymi

Drzewa minimalne kosztów są również rdzeniem pojedynczego-łączenia hierarchicznego grupowania: uruchamianie algorytmu i zatrzymywanie się tuż przed dodaniem k-1 najbardziej kosztownych krawędzi naturalnie dzieli graf na k klasterów, ponieważ usunięcie tych najbardziej kosztownych połączeń mostowych jest dokładnie tym, jak oddzielasz najluźniejsze połączenia. Drzewa minimalne kosztów są używane do przybliżania rozwiązań problemu sprzedawca, (drzewo minimalne kosztów daje udowodnione dolne ograniczenie dla optymalnego tournée, a podwojenie jego krawędzi daje spacerowalne tournée w czynniku dwóch od optymalnych dla instancji metrycznych), i pojawiają się w projektowaniu obwodów, analizie niezawodności sieci oraz segmentacji obrazów, gdzie grafy podobieństwa pikseli są przecinane wzdłuż ich najbardziej kosztownych krawędzi drzewa minimalnego kosztu, aby oddzielić regiony.

Frequently asked questions

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Minimum Spanning Tree i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.