Schnellster Pfad mit Beschleunigung bei Punkten

Question

Das ist etwas, was ich selbst erfunden habe, aber es scheint ein lustiges Problem zu sein, und es hat mich ratlos gemacht.

Sie haben eine Reihe von Punkten im zweidimensionalen Raum, wobei ein Punkt als "Start" und ein "Ende" bezeichnet wird. Jeder Punkt hat Koordinaten (in Metern vom Ursprung), aber auch eine "Beschleunigungszahl" (in Metern/Sekunde von Delta-V). Beim Erreichen eines Punktes (einschließlich des Starts) können Sie bis zu dieser Beschleunigungszahl in beliebiger Richtung beschleunigen. Die Kosten für die Kanten hängen von Ihrer aktuellen Geschwindigkeit ab, aber Sie müssen sich auch in die richtige Richtung bewegen.

Gibt es einen effizienten Algorithmus, um den schnellsten Weg bis zum Endpunkt zu finden? Ich habe nichts Besseres gefunden als "Versuche jeden Pfad und überprüfe die Ergebnisse". Djikstras und andere einfache Algorithmen funktionieren nicht, weil man nicht leicht sagen kann, dass ein Pfad zu einem Zwischenpunkt besser oder schlechter als der andere ist, wenn sie mit unterschiedlichen Anfangsgeschwindigkeiten ankommen.

Wenn das zu einfach ist, was ist, wenn Sie die Anforderung hinzufügen, dass Sie am Endpunkt anhalten müssen? (d. h., Sie müssen weniger als seinen Beschleunigungswert haben, wenn Sie das Ende erreichen.)

EDIT: Um klar zu sein, Richtung zählt. Sie behalten einen Geschwindigkeitsvektor bei, während Sie den Graphen durchlaufen, und Beschleunigung bedeutet, dass Sie ihm einen Vektor hinzufügen, dessen Größe auf die Beschleunigungszahl dieses Punktes beschränkt ist. Dies bedeutet, dass es Situationen gibt, in denen der Aufbau einer großen Geschwindigkeit nachteilig ist, da Sie zu schnell gehen werden, um zu anderen wertvollen Punkten/Ihrem Ziel zu "steuern".

Answer 1

Ich denke, dass die Anforderung, dass Sie nur die Beschleunigung von jedem Punkt verwenden, macht dieses Problem NP im allgemeinen Fall vollständig. Betrachten wir einen Eingang, der wie folgt aussieht:

Wenn die „große Distanz“ zwischen dem Endpunkt und dem Rest der Punkte groß genug ist, um die Kosten der endgültigen Lösung zu beherrschen, um eine optimale Lösung zu finden, wird koche, um einen Weg zu finden, um so viele Geschwindigkeitssteigerungen wie möglich vom Anfang des Graphen zu erhalten. Wenn Sie nur zulassen, dass jeder Punkt einmal übergeben wird, entspricht dies dem Hamilton-Pfadproblem, das NP-vollständig ist.

Das heißt, Ihr Problem hat noch einige zusätzliche Regeln (die Entfernungen sind euklidisch, die Grafik ist immer vollständig), die am Ende das Problem leichter machen könnte.

Answer 2

Sie können versuchen, dieses Problem rückwärts zu lösen, indem Sie Pfade vom Ende zum anderen Knoten rekursiv verfolgen und dann die maximale Geschwindigkeit entlang der Linie angeben, um von diesem Knoten zu einem anderen Knoten zu gelangen. Die Culling-Regel wird sein, wenn ein Pfad vom aktuellen zum nächsten Knoten mit weniger Geschwindigkeit und weniger Zeit vom Ende existiert, was bedeutet, dass der andere Pfad standardmäßig optimaler ist, da er mehr Knoten erreichen kann und weniger Zeit benötigt. Sobald ein Pfad den Startknoten erreicht, sollte er basierend auf der maximal erreichbaren Geschwindigkeit neu berechnet und gespeichert werden. Dann sammeln Sie den Pfad mit weniger Zeitaufwand.

Sie müssen hier nach einem verfügbaren Pfad suchen, da die verfügbaren Pfade in Ihrem Diagramm vom vorherigen Zustand mit einer indirekten Mechanik abhängig sind. Wenn Sie weniger Geschwindigkeit verwenden, können Sie mehr Auswahl treffen.