[HaBo]

RemoteC

Anzeige

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

GrafZahl

in welchem bezugssystem soll das geschehen? ein graph? eine einfache 2D ebene? von wievielen ausgangspunkten reden wir?

__________________

Code:

:(){ :|:& };:

Veritas Aequitas

RemoteC

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

GrafZahl

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 ...

__________________

Code:

:(){ :|:& };:

Veritas Aequitas

+++ATH0

Suchst du etwa nach dem Schwerpunkt geometrischer Flächen?

Nerdworld

Wenn ich das richtig verstanden habe, dann liegt es an der Menge der Punkte, ob das Problem überhaupt lösbar ist.

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:

benediktibk

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

ArnoNühm

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.

Scutus

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.

Tarantoga

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...

GrafZahl

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 ...

__________________

Code:

:(){ :|:& };:

Veritas Aequitas

Tarantoga

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...

GrafZahl

für X punkte hilft wohl nur distanzen berechnen und nach geringster distanz suchen ...

__________________

Code:

:(){ :|:& };:

Veritas Aequitas

ArnoNühm

Wenn ich den Ausgangspost richtig verstanden habe, wird ein Punkt im Raum und kein Knoten eines Graphen gesucht.

GrafZahl

naja ... raster den raum/die fläche ... die rasterpunkte sind die knoten des graphen, benachbarte rasterpunkte haben kanten zwischen den zugehörigen knoten ...

__________________

Code:

:(){ :|:& };:

Veritas Aequitas