Kürzeste Strecke vieler Punkte

Neue Frage »

Tripplemint Auf diesen Beitrag antworten »
Kürzeste Strecke vieler Punkte
Meine Frage:
Folgendes Problem:
Eine Familie die über ganz Deutschland verteilt ist möchte sich Treffen. Sie fahren alle Auto. Sie wollen dass der Treffpunkt an dem Ort ist der die kürzeste Gesamtstrecke für alle Fahrer bedeutet.
Gibt es eine Formel um den perfekten Treffpunkt T auf einem Koordinatensystem zu finden? Beispielhafte Startpunkte: ein Auto startet in Hamburg(05/12), eines in Berlin(09/10), eines in Leipzig(08/08)und drei Autos starten in Dortmund(03/09).
Die Formel sollte idealer Weise leicht durch weitere Standorte mit Koordinaten ergänzbar sein.

Meine Ideen:
Einfach nur eine Geometrische Fläche zu bestimmen und den Mittelpunkt diesee Fläche zu bestimmen ist nicht die Lösung, da die drei Autos aus Dortmund den perfekten Treffpunkt in ihre Richtung verschieben.
Meine Grundidee war dass es ja die Formel zur Bestimmung der Strecke zwischen zwei Punkten gibt L = Wurzel aus Delta x + Delta y
Die Summe aller L zwischen dem Punkt T und den Startpunkten ist L gesamt, welches minimal sein soll.
Ich dachte dass man dann L gesamt gleich y in einem extra Koordinatensystem setzen könnte, aber da L gesamt in Abhängigkeit zu Tx und Ty steht wäre das Koordinatensystem nicht nur zweidimensional sondern dreidimensional. Und jetzt bin ich mit meinem Latein am Ende. Die Schule ist zu lange her ^^
005 Auf diesen Beitrag antworten »
RE: Kürzeste Strecke vieler Punkte
Das Problem ist komplzierter, als man denken wuerde. Ein netter Ueberblick findet sich in "Ulrich Eckhardt, Kürzeste Wege und optimale Standorte –- Von Industriestandorten, Bomben und Seifenblasen". Das Paper findest Du als PDF im Netz.

Ich weiss nicht recht, was "einfach eine geometrische Fläche bestimmen und den Mittelpunkt dieser Fläche bestimmen" heissen soll, aber der Schwerpunkt ist so oder so nicht der gesuchte Punkt.
mYthos Auf diesen Beitrag antworten »

Man kann sich die Ausgangspunkte auf der Peripherie eines Kreises befindlich denken und von diesem Kreis mittels quadratischer Regression den Mittelpunkt bestimmen.

Der Treffpunkt wird dann bei ungefähr (6 / 9.5) liegen, die Distanz zu diesem bei 3 Längeneinheiten.

Die Sache wurde in Excel mittels des Solvers (Minimum der Summe der Fehlerquadrate) berechnet.
Der Aufwand dabei ist vergleichsweise gering.

[attach]47444[/attach]

mY+
005 Auf diesen Beitrag antworten »

Ich behaupte einfach mal weiter, dass das nicht so einfach ist. smile

Die Weiszfeld-Methode aus dem genannten Paper/Vortrag ergibt fuer gleiches Gewicht aller vier Staedte den Treffpunkt (6.78|9.63). Wenn man Dortmund das Gewicht 3 gibt, kommt (3|9), also Dortmund, raus. Der Mathematica-Befehl SpatialMedian sieht das auch so:

SpatialMedian[{{5, 12}, {9, 10}, {8, 8}, {3, 9}}]
-> {6.77778, 9.62963}

SpatialMedian[{{5, 12}, {9, 10}, {8, 8}, {3, 9}, {3, 9}, {3, 9}}]
-> {3., 9.}
HAL 9000 Auf diesen Beitrag antworten »

Eine kleine Anmerkung zur Textstory:

Die Vorstellung, man könnte jeden beliebigen Ort auf der Karte auf geradem Weg mit dem Auto anfahren, bringt einen schon ein wenig zum schmunzeln. Augenzwinkern

Ok, schreiben wir es um in das Treffen einer Milliardärsfamilie, und sie reisen per Helikopter an. smile
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »