Wie macht man das am besten? Gegeben seinen n Adressen von Wohnungen, ausgedrückt durch ihre GPS-Koordinaten. Gesucht ist der Punkt, der im Mittel allen Adressen am nächsten liegt. Also wenn man alle Entfernungen (Luftlinie, oder als Kür noch Straßenwege) vom Mittelpunkt zu Adresse 1 bis n addiert, das Minimum rauskommt. Wer hat eine praktische Idee?
https://de.wikipedia.org/wiki/Geometrischer_Schwerpunkt vielleicht findet sich unter dem Begriff etwas passendes? Für kleinräumige Betrachtung reicht sicher eine ebene zweidimensionale Annäherung.
Rainer U. schrieb: > GPS-Koordinaten. > > Gesucht ist der Punkt, der im Mittel... Luftlinie,....Adresse 1 bis n addiert, das Minimum > rauskommt. > > Wer hat eine praktische Idee? https://de.wikipedia.org/wiki/Geometrischer_Schwerpunkt#Geometrischer_Schwerpunkt_endlich_vieler_Punkte_im_reellen_Vektorraum Trivial! Rainer U. schrieb: > als Kür noch > Straßenwege) Wohl so komplex wie "Salesman-Problem"
Hallo, ich habe Zweifel, ob der Schwerpunkt mehrerer gleichgewichteter Punkte auch der Ort ist, an dem die Summe der Distanzen minimal ist. Ein Gegenbeispiel: Drei Punkte auf einer Linie bei x=0, x=1 und x=10. Die minimale Entfernungssumme hat man bei x=1 mit Summe 10, der Schwerpunkt liegt bei x=11/3. Da ist die Entfernungssumme aber 38/3, also größer als 10. Ich befürchte, für die Lösung muß man eine Iteration laufen lassen, um sich dem gesuchten Punkt immer mehr anzunähern. Die Summe der Differenzvektoren von jedem Punkt zu dem gewählten Startpunkt gibt Anhaltspunkte dafür, in welche Richtung und wie weit man den Startpunkt für den nächsten Schritt bewegen müßte. Der Schwerpunkt ist nicht immer richtig. Gruß
Richtig, selbst ohne Straßen-Routen ist das eine Abwandlung des Traveling-Salesman problems und damit "NP-Hart". https://de.wikipedia.org/wiki/Problem_des_Handlungsreisenden D.h. es ist (bislang) nicht möglich die exakte Lösung zu errechnen, ohne alle möglichen Varianten einzeln zu berücksichtigen. Wenn du doch einen Weg Findest, bekommst du von einem US Institut 1 Mio $ da es eines der 7 Millenium Probleme ist: https://de.wikipedia.org/wiki/Millennium-Probleme (die Lösung würde zugleich das P-NP Klassifizeirungsproblem lösen, da die NP Klasse dann nicht mehr existent wäre) In der Praxis wird von zufallsbasiertem Brute-Force alles bis zu neuronalen Netzen auf solche Probleme los gelassen. Ganz wage erinnere ich mich auch an einen annähernden Algorithmus in der Schule, ist aber schon zu lang her... Irgendwas mit "lokale Minima suchen". EDIT: Trivial würde ich das Areal in ein Gitter einteilen wo jede Zelle die Größe hat von, sagen wir mal 1/100stel der Größten Distanz zwischen zwei Punkten (jeweils separat in X und in Y Richtung). Das ergibt ein Areal von 100x100 Zellen in dem sich der optimale Punkt befinden muss. Darauf kannst du einfach bruteforce mäßig losrechnen. Also die Summe der Distanzen für jede Gitterzelle berechnen. Die Mitte der optimalste Zelle ist dann sicherlich ein guter Näherungswert. EDIT: Das setzt vorraus dass die Punkte halbwegs gleichmäßig verteilt sind. Ein extremer Ausreisser würde die Zelle sehr stark strecken.
Christoph db1uq K. schrieb: > https://de.wikipedia.org/wiki/Geometrischer_Schwerpunkt > vielleicht findet sich unter dem Begriff etwas passendes? > Für kleinräumige Betrachtung reicht sicher eine ebene zweidimensionale > Annäherung. Hast du was gefunden? Wollte auch von Wiki dir den Link schicken
Antwort schreiben
Bitte melde dich an, um einen Beitrag zu schreiben.