Gegeben sind N Punkte (in 2D) mit x- und y-Koordinaten. Sie müssen einen Punkt P finden (in N gegebenen Punkten), so dass die Summe der Abstände von anderen (N - 1) Punkten zu P minimal ist.
für ex. N Punkte gegeben mit p1 (x1, y1), p2 (x2, y2) ...... pN (xN, yN). wir haben einen Punkt P zwischen p1, p2 .... PN gefunden, dessen Summe der Abstände von allen anderen Punkten minimal ist.
Ich habe einen Brute-Force-Ansatz gewählt, aber ich brauche einen besseren Ansatz. Ich habe es auch versucht, indem ich Median, Mittelwert usw. gefunden habe, aber es funktioniert nicht in allen Fällen.
Dann kam ich auf eine Idee, dass ich X als Eckpunkte eines Polygons behandeln und den Schwerpunkt dieses Polygons finden würde, und dann werde ich einen Punkt von Y wählen, der dem Schwerpunkt am nächsten liegt. Aber ich bin mir nicht sicher, ob der Schwerpunkt die Summe seiner Abstände zu den Eckpunkten des Vielecks minimiert, also bin ich mir nicht sicher, ob das ein guter Weg ist? Gibt es einen Algorithmus zur Lösung dieses Problems?
Wenn Ihre Punkte schön verteilt sind und wenn es so viele von ihnen gibt, dass die rohe Gewalt (Berechnen der Gesamtdistanz von jedem Punkt zu jedem anderen Punkt) unattraktiv ist, könnte die folgende Antwort Ihnen eine ausreichend gute Antwort geben. Mit "schön verteilt" meine ich (ungefähr) einheitlich oder (ungefähr) zufällig und ohne markierte Clusterbildung an mehreren Orten.
Erstellen Sie ein einheitliches k*k -Grid, wobei k eine ungerade ganze Zahl in Ihrem Space ist. Wenn Ihre Punkte gut verteilt sind, befindet sich der (wahrscheinlich) in der zentralen Zelle dieses Gitters. Für alle anderen Zellen im Raster zählen Sie die Anzahl der Punkte in jeder Zelle und approximieren Sie die durchschnittliche Position der Punkte in jeder Zelle (verwenden Sie entweder das Zellenzentrum oder berechnen Sie den durchschnittlichen (x,y) für Punkte in der Zelle).
Berechnen Sie für jeden Punkt in der Zentralzelle den Abstand zu jedem anderen Punkt in der Zentralzelle und den gewichteten Mittelabstand zu den Punkten in den anderen Zellen. Dies ist natürlich der Abstand vom Punkt zur "durchschnittlichen" Position der Punkte in den anderen Zellen, gewichtet mit der Anzahl der Punkte in den anderen Zellen.
Sie müssen mit der erhöhten Genauigkeit der höheren Werte für k gegen die erhöhte Rechenlast jonglieren und herausfinden, was am besten für Ihre Punkte funktioniert. Wenn die Verteilung der Punkte über die Zellen hinweg nicht einheitlich ist, ist dieser Ansatz möglicherweise nicht geeignet.
Diese Art von Ansatz wird in groß angelegten Simulationen sehr häufig verwendet, bei denen Punkte Eigenschaften wie Schwerkraft und Ladung aufweisen, die über Entfernungen hinweg funktionieren. Ob es Ihren Bedürfnissen entspricht, weiß ich nicht.
Der betrachtete Punkt ist bekannt als das geometrische Median
Der Schwerpunkt oder Massenmittelpunkt, der ähnlich wie der geometrische Median definiert wird, um die Summe der Quadrate der Abstände zu jeder Probe zu minimieren, kann durch eine einfache Formel gefunden werden - seine Koordinaten sind die Durchschnittswerte der Koordinaten der Stichproben eine solche Formel ist für den geometrischen Median nicht bekannt, und es wurde gezeigt, dass keine explizite Formel oder ein exakter Algorithmus, der nur arithmetische Operationen und k-te Wurzeln beinhaltet, im Allgemeinen existieren kann.
Tags und Links algorithm