Dokładniejsza analiza zmodyfikowanego algorytmu Borůvka


11

Algorytm Borůvki jest jednym ze standardowych algorytmów do obliczania minimalnego drzewa opinającego dla wykresu , z .G=(V,E)|V|=n,|E|=m

Pseudo-kod to:

MST T = empty tree
Begin with each vertex as a component
While number of components > 1
    For each component c
       let e = minimum edge out of component c
       if e is not in T
           add e to T  //merging the two components connected by e

Każdą iterację pętli zewnętrznej nazywamy rundą. W każdej rundzie wewnętrzna pętla zmniejsza liczbę elementów o co najmniej połowę. Dlatego jest co najwyżej rund . W każdej rundzie wewnętrzna pętla patrzy na każdą krawędź maksymalnie dwa razy (raz z każdego elementu). Dlatego czas działania wynosi co najwyżej .O(logn)O(mlogn)

Załóżmy teraz, że po każdej rundzie usuwamy wszystkie krawędzie, które łączą tylko wierzchołki w tym samym komponencie, a także usuwamy zduplikowane krawędzie między komponentami, tak aby wewnętrzna pętla patrzyła tylko na pewną liczbę krawędzi m '<m, które są krawędziami o minimalnej masie, które połącz dwa wcześniej odłączone komponenty.

Jak ta optymalizacja wpływa na czas działania?

Gdybyśmy w jakiś sposób wiedzieli, że w każdej rundzie zmniejszyłoby liczbę krawędzi o połowę, wówczas czas pracy zostałby znacznie skrócony: .T(m)=T(m/2)+O(m)=O(m)

Jednak podczas gdy optymalizacja radykalnie zmniejszy liczbę badanych krawędzi (tylko 1 krawędź do ostatniej rundy i co najwyżej # komponentów wybiera 2 ogólnie), nie jest jasne, w jaki sposób / jeśli możemy wykorzystać ten fakt do zaostrzenia analizy czasu wykonywania.


W najgorszym przypadku (łańcuch) usunąłbyś dokładnie jedną krawędź na rundę, więc nie możesz użyć tego faktu do poprawy granic dla ogólnego wykresu. Można jednak rozważyć np. Tylko pełne wykresy.
Xodarap,

@ Xodarap, jeśli jest prostą ścieżką (czy to rozumiesz przez łańcuch?), To w pierwszej rundzie wybierasz co najmniej połowę krawędzi. Krawędzie te są usuwane z kolejnych rund. G
Joe

Zauważ, że możesz użyć jednej z wysoce zoptymalizowanych struktur znajdowania związków, aby ulepszyć ten algorytm.
Raphael

Odpowiedzi:


5

Możliwe jest tworzenie przypadków testowych dla ogólnych wykresów, w których krok twojego Borůvki nie zmniejszyłby o połowę liczby krawędzi na każdym kroku, nawet jeśli zmniejszyłby o połowę liczbę wierzchołków. Interesującą uwagą jest to, że sugerowana optymalizacja działa dla grafów płaskich. Jest tak, ponieważ w przypadku wykresów płaskich i, e . I generalnie prowadzi to do przyspieszenia klasy małych zamkniętych rodzin grafów.| E | = O ( | V | )|E|3|V|6|E|=O(|V|)

Odniesienie:

  • Praca magisterska, Claude Anderson (na stronie 100 opisano najgorszy przypadek wprowadzenia algorytmu Borůvki). [połączyć]

  • „Dwa liniowe algorytmy czasowe dla MST na mniejszych klasach zamkniętych grafów”. Archivum mathematicum 40 (3): 315–320, 2004. [link]

Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.