Die Schnellste Route

Dravere

Grüsse zusammen,

Ich bräuchte mal ein paar Ansatzhilfen, ganze Lösungen wären natürlich auch willkommen

Problem:
Wir haben einen 3D-Raum, einen Startpunkt und einen Endpunkt. Wir kennen die Koordinaten beider Punkte. Nun haben wir z.b. ein Schiff, welches vom Startpunkt zum Endpunkt fliegen soll. Es kann aber nur eine gewisse Tankfüllung mit sich nehmen. Anderst gesagt, irgendwo auf dem Flug zum Endpunkt, wird der Tank leer sein und das Schiff wird nur noch mit einem sehr langsamen Antrieb vorwärts kommen.
Desweiteren haben wir eine Liste von Tankstellen, welche sich alle irgendwo im Raum befinden. Welchen Weg muss nun das Schiff nehmen, um in der kürzesten Zeit zum Endpunkt zu kommen? Dabei ist es egal, wieviele Male es an einer Tankstelle haltet. Allerdings verbraucht jedes Auftanken n Minuten.

Daten welche wir kennen:
Startpunkt, Endpunkt, alle möglichen im Raum verfügbaren Tankpunkte, Antriebsgeschwindigkeit, Geschwindigkeit ohne Antrieb, Max Tankfüllung, Max Flugweite mit Antrieb bei vollem Tank, Dauer um zu tanken

Was ich brauche:
Eine möglichst Effiziente Art um auszurechnen, welches die schnellste Route ist.

Danke für die Hilfe.

Grüssli

physici_errantes

Alle Wege durchrechnen lassen und den schnellsten auswählen. imho machen das Routenplaner auch nicht anders.

Jan

Das Problem ließe sich vermutlich sehr schön als Graph darstellen. Da könnte man dann eine leicht modifizierte Variante eines Kürzeste-Wege-Algorithmus drüberlaufen lassen.

Dravere

physici_errantes schrieb:

Alle Wege durchrechnen lassen und den schnellsten auswählen. imho machen das Routenplaner auch nicht anders.

Das aber nicht wirklich Effizient, da es wohl so ein paar Millionen oder vielleicht noch mehr an Möglichkeiten gibt. Ich meine da liegen womöglich auch Tankstellen gar nicht auf dem Weg zwischen Start und Endpunkt, sondern irgendwo in eine andere Richtung. Zudem man kann ja x-fach an Tankstellen halten. Dadurch gibt es eine soooo grosse Kombinationsmöglichkeit, dass ich das nicht wirklich für das effizienteste halte. Da gibt es doch bestimmt was sinvolleres.

Grüssli

THX 1138

http://ai-depot.com/BotNavigation/Path-AStar.html
http://www.nist.gov/dads/HTML/shortestpath.html

Dravere

THX 1138 schrieb:

http://ai-depot.com/BotNavigation/Path-AStar.html
http://www.nist.gov/dads/HTML/shortestpath.html

Danke für die Links. Haben mir schon mal sehr weiter geholfen. Sie sprechen zwar nicht mein Problem genau an, aber geben mir immerhin eine Idee, wie ich mein Problem lösen könnte.
Wenn wer noch andere Ideen hat oder sonst etwas, dann immer her damit

Grüssli

Jester

Noch zusätzlich kann man die Suche bidirektional machen (also vom Start zum Ziel und gleichzeitig vom Ziel zum Start suchen lassen. Wenn sich die Suchräume treffen hat man ne kürzeste Route gefunden. (Achtung: die läuft nicht zwangläufig durch den Punkt an dem sich die Suchräume treffen!) Dadurch wird der Suchraum auch nochmal verkleinert.