Gegeben:
-Menge von festen Vektoren A mit Dimension d, d so zwischen 16 und 60
-Ein beliebiger Vektor v mit Dimension d

Gesucht:
-Vector aus A mit dem kleinsten euklidischen Abstand zu v

Ich habe schon mit KD-Trees herumexperimentiert, jedoch versagen diese bei höheren Dimension, so dass alle Baumknoten besucht werden und das ganze noch langsamer wird als einfach alle Vektoren abzusuchen. Kennt jemand ein effizientes Verfahren?

Sortier die festen Vektoren im Speicher nach dem Abstand vom Ursprung und baue danach einen binärbaum auf.

Tue das gleiche noch einmal für 3 weitere Punkte (die eine Ebene aufspannen).

Anschließend musst Du nur für v den euklidischen Abstand zu diesen 3 Punkten bestimmen und dann in den 3 Binärbäumen die Knoten suchen, die den geringsten Abstand haben. Wenn die Antwort mehrdeutig ist, berechnest Du von diesen Knoten nach V den Abstand und wählst den kürzesten.

Scheint zwar erstmal viel Aufwand, im Idealfall hast du aber nur 12 statt 16 Abfragen, im schlechtesten 16 (an deiner unteren Grenze) bzw. 18\21 Abfragen an deiner oberen Grenze.

(So würd ich das machen, keine Garantie, ob's wirklich so funzt).

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

Hmm, hast du dir das grad ausgedacht? Ich sehe da jetzt überhaupt keinen Ansatz, wie das das NNP effizient lösen soll.

Hallo,

Deine Vektoren sollen wohl beliebige Strecken in einem n-dimensionalen Raum sein.
Ich wuerde die Vektoren als Geraden betrachten(Punkt-Richtungsform ist ja gegeben) und deren Abstaende bestimmen.
Vielleicht sollte man zur Einschraenkung der Rechnerei zuvor aus allen Abstaenden der mittleren Punkte der Vektoren zum mittleren Punkt von v den kleinsten bestimmen.(Dieser ist ein >echter< Abstand)
(n - Rechnungen * dimensionen sqr und summe ist ja schnell die Wurzel ist vollkommen unnoetig , man kann ja auch Abstandsquadrate vergleichen).
Alle Vektoren deren Geradenabstand zu v groesser als kleinster realer Abstand bisher brauchen nicht weiter untersucht werden.
Falls der Abstand kleiner ist eben testen, ob der Punkt des kleinten Abstandes jeweils auf den Vektoren liegt.
Liegt dieser Punkt auf beiden-> neuer kleinster Abstand.
Liegt er auf einem dann Abstaende zu den Endpunkten des anderen bestimmen.
Sonst die Abstaende zu allen Endpunkten bestimmen und Minimum waehlen.
..Falls kleiner als bisher dann neuer kleinster Abstand.

Ich weiss aber nicht, wieviel Rechenaufwand die Bestimmung des Geradenabstandes in n-Dimensionen ist.

Gruss Horst

Aeeh ... ich verstehe jetzt nicht ganz, was du eigentlich vorschlägst, aber Vektoren sind keine Strecken, sondern eigentlich nur Punkte. Diese als Geraden zu betrachten geht schonmal garnicht, es sei denn, sie gehen alle durch den Ursprung, und dann ist der Abstand eh Null. Nach einem Algorithmus, der alle Vektoren beim Suchen des NN abklappern muss, suche ich jetzt auch nicht.

das ist so auch nicht richtig, ein vektor kann nicht durch den ursprung gehen, ein vektor ist dimensional unabhängig. man kann einem vektor jedoch einen punkt direkt zuordnen (ortsvektor)

Wer hat denn behauptet, dass ein Vektor durch den Ursprung geht?

Zitat:

Aeeh ... ich verstehe jetzt nicht ganz, was du eigentlich vorschlägst, aber Vektoren sind keine Strecken, sondern eigentlich nur Punkte. Diese als Geraden zu betrachten geht schonmal garnicht, es sei denn, sie gehen alle durch den Ursprung,

das sie bezieht sich eindeutig auf vektoren und vektoren können net durchn ursprung gehen

Nein, das sollte heissen, dass man eine Gerade, welche durch den Ursprung geht, durch einen einzelnen Vektor beschreiben kann. Aber das hat ja jetzt nichts mit dem Problem zu tun. Ich werde hier wohl auch keine Lösung erhalten, da nichtmal das Grundproblem verstanden wird.

Hallo,

ich hatte nach KD-tree's gesucht und habe dieses gesehen:
de.wikipedia.org/wik...nary_Space_Partition
und da sind nun einmal Strecken (langen Vektoren???) betrachtet worden.

Du musst immer n-1 Vergleiche machen , das ist wie bei sortieren. um >den< kleinsten zu finden , musst Du schon n -1 Vergleiche machen, bei n-2 weisst du es immer noch nicht genau.

Das ist kein nearest neighbour Problem, Du gibst v ja vor.
Beim NNP wuerdest Du t,u aus A suchen, die sich am naechsten sind.

Gruss Horst

"The nearest neighbor problem is defined as follows: given a set S of n points in V^n, construct a data structure that, given any q e V^n, quickly finds the point p e S that has the smallest distance to q."

Der Suchpunkt (Query Point) muss nicht Teil der vorgegebenen Punktmenge sein.

Hallo,

warum schreibst Du es nicht gleich so?

Gruss Horst

Ja, mein Vorschlag ist grad ausgedacht.

Und zur Technik: Ich berechne die euklidischen Abstände der Punkte einfach im Voraus und kann damit anhand dieser Vorberechnung eine Filterung vornehmen, die die Menge in Fragekommender Punkte reduziert.

Beschreibung, wie man das bauen könnte, hab ich oben bereits geschrieben. Sollten da Probleme auftreten, einfach fragen.

P.S.: Die 3 Stützvektoren für die Berechnung sind eigentlich frei wählbar, sollten aber so gewählt werden, dass Berechnungen mit ihnen möglichst schnell vorgenommen werden können.

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

@BenBe: Also den Raum durch Ebenen zu Unterteilen hört sich nach BSP-Tree an. Leider ist es so, dass solche Verfahren bei steigender Dimension nicht mehr funktionieren und gegen O(n) konvergieren, also nicht besser als einfaches Brute-Force-Abklappern sind.