Pathfinding, oder doch nicht?
-
Hi,
ich habe ca. 800 Punkte im Raum mit unterschiedlichen Abstand.Jetzt möchte ich einen Anfangs und einen Zeilpunkt angeben und den kürzesten Weg finden, der alle diese Punkte genau einmal "übergeht".
Meine Frage ist jetzt: Hat das noch was mit Pathfinding zu tun (es exsistieren keine Hindernisse)? Kann man das mit A* lösen oder gibt es bessere Möglichkeiten?
MfG
Alexander Sulfrian
-
Das ist IMHO eine abgewandelte Form des Traveling-Salesman-Problems, mit dem Unterschied, dass du nicht wieder zum Ausgangsort zurückehrst. Es dürfte daher, wenn ich jetzt nichts übersehen habe, kein Algorithmus existieren, der dieses Problem effizient löst... bei 800 Knoten hast du dann verloren.
http://de.wikipedia.org/wiki/Traveling_salesmanIn gewisser Hinsicht ist es Pathfinding, aber du hast für jede mögliche Direktverbindung einen Dijkstra-Aufruf für die möglichen Zwischenstationen, daraus bildet man dann wieder ein einzelnes Kantengewicht und kommt dann auf einen Gesamt-Graphen. Sehr böse.
-
Optimizer schrieb:
Das ist IMHO eine abgewandelte Form des Traveling-Salesman-Problems, mit dem Unterschied, dass du nicht wieder zum Ausgangsort zurückehrst.
Hi,
zur Not geht's auch dass ich zum Ausgangspunkt zurückkehre.
Ich werd mir mal den Link anschauen.MfG
Alexander Sulfrian
-
Ich glaube nicht, dass es das leichter macht. np-vollständig ist der Handlungsreisende schon, ich überlege gerade nur, ob es mit Start-Ziel das auch noch ist. Ich sehe aber jetzt nichts, warum das mit Start-Ziel leichter werden sollte. Wird wohl sehr rechenaufwändig werden.
-
WEnn du zeit zum berechnen Hast, kannst du versuchen mit nem genetischen Algo weiterzukommen, auf www.ai-junkie.com gibts da sowas
-
Vielleicht helfen dir folgende Beobachtungen die ich gemacht habe (aber nicht überprüft habe):
- Wenn B der nacheste Punkt zu einem Punkt A ist und A der naheste zu B dann wird der Weg entweder von A nach B oder von B nach A gehen.
- Wenn ein Punkt A gleichweit weg von 2 Punkten B und C liegt und die Entferungen AB und AC der des nahesten Punkt zu A entsprechen dann kommt der Weg von entweder von B und geht zu A und dann C oder kommt von C und geht zu A und dann B.
EDIT:
Vielleicht solltest du mal etwas genauer beschreiben worum es geht: Muss es eine optimale Lösung sein? Sind die Punkte irgendwie angeordnet oder wirklich zufällig verteilt?
-
Hi,
erstmal danke für die Hinweise.
Also du Punkte sind zufällig im Raum angeordnet. Es muss aber nicht zwingend eine 100% beste Möglichkeit sein. Will halt nur nicht, dass es die längste wird
Ich werd es schätzungsweise mit der Nearest Neighbout Heuristic machen, bin für andere Vorschläge aber gerne noch offen...
MfG
Alexander Sulfrian
-
Wenn du einen anderen rehct einfachen haben willst, such mal nach Nearest Insertion (Farthest Insertion gibt ofter bessere Ergebnisse, ist aber sher änlich)
-
Ich würde es mal mit einem Ameisen Algorithmus versuchen.
Dabei lässt man virtuelle Ameisen den weg laufen, welche
dann die Spuren ihrer Vorgänger auswerten, und somit
dann kürzere Wegstrecken bevorzugen.
-
phlox81 schrieb:
Ich würde es mal mit einem Ameisen Algorithmus versuchen.
Dabei lässt man virtuelle Ameisen den weg laufen, welche
dann die Spuren ihrer Vorgänger auswerten, und somit
dann kürzere Wegstrecken bevorzugen.Hört sich interessant an. Gibt's irgendwo ne Seite mit Erläuterungen und sogat evtl. Beispielcode?
MfG
Alexander Sulfrian
-
In einer C't war mal was zu drin, im netz müsstest du auch
einiges finden. Wobei ich nicht weis, wie gut dir das
helfen wird, bei 800 knoten ist die wahrscheinlichkeit,
das die verbindung zwischen 2 Knoten die Kürzeste UND
die Beste ist, ist evtl. nicht immer gegeben...Lässt sich aber optimieren, in dem man immer den kürzesten
gefundenen Weg speichert, bzw. evtl. schon für zwischenschritte
speichert, und Ameisen die höher liegen einfach killt.Und je länger der Algorithmus rechnet, desto besser ist das Ergebnis
