Ich habe eine große Menge von Punkten (n & gt; 10000 an Zahl) in einem metrischen Raum (z. B. ausgerüstet mit Jaccard Abstand ). Ich möchte sie mit einem minimalen Spannbaum verbinden, indem ich die Metrik als Gewicht an den Kanten verwende.
Vielen Dank im Voraus!
Bearbeiten Sie für die Poster unten: Klassische Algorithmen zum Auffinden eines minimalen Spannbaums funktionieren hier nicht. Sie haben einen E-Faktor in ihrer Laufzeit, aber in meinem Fall E = n 2 , da ich tatsächlich den vollständigen Graphen betrachte. Ich habe auch nicht genug Speicher, um alle & 499995000 Kanten zu speichern.
Offenbar entsprechend: Es wird die Gewichtung der metrisch minimal aufspannenden Bäume in der sublinearen Zeit geschätzt kein deterministisches o (n ^ 2) (beachte: smallOh, das ist wahrscheinlich das, was du unter einem weniger als O (n ^ 2) vermuteten Algorithmus). Dieses Papier gibt auch einen sublinearen randomisierten Algorithmus für den metrischen Spannbaum mit minimalem Gewicht.
Sehen Sie sich auch dieses Papier an: Ein optimaler minimaler Spanning-Tree-Algorithmus , der einen optimalen Algorithmus liefert. Das Papier behauptet auch, dass die Komplexität des optimalen Algorithmus noch nicht bekannt ist!
Die Hinweise in der ersten Arbeit sollten hilfreich sein und das Papier ist wahrscheinlich das Wichtigste für Ihre Frage.
Ich hoffe, das hilft.
Als ich vor 3-4 Jahren ein sehr ähnliches Problem betrachtete, konnte ich in der von mir betrachteten Literatur keine ideale Lösung finden.
Der Trick, den ich denke, ist es, eine "kleine" Teilmenge von "wahrscheinlich guten" Kanten zu finden, auf der man dann einfach Kruskal laufen lassen kann. Im Allgemeinen ist es wahrscheinlich, dass viele MST-Kanten in der Menge von Kanten gefunden werden können, die jeden Knoten mit seinen nächsten Nachbarn verbinden, für einige kleine k . Diese Kanten können den Graphen nicht überspannen, aber wenn dies nicht der Fall ist, kann jede Komponente auf einen einzelnen Eckpunkt (zufällig ausgewählt) reduziert und der Prozess wiederholt werden. (Um eine bessere Genauigkeit zu erzielen, anstatt einen einzelnen Vertreter zu wählen, um der neue "Supervertex" zu werden, wählen Sie eine kleine Zahl r von Vertretern und in der nächsten Runde alle r ^ 2 Entfernungen zwischen 2 Supervertices, die Wahl des Minimums.)
k -Nearest-Neighbor-Algorithmen sind für den Fall, in dem Objekte als Vektoren in einem endlichdimensionalen euklidischen Raum dargestellt werden können, ziemlich gut untersucht. Wenn Sie also einen Weg finden, Ihre Objekte abzubilden bis dahin (zB mit multidimensional scaling ), dann hat man vielleicht Glück. Insbesondere ermöglicht die Zuordnung zu 2D die Berechnung eines Voronoi-Diagramms, und die MST-Kanten befinden sich immer zwischen benachbarten Flächen. Aber nach dem, was ich gelesen habe, führt dieser Ansatz nicht immer zu qualitativ guten Ergebnissen.
Andernfalls sind Clusteransätze möglicherweise hilfreich: Clustering großer Datensätze in beliebigen metrischen Bereichen ist eine der wenigen Arbeiten, die ich explizit mit Objekten befasse, die nicht notwendigerweise endlichdimensionale Vektoren in einem euklidischen Raum sind, und die die Möglichkeit von rechenintensiven Abstandsfunktionen berücksichtigt.
Tags und Links algorithm minimum-spanning-tree