Graphentheorie: nächsten Nachbarn finden, effizienter Algo?

[wry]

Hallo erstmal,

ich habe gerade ein Problem bzgl. Berechnung des nächsten Nachbarn für alle Knoten in einem Graphen.

Momentan mache ich das auf naive Art und Weise, d.h. jedes mal wenn ich einen neuen Knoten in den Graphen einfüge, prüfe ich für alle Knoten im Graphen ob der neue Knoten näher liegt als der vorherige nächste Knoten, sprich Komplexität O(n).

Gibt es hier ein effizienteres Verfahren?

Eine Idee die ich hatte, war, dass ich diese Prüfung nur für Knoten innerhalb eines bestimmten Bereichs, der um den neuen Knoten herum reicht, mache.
Konkret, hatte ich die Idee vom neuen Knoten aus in alle 4 Himmelsrichtungen zu gehn (x/y Koordinaten vergleich in einem sortierten Array) und den nächstgelegen Knoten zu finden, dann denjenigen aussuchen, der am weitesten weg ist und diese Distanz als Bereichs-quadrat um den neuen Knoten aufspannen und den check nur für alle Punkte innerhalb dieses Quadrats machen.
Habs am Papier versucht, aber ich glaube, das mit den 4 Himmelsrichtungen geht gar nicht, nur auf Basis von Koordinatenvergleichen im Array (unter On).

Kennt hier vielleicht jemand ein Verfahren?

Hier auch noch ein Bild, damit sich jeder was Vorstellen kann :biggrin:
http://h9.abload.de/img/problem8aawz.jpg

[MaxistXXL]

Hmm,
so richtig verstanden habe ich nicht, was du möchtest. Du sprichst von Graphen, malst dann aber Punkte in ein Diagramm ein. Wenn du in einen Graphen Knoten hinzufügst, kommst du um die Überprüfung aller Nachbarn nicht herum.
Meine Kristallkugel verrät mir aber, dass du Octrees suchst. Eine konzeptionelle Erklärung liefert http://de.wikipedia.org/wiki/Octree
Hilft dir das weiter?

[Berni]

Wenn es nur um die Optimierung von Inserts geht: Du weißt ja den Abstand, den ein Knoten momentan hat. In einem Kreis um diesen Bereich musst du also quasi eine "Überwachung" hinterlegen. Wenn in diesem Bereich ein neuer Knoten erzeugt wird, dann muss nur der für diesen Bereich hinterlegte Knoten geprüft werden (oder ggf. auch mehrere aber eben bei Weitem nicht alle). Um die Bereiche abzubilden kann man das Koordinatensystem als Array hinterlegen. Je nach Größe des Koordinatensystems sollte man das Ganze dann nicht auf Einzelkoordinatenbasis machen sondern auf größere Bereiche von z.B. 10x10 Pixeln anpassen um RAM zu sparen (ein Faktor für die Performance ist natürlich auch das Aktualisieren der Überwachungsbereiche).

[MaxistXXL]

Und was macht er, wenn ein Knoten sehr weit entfernt von allen anderen Knoten plaziert wird? Außerdem müsste trotzdem noch für jeden Bereich der Überwachung geprüft werden, ob der Knoten darin plaziert wurde. Im Endeffekt wäre nichts gewonnen.

[Trap]

Ist wie sehr oft beim Suchen: Suchbaum oder Hashing.

[Gast]

Voronoi Diagramm

[MaxistXXL]

Auch auf die Gefahr hin, mich unbeliebt zu machen, aber auch diese Vorschläge sind unbrauchbar...
Ist wie sehr oft beim Suchen: Suchbaum oder Hashing.
Das ist viel viel zu allgemein. Klar, auch ein Octree oder Quadtree ist ein Suchbaum, aber normale Suchbäume eigenen sich gerade nicht, da hier die Entfernung von 2 Werten abhängt, normalerweise aber nur nach einem Wert verzweigt wird. Bis er sich da eine funktionelle Adaption ausgedacht hat, hat er den Octree auch schon implementiert.
Hashing ist erst recht nicht zu gebrauchen. Damit findet man Werte von Schlüsseln, die man kennt, in konstanter Zeit. Was soll denn hier gehasht werden, und wie kann er aus einem gegebenen Punkt "(x,y)" den Schlüssel berechnen.

Voronoi Diagramm
Das klingt nicht schlecht, allerdings müssten die bei jedem Knoten aktualisiert werden. Es scheint (Wikipedia), dass dies nicht schneller geht, als alle Punkte auf ihre Entfernung hin zu testen. Ein Quadtree kann hingegen sehr leicht aktualisiert werden.

Ansonsten ist die Frage, ob es nicht ausreicht, erst alle Punkte einzulesen, und dann den minimalen Spannbaum des vollen Graphen zu berechnen. Das geht sehr schnell.

[pest]

Die Knoten eines Graphen haben keine "Abstände" :frown:

[Gast]

Komplexität O(n).[/URL]

Wie kommt man denn auf so etwas?

[wry]

Danke euch für die ganzen Vorschläge! :smile:

Über Suchbäume/Trees hatte ich noch gar nicht nachgedacht, da könnte sich vielleicht was machen lassen. Ich werde mir das mal durch den Kopf gehen lassen.

Das mit dem Vornoi Diagramm fand ich sehr interessant, aber ich denke das selbe wie MaxistXXL, der Algo zur Berechnung des Diagramms hat schon min. O(n), wenn ich das recht verstehe. Das von Berni klingt auch gut, aber ich glaube, ich kann das gegenwärtig gar nicht so umsetzten, dass es schneller laufen würde als der naive Versuch.

@Gast
O(n) deshalb, weil für jeden neuen Knoten den ich einfüge, ich für alle Knoten im Graphen (=n) prüfe, ob der neue Knoten näher ist als der (vorige) nächste Nachbar des zu überprüfenden Knotens im Graphen. Ich hoffe das passt so, ich bin leider keine große mathematische Leuchte, wie das traurige Gesicht von Pest hier schon auf subtile Art und Weise verrät :freak:

[DocEW]

Vielleicht hilft das hier?

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

[wry]

Super, danke vielmals DocEW!
Das bringt etwas mehr Klarheit in die Sache.