Ist man mit einem Irrgarten konfrontiert und es besteht einem die Möglichkeit, Markierungen auf irgendeinerweise zu hinterlassen, so eignet sich der Tremaux-Algorithmus.
Der hinterliegende Vorgang ist grundsätzlich einfach zu verstehen, denn es orientiert sich anhand den folgenden Regeln:
- Doppelte Markierungen gelten als Blockade.
- Steht nur vorne und hinten als Richtungen zur Verfügung, nimmt man einen Schritt nach vorne.
- Trifft man auf einer Kreuzung, so müssen die Felder der rechten und linken Richtung, sofern sie weniger als zwei Markierungen aufweisen, klar markiert werden. Anschliessend führt man alle der folgenden Regeln, zu welchen die Situation passt.
- Sind keine Markierungen links oder rechts vorhanden: Folge einen zufälligen Pfad und markiere diesen.
- Has the field behind the junction been marked once: Mark the previous field to identify it as a dead end.
- Sind keine Markierungen links oder rechts vorhanden: Folge einen zufälligen Pfad und markiere diesen.
As long as the maze is static and solvable, this will find the way out.
Für die Neugierigend hab ich ein kleines Programm geschrieben, welches der Algorithmus visuell darstellt. Dies befindet sich hier: https://github.com/LazarusPit/maze-solver
Übrigens: Der Algorithmus lässt sich auf Irrgärten skalieren, bei denen mehr als 4 Richtungen pro Feld existieren können. Dabei ist nur das Konzept von links und rechts teils verwirrend, da es pro Himmelsrichtung mehr als eine Richtung geben könnte. Hier müsste man sich lediglich auf alle möglichen Richtungen ausser derjenigen, aus der man gekommen ist.
DE 
EN