Pathfinding
-
Hallo,
ich brauche einen Pathfinding Algorithmus. Die Besonderheit ist, dass ich auch sehr auf Rechenzeit achten muss. Deswegen ist es vielleicht sinnvoll nicht immer die beste Möglichkeit auszuspucken, wenn dadurch lange gerechnet werden muss.
Allerdings ist das Scenario recht einfach. Ich habe eine Liste von Orten mit Koordinaten und eine Liste von Wegen (mit Startort, Endort und Zeit, die zum Zurücklegen gebraucht wird).
Gibts da schon was fertig (sicherlich) oder muss ich mir da neu gedanken drüber machen.
Danke!
-
Wie wärs mit einem genetischen Algorithmus ala traveling salesman problem ?
-
Ich habe gerade das hier gefunden: http://ai-depot.com/Tutorial/PathFinding-Heuristics.html
ist schon nicht schlecht.
Der Travelling Salesman ist wohl etwas übertrieben, soweit ich das auf den ersten Blick sehe. Ich werde wohl nicht mehr als 25 Orte und nicht mehr als 50 Wege haben. Aber ich schau ihn mir nochmal genauer an.
-
Die übliche Antwort auf dieses Problem ist wohl: A*. Hast du dir diesen Algorithmus schon angeguckt? Wenn ja, was ist das Problem? Muss dein Algorithmus schneller sein?
-
Tippgeber schrieb:
Wie wärs mit einem genetischen Algorithmus ala traveling salesman problem ?
1. Hä? Seit wann ist ein Problem ein Algorithmus? ...bzw. Sag mal genauer, was du eigentlich meinst.
2. Ich glaube nicht, dass ein genetischer Algorithmus hier ein "Wundermittel" ist.
-
A* ist optimal effizient, entscheidend ist, dass du die Entfernungen zwischen zwei Knoten möglichst genau schätzen kannst.
-
Optimizer schrieb:
A* ist optimal effizient
...für das standard finde-den-kürzesten-Weg Problem. Das war hier aber nicht genau gefragt. Hier wurde nur nach irgendeinem Weg gefragt, was das Problem natürlich etwas aufweicht. Außerdem hat Loggy hier vielleicht Informationen zur Verfügung, die ihm weitere Optimierungen erlauben könnten.
Er könnte zum Beispiel zentrale Wege vorher abspeichern und das Problem damit von "Wie komme ich am schnellsten von einer Adresse in Hamburg nach München?" auf ein "Wie komme ich am schnellsten zur Autobahn?" reduzieren.
-
Gregor schrieb:
1. Hä? Seit wann ist ein Problem ein Algorithmus? ...bzw. Sag mal genauer, was du eigentlich meinst.
Habe ich das je behauptet? Das angesprochene Problem kann mit solch einem Algorithmus gelöst werden, ist vielmehr ein klassisches Beispiel dafür. Es geht dabei darum, den kürzesten Weg zu finden. Aber das kann man mit einem Blick in www.google.de selber schnell rausfinden :p
Wundermittel hin oder her, es ist ein Mittel.
-
Mit der Optimalität von A* wär ich in diesem Falle vorsichtig. A* ist optimal in dem Sinne, daß er auf jeden Fall den minimalen Weg findet, und auch die minimale Anzahl Knoten dafür expandiert, wenn Du aber auf den kürzesten Weg (optimale Lösung) verzichtest, dann kann es sein, daß es sogar schneller geht.
Aber ich halte A* hier auf jeden Fall für geeignet. Mit einer guten Heuristik ist er wohl nur in Spezialfällen zu schlagen.
-
Tippgeber schrieb:
Habe ich das je behauptet? Das angesprochene Problem kann mit solch einem Algorithmus gelöst werden, ist vielmehr ein klassisches Beispiel dafür. Es geht dabei darum, den kürzesten Weg zu finden. Aber das kann man mit einem Blick in www.google.de selber schnell rausfinden :p
Ich kenne das Traveling-Salesman Problem selbstverständlich. ...und dieses Problem ist nicht das Traveling-Salesman Problem, sondern etwas komplett anderes. ...liegt auch in einer komplett anderen Komplexitätsklasse. Die einzige Gemeinsamkeit ist wohl, dass beide Probleme mit Graphen zu tun haben.
-
Nagut, ich werde erstmal A* implementieren und dann schauen.
Allerdings weiß ich noch nicht, wie ich am besten den Weg schätze. Luftline ist möglich, aber nicht optimal, da ich verschiedene Wegqualitäten habe.
Aber ich muss erstmal klären, wie wichtig das jeweilige Ziel ist.
Also Danke erstmal.
-
Wichtig beim A* ist, daß Du nicht überschätzt. Unterschätzen ist okay, überschätzen ist blöd (Du verlierst u. U. die Optimalität). Deswegen ist Luftlinie zumeist bei Wegen keine schlechte Wahl... aber nur, wenn es keine "Umwege" gibt, die kürzer sind. Aber dafür mußt Du das konkrete Problem anschauen. Und umso besser Du schätzt umso weniger Knoten wird Dein A* expandieren müssen.
MfG Jester