Lösungsalgorithmen für Irrgärten

Grundidee und Voraussetzungen

Lösungsalgorithmen für Irrgärten sind Verfahren, mit denen automatisiert ein Weg aus einem Irrgarten gefunden werden kann. Einige Methoden funktionieren aus der Sicht einer Person oder eines Roboters im Irrgarten, ohne dass der gesamte Aufbau bekannt ist. Dazu gehören die zufällige Wegwahl, die Rechte-Hand-Methode, der Pledge-Algorithmus, der Trémaux-Algorithmus und der Algorithmus von Gaston Tarry. Andere Verfahren setzen voraus, dass man den ganzen Irrgarten überblickt, etwa auf Papier oder in einem Computerprogramm. Dazu zählen das Auffüllen von Sackgassen und die Suche nach dem kürzesten Ausweg.

Ein Standard- oder perfekter Irrgarten ist ein Irrgarten, in dem man nicht im Kreis gehen kann. In der Graphentheorie entspricht er einem Baum: Zwischen den Punkten gibt es Verzweigungen, aber keine geschlossenen Schleifen. Diese Verbindung erklärt, warum graphentheoretische Verfahren bei der Lösung von Irrgärten wichtig sind.

Einfache Wegwahl und Wandverfolgung

Bei der zufälligen Wegwahl geht man bis zur nächsten Kreuzung geradeaus und entscheidet dort zufällig, in welcher Richtung man weitergeht. Die Methode kann bereits von einem sehr einfachen Roboter ausgeführt werden. Da dieselben Wege mehrfach betreten werden können, dauert die Suche im Allgemeinen sehr lange. Trotzdem wird der Ausgang schließlich erreicht.

Bei der Rechte-Hand-Methode legt man die rechte Hand an eine Wand und hält während des gesamten Weges Kontakt zu ihr. Ebenso kann konsequent die linke Hand verwendet werden. Sind alle Mauern miteinander oder mit der Außenseite verbunden, ist der Irrgarten also einfach zusammenhängend, erreicht man auf diese Weise entweder einen anderen Ausgang oder kehrt zum Eingang zurück. Topologisch lässt sich dies so erklären: Zusammenhängende Wände können gedanklich zu einem Kreis verformt werden, dessen Rand man vom Start bis zum Ende entlangläuft.

Die Methode kann versagen, wenn der Irrgarten nicht einfach zusammenhängend ist. Legt man die Hand etwa an eine freistehende Säule, kann man diese endlos umrunden. Theoretisch könnte eine Säule sogar einen fraktalen Querschnitt mit unendlich großem Umfang haben; praktisch lassen sich solche Formen jedoch nicht errichten. Außerdem eignet sich die Wandregel möglicherweise nicht dazu, ein bestimmtes Ziel im Inneren zu finden.

Auch bei Irrgärten mit drei oder mehr Dimensionen ist die Methode anwendbar, wenn sich die möglichen Richtungen an Kreuzungen eindeutig auf eine zweidimensionale Ebene übertragen lassen. Dabei muss die aktuelle Orientierung immer bekannt sein, damit rechts und links eindeutig bestimmt werden können.

Hindernisse sicher umrunden

Der Pledge-Algorithmus verhindert, dass eine Person oder ein Roboter dauerhaft eine freistehende Wand umrundet. Er verwendet eine zufällig gewählte Zielrichtung und benötigt bei der Anwendung in einem zweidimensionalen Irrgarten einen Kompass. Solange kein Hindernis im Weg liegt, bewegt man sich geradeaus in der Zielrichtung. Trifft man auf ein Hindernis, folgt man dessen Wand stets mit derselben Hand und zählt dabei alle Drehwinkel: Drehungen in eine Richtung werden positiv, Drehungen in die Gegenrichtung negativ gezählt.

Die Wand darf erst verlassen werden, wenn zwei Bedingungen gleichzeitig erfüllt sind: Die aktuelle Ausrichtung stimmt wieder mit der Zielrichtung überein, und die Summe aller Drehungen ist gleich Null. Nur die ursprüngliche Richtung wieder erreicht zu haben, genügt nicht.

Das zeigt das Beispiel eines Hindernisses in Form des Großbuchstabens „G“. Wer von rechts eintritt, kann nach einer vollständigen Drehung wieder in die Zielrichtung blicken, obwohl die Winkelsumme 360° beträgt. Würde man nun die Wand verlassen, geriete man in eine Endlosschleife. Der Pledge-Algorithmus folgt der Wand weiter, bis neben der richtigen Ausrichtung auch die Winkelsumme Null erreicht ist.

In einem endlichen und fairen zweidimensionalen Irrgarten findet der Algorithmus von jedem inneren Punkt aus den Weg ins Freie. Umgekehrt ist er im Allgemeinen nicht geeignet, vom Eingang aus ein bestimmtes Ziel im Inneren zu erreichen.

Systematische Verfahren mit Markierungen

Der Trémaux-Algorithmus benutzt Markierungen, beispielsweise Striche auf dem Boden. Er funktioniert garantiert in allen Irrgärten mit wohldefinierten Durchgängen. Jeder Gang ist entweder unbesucht, einfach markiert oder zweifach markiert. Zu Beginn wird eine beliebige Richtung gewählt. Jeder durchlaufene Gang wird von einer Kreuzung bis zur nächsten markiert.

An einer erstmals erreichten Kreuzung wählt man einen beliebigen weiterführenden Gang. Kommt man an eine bereits markierte Kreuzung und ist der gerade benutzte Gang erst einmal markiert, dreht man um und markiert ihn beim Rückweg ein zweites Mal. Andernfalls nimmt man einen Gang mit möglichst wenigen Markierungen. Wird das Ziel erreicht, ist der direkte Weg zurück zum Start genau einmal markiert. Existiert kein Ausgang, kehrt man schließlich zum Ausgangspunkt zurück; dann trägt jeder Gang genau zwei Markierungen und wurde einmal in jeder Richtung durchlaufen. Dieser Weg heißt „bidirectional double-tracing“.

Der 1895 von Gaston Tarry (1843–1913) entdeckte Algorithmus verwendet die Markierungen „Stopp“ und „zuletzt“:

• Beim Betreten eines Ganges wird dessen Eingang mit „Stopp“ markiert. Ein so markierter Gang darf nicht erneut betreten werden.

• Beim ersten Besuch einer Kreuzung wird der gerade verlassene Gang mit „zuletzt“ markiert.

• Solange unmarkierte Gänge vorhanden sind, wird einer davon beliebig gewählt. Gibt es keinen mehr, geht man durch den mit „zuletzt“ markierten Gang.

Der Ausgang wird damit garantiert gefunden. Gibt es keinen Ausgang, werden alle Kreuzungen besucht und alle Gänge genau zweimal, einmal in jeder Richtung, durchschritten; anschließend endet das Verfahren wieder am Startpunkt. Anders als der Pledge-Algorithmus kann Tarrys Methode auch vom Eingang zu einem Ziel im Inneren führen. Der Trémaux-Algorithmus ist ein Spezialfall des Algorithmus von Tarry.

Verfahren bei vollständigem Überblick

Beim Auffüllen von Sackgassen müssen Aufbau, Start und Ziel des gesamten Irrgartens bekannt beziehungsweise sichtbar sein. Das Verfahren eignet sich deshalb für Irrgärten auf Papier oder in Computerprogrammen, nicht aber für eine Person in einem unbekannten Irrgarten. Zunächst werden alle Sackgassen gesucht und jeweils bis zur nächsten Kreuzung „aufgefüllt“, also aus der weiteren Suche ausgeschlossen.

Jeder Schritt bewahrt die Topologie des Irrgartens: Das Ziel kann nicht versehentlich vom Start getrennt werden. Das Verfahren endet auch nicht zu früh, weil das Ergebnis keine Sackgassen mehr enthalten darf. In einem perfekten Irrgarten bleibt nach dem Auffüllen aller Sackgassen genau der Lösungsweg übrig. Besitzt der Irrgarten Kreise, erhält man alle möglichen Lösungswege.

Wenn mehrere Lösungen existieren, kann mit einer Breitensuche der kürzeste Start-Ziel-Weg bestimmt werden. Dabei werden die Zellen mithilfe einer Warteschlange in immer größerer Entfernung vom Start untersucht, bis das Ziel erreicht ist. Für jede besuchte Zelle speichert man entweder ihre Entfernung vom Start oder die benachbarte Zelle, von der aus sie betreten und in die Warteschlange aufgenommen wurde. Anschließend verfolgt man diese gespeicherten Angaben vom Ziel zurück zum Start. So ergibt sich der kürzeste Lösungsweg.

Physikalische Lösungsmodelle

Ein Irrgarten lässt sich auch durch Strömungen lösen. Füllt man Wasser in den Eingang eines waagerecht liegenden Irrgartens oder bläst Luft in einen Irrgarten mit luftdichten Gangdecken, zeigt die stärkste Strömung den kürzesten Weg zum Ausgang. Der Ausgang muss dabei als Austrittsöffnung dienen; in Sackgassen entsteht keine Strömung.

In geeigneten analogen Schaltungen können elektrische Ströme die Wasser- oder Luftströmungen ersetzen. Vermutlich nutzen auch Schleimpilze beim Durchqueren von Irrgärten einen Lockstoffgradienten, der ähnlich wie eine Wasserströmung wirkt.