Sagen wir, ich möchte eine Navigationsroute von San Francisco nach New York zeichnen. Es gibt ungefähr tausend Dienste, die das kostenlos tun können. Es gibt auch viele Dienste, die das Problem des reisenden Verkäufers lösen und eine Route durch 6 Städte berechnen können, um die optimale Reihenfolge herauszufinden. Das sind alles gelöste Probleme.Wie könnte ich eine Kartenroute berechnen, die über optionale Wegpunkte von einem Startpunkt zu einem Zielpunkt führt?
Jetzt sagen wir, ich möchte einen Kurs von SF nach NY planen, halten an EV-Ladegeräte aus einer Datenbank auf dem Weg.
Das ist schwieriger als nur eine Reihe von Wegpunkten, weil ich nicht bei jedem anhalten muss. Ich muss nur meinen Weg beschränken, um von einem zum nächsten zu springen.
Wie kann ich das herausfinden? Gibt es einen Algorithmus, mit dem ich das vereinfachen kann? Oder vielleicht könnte ich OSRM() verwenden, um mir irgendwie zu helfen, anstatt mich auf die öffentlichen APIs zu verlassen. Wir könnten das brutal erzwingen und einfach die Routen berechnen, bis wir die kürzeste finden, die funktioniert, aber ich konnte sehen, dass das ziemlich schnell auseinander fällt.
von jedem Wegpunkt die Entfernung zum nächsten Punkt berechnen, wenn die Entfernung zur aktuellen Ladung größer ist, dynamisch einen neuen Wegpunkt für das nächste Ladegerät hinzufügen ... –
Das war mein erster Gedanke, aber manchmal muss man einen Umweg machen eine Route, die du normalerweise nicht nehmen würdest. Ich glaube nicht, dass die Suche nach dem nächsten Ladegerät in allen Situationen funktionieren würde, besonders wenn kein Ladegerät in der Nähe ist. –
Es ist unklar, wie viele dieser "optionalen" Wegpunkte tatsächlich notwendig sind: Sie geben eine obere Grenze ("Ich muss nicht bei jedem stoppen"), aber keine untere Grenze. Warum also nicht alle überspringen? Sie sind schließlich optional. –