schnellsten Weg berechnen

[Alkhorithmus]

Guten Tag.

Aufgrund meiner erbämlichen Fähgkeit selbst komplexere Alghorithmen zu entwickeln, habe ich mich hier angemeldet.

Mein Problem ist folgendes:

Ich habe ein 2-dimensionales Array, indem ich eine "Karte" abgespeichert habe.

Diese karte wird immer zufällig von einer Funktion von mir generiert...

jetzt möchte ich den schnellsten Weg von einem Punkt zum anderen berechnen.

Das wäre ja kein Problem, wenn es nicht noch die unpassierbaren Felder gibt.

Grafisch sieht das so aus.

S = Startpunkt

Z = Zielpunkt

B = begehbares Feld

0 = unpassierbares Feld

BBBB0

S0BBB

B0BBZ

BB0BB

BBBBB

Jetzt möchte ich (wie schon erwähnt) den kürzesten Weg von S nach Z berechnen.

mfg

Alkhorithmus

[Klotzkopp]

Wikipedia listet einige Beispiele auf. Oder willst du etwas Eigenes basteln?

[flashpixx]

Der bekannteste ist wohl Dijkstra-Algorithmus ? Wikipedia der auch in Navis in etwas abgewandelter Form eingesetzt wird

Du musst nur Deine Daten passend organisieren. Ein anderer Ansatz, der sich auf dem 2D Feld etwas besser realisieren lässt wäre Backtracking ? Wikipedia (ich meine aber, dass die Komplexität etwas schlechter ist)

[Alkhorithmus]

Danke...

Ich werd es mir mal angucken. Bei Fraggen meld ich mich wieder...

€dit1: Backtracking wird glaub ich zu lange dauern^^ Das Feld ist 140x140 Felder groß...

mfg

Alkhorithmus

Bearbeitet 19. März 2010 von Alkhorithmus

[Alkhorithmus]

Ich habe mich jetzt für den Dijkstra-Algorithmus entschieden.

Jetzt hab ich leider folgendes Problem.

Durch den Effekt dass alle Nachbarn gleich weit voneinander entfernt sind, gibt es komische Berechnungsfehler...

irgendeine Zahl = Weite bis zum Start

0 = Start (0 Schritte bis zum Start)

x = noch nicht berechnet

xxx2xx

xx1012

x2x1xx

Diese 2 kann nicht stimmen^^

mfg

Alkhorithmus

[Alkhorithmus]

srry, ich kann den Beitrag leider nicht mehr editieren...

Ich hab die Funktion jetzt fertig geschrieben. Doch leider braucht sie etwas weniger Zeit als eine Minute, wenn sie einen Weg von 20 Schritten ausrechnen soll. Könnte man das nicht verschnellern???

Es müsste theoretisch gehen^^ Nur leider weiss ich als Hobbyprogrammierer nicht, wie ich das anstellen sollte...

Im moment verwendet er noch den normalen Dijkstra-Algorithmus, der ein bestimmten Knoten sucht. Doch bei 20 Schritten, wird das ein bisschen zu langsam für einen KI.

Hat jemand noch ne Idee, wie man das verschnellern könnte?

mfg

Alkhorithmus

[flashpixx]

Hat jemand noch ne Idee, wie man das verschnellern könnte?

Generell gilt, dass Dein Problem, was eine Abwandlung des TSP (Traveling Sales Person) ist, das ganze NP-hart ist, d.h. für eine Menge X an Wegen, brauchst Du exponentiell viele Schritte, wenn Du alle Möglichkeiten durchlaufen willst, d.h. Du findest nur so den wirklich "optimalen" Weg.

Wenn Du nicht zwingen des kürzesten Weg brauchst, d.h. Du suchst einen "möglichst kurzen" Weg, wäre ein heuristisches Verfahren eine sinnvolle Alternative. Hierzu wäre z.B. ein Ameisenalgorithmus evtl kombiniert mit einem Genetischen Algorithmus / Evolutionäre Algorithem möglich.

Gerade Ameisenalgorithmen lassen sich schön Multithread / Multicore aufbauen und sind recht effizient. Alleine aber bei großen Problemen nicht sinnvoll.

Das ganze, wenn Du sehr viele Wege hast, d.h. > 1000 Möglichkeiten wäre dann noch mit einem "local search" wie z.B. Hill-Climbing oder eben Dijkstra zu optimieren.

Solche Heuristiken kann man nicht "generell" verwenden, da sie wirklich nur gute Ergebnisse liefern, wenn man problemspezifisch arbeitet