Ich möchte meinen minimalen Spanning-Tree-Algorithmus mit den Besten der Besten vergleichen. Weiß jemand, wo ich eine C ++ - Implementierung dieser Algorithmen finden kann? Ich habe geangelt und gegoogelt und nichts gefunden. Wenn diese Algorithmen die besten sind, muss es irgendwo eine C ++ - Implementierung geben?
Der schnellste minimale Spannbaum Algorithmus bis heute wurde von entwickelt David Karger, Philip Klein und Robert Tarjan, der eine lineare Zeit gefunden hat randomisierter Algorithmus basierend auf a Kombination von Borůvkas Algorithmus und der Reverse-Delete-Algorithmus. [2] [3] Der schnellste nicht-randomisierte Algorithmus, von Bernard Chazelle, basiert auf der weicher Haufen, eine ungefähre Priorität Warteschlange. [4] [5] Seine Laufzeit ist O (m α (m, n)), wobei m die Anzahl von ist Kanten, n ist die Anzahl der Ecken und α ist das klassische funktionale Inverse der Ackermann-Funktion. Das Die Funktion α wächst extrem langsam das kann es für alle praktischen Zwecke sein als Konstante betrachtet werden, nicht größer als 4; also Chazelles Algorithmus kommt der linearen Zeit sehr nahe. Ob die Kantengewichte sind ganze Zahlen mit a begrenzte Bitlänge, dann deterministisch Algorithmen sind mit linearen bekannt Laufzeit. [6] Ob es existiert ein deterministischer Algorithmus mit linearem Laufzeit für allgemeine Gewichte ist immer noch eine offene Frage. Aber Seth Petie und Vijaya Ramachandran haben eine nachweisbar optimale deterministische gefunden minimum spanning tree Algorithmus, der Rechenkomplexität von denen ist unbekannt. [7]
Ich habe bereits gegen die Grafikalgorithmen von Boost C ++ getestet.
Wenn die Wikipedia-Seite sagt "der schnellste minimale Spanning-Tree-Algorithmus", was sie meinen, ist der Algorithmus mit den niedrigsten asymptotischen Grenzen - in diesem Fall O (m α (m, n)), mit m, n, und α definiert wie in dem Zitat, das Sie eingefügt haben. Einfach gesagt, bedeutet dies, dass für sehr große Eingabewerte die Menge an Zeit immer durch C * m * α (m, n) begrenzt ist, für einen Wert von C. Aber beachte, dass C sehr groß sein kann - d , dieser Algorithmus ist möglicherweise langsamer als andere, wenn er auf kleinere Eingabewerte angewendet wird, obwohl er für sehr große Eingabewerte schneller ist als andere.
Beim Vergleich der asymptotischen Grenzen zweier Algorithmen gibt es kein "Testen", um zu sehen, welches schneller ist - Sie beweisen einfach die asymptotischen Grenzen jedes Algorithmus und sehen, welche niedriger ist. ("Asymptotisch" bezieht sich auf das Verhalten, wenn die Eingabegröße ins Unendliche geht - und es ist schwierig, Tests mit unendlich großen Eingabewerten auszuführen.)
Beachten Sie jedoch, dass es Fälle gibt, in denen Sie nicht den asymptotisch schnellsten Algorithmus verwenden sollten. Wenn das "C" sehr groß ist, sollten Sie einen einfacheren Algorithmus für kleinere Datenwerte verwenden.
Ich schätze, dass Ihr Algorithmus das C verbessern kann, aber nicht die asymptotischen Grenzen. Aber wenn ich falsch liege, dann solltest du es bei ACM einreichen!
Weitere Informationen finden Sie unter Ссылка
www.dcc.uchile.cl/~raparede/publ/09algorIQS.pdf "Bei Sortierung, Heaps und Minimum Spanning Trees", Gonzalo Navarro und Rodrigo Paredes
präsentiert einige "Besten der Besten" in-core und extern Speichermessungen und gibt Hinweise auf ältere Implementierungen.
Sie melden die Anzahl der E / As und die CPU-Zeit in Abhängigkeit von Graphgröße, und beschreiben ihre Testfälle gut, also im Prinzip könnten Sie die Tests machen und vergleichen mit ihre veröffentlichten Graphen. Sie könnten ihre Prim2 verwenden Referenz (Code von Peter Sanders, der viele macht seiner schnellen Codes frei verfügbar) zu kalibrieren deine eigenen Maße.
Tags und Links c++ minimum-spanning-tree