geringste Gesamtstrecke für einen Treffpunkt berechnen

GrafZahl hat gesagt.:
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 ...
Zum Vergrößern anklicken....

Die Idee hatte ich auch schon. Problem ist, dass die Ableitung nach x ne Funktion abhängig von y ist. Ich kann also alle möglichen Nullstellenpaare (xN,yN) betrachten. Problem ist, dass nicht zwingend in einem dieser Punkte die Ableitung in alle Richtungen 0 sein muss.
 
ArnoNühm hat gesagt.:
Dijkstra und dessen Varianten sind nur geeignet, wenn man nur endlich viele Punkte betrachtet.
Zum Vergrößern anklicken....
Na ja, im Eröffnungspost ist schließlich von dem Ort eines Treffpunkts die Rede - da ich nicht davon ausgehe, dass sich da unendlich viele Personen von unendlich vielen Ursprungsorten treffen wollen, setze ich mal voraus das es tatsächlich nur um endlich viele Punkte geht...;)
 
Tarantoga hat gesagt.:
Na ja, im Eröffnungspost ist schließlich von dem Ort eines Treffpunkts die Rede - da ich nicht davon ausgehe, dass sich da unendlich viele Personen von unendlich vielen Ursprungsorten treffen wollen, setze ich mal voraus das es tatsächlich nur um endlich viele Punkte geht...;)
Zum Vergrößern anklicken....

Hast mich missverstanden. Ist klar, dass die Anzahl der Startpunkte endlich ist. Ich meine die Menge der möglichen Treffpunkte ist unendlich. Es ist also hochgradig inneffizient über jeden Punkt einer Fläche zu Routen, da es in nem in jedem auch noch so kleinen nichtleeren Polygon unendlich viele Punkte gibt.
 
wenn dir die einschränkung zur limmitierung der punkte nicht reicht (EINER der resultierenden punkte ist das minimum, du weißt nur noch nicht welcher) kannst du auch gerne mit einem 2. kriterium wie fxx + fyy -fxy² > 0 & fxx > 0 weiter rechnen, oder die Hesse matrix aufstellen ... aber im normal fall sollte die erste bedinung ausreichen um nur noch eine hand voll punkte testen zu müssen ... bekommst du eine unendliche anzahl von punkten und kannst mit einfacher logik nicht weiter einschränken, muss man halt weiterrechnen ... lustig wirds, wenn die anzahl der minima unendlich wird (ein kreis von infinitissimal dicht beieinanderliegenden startpunkten, mit einem startpunkt in der mitte, aber das sind konstruierte beispiele die nicht viel mit der realität gemein haben ...)
 
Alles klar soweit hab ichs jetzt. Der Post oben mit der Nullstelle war nen Irrtum.
Die Nullstellen der Ableitung zu bestimmen sollte auch ohne Näherungsverfahren machbar sein (Hab das jetzt nicht überprüft). Wunder mich nur, warum auf den Seiten über das Steiner-Weber-Problem immer Optimierungsalgorithmen genommen wurden. Dürfte doch eigentlich das gleiche wie das hier sein.
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben