geringste Gesamtstrecke für einen Treffpunkt berechnen

R

RemoteC

0
Hallo!

Gibt es eine Möglichkeit bzw. einen Algorithmus den Ort eines Treffpunktes zu berechnen der so günstig liegt, dass die Gesamtstrecke von allen Ausgangspunkten am Geringsten ist?

Gehen tut das sicher irgendwie, nur wie? Meine erste Überlegung war über Trigonometrie aber da steh ich irgendwie an :-|

lg
 
in welchem bezugssystem soll das geschehen? ein graph? eine einfache 2D ebene? von wievielen ausgangspunkten reden wir?
 
2D-Koordinatensystem ... hab jetzt etwas weiter überlegt und habe mal mit dem Mittelwert der Koordinaten der einzelnen Ausgangspunkte gerechnet ... die Frage ist nur ob der Punkt der da rauskommt der Punkt ist den ich suche.

Anzahl der Ausgangspunkte sollten ja egal sein :confused:
 
prinzipiell suchst du das globale minimum einer funktion f(x,y) die deffiniert ist als summe der strecken aller ausgangspunkte zu (x,y) ... wobei jeder summand die form sqrt((xi-x)²+(yi-y)²) hat

um das ganze nun rechnerisch zu belegen wirst du dich hier munter fröhlich der differentialrechnung bedienen müssen ...

ich hab da heute nacht keinen kopf mehr für ...


aber es klingt irgendwie logisch, dass der koordinaten-mittelwert die kürzesten strecken liefert ...
 
Wenn ich das richtig verstanden habe, dann liegt es an der Menge der Punkte, ob das Problem überhaupt lösbar ist. :D

Schau dir mal das Problem des Handlungsreisenden an - damit, und mit dem verbundenen P/NP-Problem habe ich mich lange Zeit beschäftigt.

Ansonsten hilft, wie schon genannt, Satz d. Pythagoras:


png.latex
 
Ich habe die Vermutung, dass der Schwerpunkt nicht die Lösung des Problems ist. Die Verbindung der Eckpunkte zum Schwerpunkt über die Schwerelinien bildet wahrscheinlich nicht die kleinste Summe der Verbindungen. Das läuft auf eine Extremwertrechnung hinaus, nur fehlt mir noch eine Nebenbedingung. :-|

mfg benediktibk
 
hm hatte zuerst auch erst gedacht, es sei der mittelwert, hatte dann aber schwierigkeiten das zu beweisen.

hab danach kurz gegoogled und festgestellt, dass man das auch als Standortproblem oder Steiner-Weber-Problem bezeichnet und es dafür offensichtlich keine analytische lösung gibt. stattdessen wird die lösung mit optimierungsalgorithmen z.B. Newtonverfahren gesucht.
 
du könntest den Greedy-Algorithmus namens Dijkstras Algorithmus verwenden...dieser berechnet von einem Ausgangspunkt und den Gewichtungen der Strecken (z.B. Länge, oder Durchsatz) die kürzesten Pfade....

was aber wohl interessanter wäre, wäre der Floyd-Warshall-Algorithmus - dieser scheint zwar in kubischer Zeit zu laufen, dürfte jedoch dem Problem "Kürzeste Pfade für alle Knotenpaare" am meisten entsprechen.

Wenn du dich noch etwas gedulden kannst: Ich schreibe gerade an einem Skript für grundlegende Algorithmen, darunter eben auch Strecken im 2D.
 
In Frage käme übrigens auch der A*-Algorithmus, über den ich gerade in einem Fachbuch gestolpert bin, ein informierter Suchalgorithmus zur Berechnung der kürzesten Strecke zwischen zwei Knoten in einem Graphen. Im Gegensatz zu einem "gewöhnlichen", uninformierten Algorithmus, verfügt A* über eine heuristische Methode um den Suchvorgang zu optimieren, in dem zuerst die vielversprechendsten Routen untersucht werden. Der Algorithmus findet immer die optimale Lösung...
 
das problem ist ja, dass er X startpunkte hat, und nicht strecken von A nach B sucht, sondern den punkt auf der karte (nicht zwangsweise einen der startpunkte) der die geringste gesammt distanz zu allen startpunkten aufweißt ...
 
Aber der Punkt C, der auf der optimalen, also kürzesten, Strecke zwischen A und B liegt und von beiden Startpunkten exakt gleich weit entfernt ist, sollte der von RemoteC gesuchte Punkt sein, oder?
Das mit den X Ausgangspunkten ist natürlich ein Problem, da muß man noch ein bisschen basteln...;)

Der Algorithmus ist mir auch nur aufgefallen, weil er zu den Neuerungen in der Neuauflage eines Buchs über Algorithmen & Datenstrukturen, das ich mir heute gegönnt habe, gehört. Beim lesen der Kurzbeschreibung über den Algorithmus fiel mir irgendwie sofort dieser Thread ein...:D
 
naja ... raster den raum/die fläche ... die rasterpunkte sind die knoten des graphen, benachbarte rasterpunkte haben kanten zwischen den zugehörigen knoten ...
 
GrafZahl hat gesagt.:
für X punkte hilft wohl nur distanzen berechnen und nach geringster distanz suchen ...
Zum Vergrößern anklicken....
Klingt logisch.

ArnoNühm hat gesagt.:
Wenn ich den Ausgangspost richtig verstanden habe, wird ein Punkt im Raum und kein Knoten eines Graphen gesucht.
Zum Vergrößern anklicken....
Wie GrafZahl ja auch schon sagte, ist das im Grunde das gleiche - benutzt wird der A*-Algorithmus z. B. in Navigationssystemen, um die küzeste Route zwischen zwei Orten zu finden...;)
 
@Tarantoga
Das geht nur für einen Graph, also zum Beispiel mit den Openstreetmap Kartendaten oder so. Nicht für ein Koordinatensystem.
In einem Koordinatensystem gibt es unendlich mögliche Punkte (Relle Zahlen als Koordinaten). Wenn man die möglichen Koordinaten so beschränkt, dass es endlich viele mögliche Punkte werden kann man einen Graph dazu basteln.

Der kürzeste Weg zwischen zwei Punkten (x1, y1), (x2, y2) in einem 2-Dimensionalem kartesischem Koordinatensystem ist immer Wurzel((x1-x2)² + (y1-y2)²)

Formal sieht das Problem dann so aus: gegebene sind Punkte (x1, y2) ... (xn, yn) und gesucht ist ein Mittelpunkt (xm, ym), so dass die Funktion
f(xm, ym) = Wurzen((x1-xm)²+(y1-ym)²) + ... + Wurzen((xn-xm)²+(yn-ym)²)
minimal ist.

Da kann man sich dann den Regeln der Analysis bedienen und das lösen :P

In einem ungerichtetem Graphen könnte man das wie folgt lösen:
Man berechnet für n Knoten mit Dijkstra einen kürzesten Wege Baum. Dijkstra hat eine Laufzeit von O(e * log(v)) bei e Kanten und v Knoten. Also O(n * e * log(v)). Dann muss man noch für v Knoten die kürzesten Wege addieren und den kürzesten insgesammt auswählen O(v*n) was eine Gesammtlaufzeit von O(v*n + n * e * log(v)) macht.

Ich hoffe das stimmt jetzt so wie ich mir das gedacht habe, aber eigentlich sollte das funktionieren ...
 
Ok nehmen wir nen eindimensionalen Vektorraum über R und rastern ein beliebig kleines Intervall, sodass wir alle Punkte erfassen ... sagst du mir bescheid, wenn du fertig bist? ;)
 
raster die karte mit punkten der ausdehnung 1*1 ... hast du den rasterpunkt ermittelt, der als günstigster ort in frage kommt, kannst du wiederum diesen rasterpunkt rastern, und das spielchen itterativ fortsetzen bis dir die präzision ausreicht ... oder du moos ansetzt ... je nach dem ...



wenn du es ausrechnen willst, siehe post 4

stell für die startpunkte die distanzfunktion auf, bilde die erste ableitung nach x und die erste ableitung nach y ... setze beide je gleich 0, und löse die gleichungssysteme ... danach hast du eine überschaubare anzahl an kandidaten, für die du dann die distanz-summe berechnen kannst und die kleinste wählst ...
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben