Lösungsalgorithmen für Irrgärten

Lösungsalgorithmen für Irrgärten beschreiben Methoden, mit denen automatisiert ein Weg aus einem Irrgarten gefunden werden kann. Dabei gibt es Algorithmen, die einer in einem Irrgarten gefangenen Person ins Freie helfen können, ohne dass sie etwas über den Irrgarten weiß: die zufällige Wegwahl, die Rechte-Hand-Methode, der Pledge-Algorithmus und der Trémaux-Algorithmus. Dagegen setzen Algorithmen wie das Auffüllen von Sackgassen oder das Finden des kürzesten Auswegs voraus, dass der Irrgarten als Ganzes überblickt werden kann. Irrgärten, in denen man nicht im Kreis gehen kann, werden auch als Standard- oder perfekte Irrgärten bezeichnet. Diese sind äquivalent zu einem Baum in der Graphentheorie. Dies wird intuitiv klar, wenn man sich vorstellt, dass man die Wege eines perfekten Irrgartens geradebiegt. Macht man dies in der richtigen Weise, so sieht das Ergebnis einem Baum sehr ähnlich. Daher spielt die Graphentheorie auch eine große Rolle bei den Lösungsalgorithmen für Irrgärten.