Najszybszy algorytm minimum drzewo rozpinające

Question

http://en.wikipedia.org/wiki/Minimum_spanning_tree

Czekam na benchmarku moje minimum rozpinające algorytm drzewa przeciw najlepszym z najlepszych. Czy ktoś wie, gdzie mogę znaleźć implementację C++ tych algorytmów? Ja binged i googled i nic nie znalazłem. Jeśli te algorytmy są najlepsze, to na pewno musi być gdzieś implementacja C++?

Najszybszy minimum Spanning Tree algorytm do tej pory został opracowany przez David Karger, Philipa Klein i Robert Tarjan, który znalazł czas liniowy randomizowane algorytm oparty na kombinacji algorytm borůvki i odwrotnej -delete algorytm. [2] [3] Najszybszy, nieza-randomizowany algorytm, autorstwa Bernarda Chazelle, oparty jest na miękkim stercie o numerze , o przybliżonym priorytecie, . [4] [5] Jego czas działania wynosi O (m α (m, n)), gdzie m jest liczbą krawędzi , n jest liczbą wierzchołków, a α jest klasyczną funkcjonalną odwrotnością funkcji Ackermanna. Funkcja α rośnie bardzo wolno, więc dla wszystkich celów praktycznych może być uważana za stałą nie większą niż 4; tak więc algorytm Chazelle'a zajmuje bardzo blisko czasu liniowego. Jeśli grubości krawędzi są liczbami całkowitymi z ograniczoną długością bitową , wówczas znane są deterministyczne algorytmy o liniowym czasie trwania . [6] Niezależnie od tego, czy istnieje , algorytm deterministyczny o liniowym czas działania dla ogólnych mas to to wciąż otwarte pytanie. Jednak Seth Petie i Vijaya Ramachandran mają ustalili możliwie optymalny algorytm minimalnego drzewa opinającego, którego złożoność obliczeniowa jest nieznana. [7]

Już testuję algorytmy wykresu Boost C++.

Answer 1

Gdy strona Wikipedii mówi "najszybszy algorytm minimalnego drzewa opinającego", chodzi o algorytm o najniższych asymptotycznych granicach - w tym przypadku O (m α (m, n)), o m, n i α zdefiniowane tak, jak w cytowanym fragmencie. Mówiąc prościej, oznacza to, że dla bardzo dużych wartości wejściowych, długość czasu będzie zawsze ograniczona C * m * α (m, n), dla pewnej wartości C. Należy jednak pamiętać, że C może być bardzo duże - tj. , ten algorytm może być wolniejszy od innych, gdy zostanie zastosowany do mniejszych wartości wejściowych, mimo że jest szybszy niż inne w przypadku bardzo dużych wartości wejściowych.

Porównując asymptotyczne granice dwóch algorytmów, nie ma "testowania", aby zobaczyć, który jest szybszy - wystarczy udowodnić asymptotyczne granice każdego algorytmu i zobaczyć, który z nich jest niższy. („Asymptotic” odnosi się do zachowań jako wielkość wejściowa dąży do nieskończoności - i trudno uruchomić testy z nieskończonej wielkości wartości wejściowych.)

Należy jednak pamiętać, że istnieją przypadki, w których należy nie używają asymptotycznie najszybszy algorytm. Jeśli "C" jest bardzo duże, lepszym rozwiązaniem może być użycie prostszego algorytmu dla mniejszych wartości danych.

Zgaduję, że twój algorytm może poprawić się na C, ale nie na asymptotycznych granicach. Ale jeśli się mylę, powinieneś przesłać go do ACM!

Aby uzyskać więcej informacji, zobacz: http://en.wikipedia.org/wiki/Big_O_notation

Answer 2

www.dcc.uchile.cl/~raparede/publ/09algorIQS.pdf "na temat sortowania, stogi, a Minimum Spanning Trees", Gonzalo Navarro Rodrigo Paredes

przedstawia niektóre "najlepsze z najlepszych" wewnętrznych i zewnętrznych pomiarów pamięci i zawiera odniesienia do starszych implementacji .

zgłosić Oni # wejść/wyjść oraz czasu procesora w zależności od wielkości milimetrowym i opisują swoje przypadki testowe, tak więc w zasadzie można zrobić testy i porównania z publikowanych wykresach. Możesz użyć ich odnośnika Prim2 (kod od Petera Sandersa, który udostępnia wiele bezpłatnych kodów szybkiego dostępu), aby skalibrować swoich własnych pomiarów.