Irrgarten lösen

[AmY]

Hallo Leser!
Also, ich habe folgendes Problem:
Ich möchte ein großen Irrgarten möglichst schnell lösen. Jetzt ist meine Frage ob es eine schnellere Möglichkeit gibt als das ich immer an der Wand lang gehe, bis ich am Ziel bin. Diese Lösungsverfahren ist zwar generell ganz ok, nur bei Irrgärten mit 10^8 und mehr Feldern dauert das doch recht lange. Die Irrgärten sind übrigends immer wieder ganz neu zufällig(sonst müsst ich ja nicht den Weg suchen). Wäre schön wenn ihr mir helfen könntet!
Achso, zum Zweck: Das hat was mit einer Verschlüsselungstechnik (über mehrere Rechner) zu tun, die ich mir ausgedacht habe. Aber eigendlich ist das ja auch unwichtig für die Fragestellung. Vielleicht stell ich das Projekt irgendwann mal vor wenns so klappt wie ich hoffe.
Liebe Grüße
AmY

[Daniel Schuhmann]

http://www.cobans.net/fun.php

Könnte Dir weiterhelfen... :)

[JPSelter]

Spontan fällt mir folgender Ansatz ein (gerade selbst erdacht): Man probiert vom Eingang UND vom Ausgang gleichzeitig durch. In jedem Feld müsste gespeichert werden, wie man dorthingekommen ist (verkettete Liste, Array). Irgendwann treffen sich beide "Schlangen" und man verknüpft beide Wege zu einem. Naja, obs jetzt schneller ist, kann ich nicht sagen, vielleicht ist das auch kompletter Müll :D Aber vielleicht regt es zum Nachdenken an ;)

[chaosben]

Ich hab da noch einen Vorschlag, der aber auch nur quick&dirty gedacht wurde. :)

Wenn die Richtung des Ziels klar ist, könnte man bei einem Abzweig prüfen, wie hoch die Wahrscheinlichkeit ist, das man in dieser Richtung das Ziel findet. Und dann kann man der Reihe nach die Abzweige probieren, die am wahrscheinlichsten sind.

[Binärbaum]

Es gibt für solche Fälle auch spezielle Wegfindungsalgorithmen, der bekannteste davon dürfte der A*-Algorithmus (A-Stern-Algorithmus) sein. Wenn man mal A stern algorithmus bemüht, dürfte man da schnell etwas finden. ;)

MfG
Binärbaum

[AmY]

Zitat:

Zitat von Daniel Schuhmann

http://www.cobans.net/fun.php

Könnte Dir weiterhelfen... :)

danke das war ein super tip!
(da ist das mit dem A-Stern-Algorithmus gelöst)

lg amy