Die Türme von Hanoi
In diesem Beispiel schauen wir uns das Spiel Türme von Hanoi etwas genauer an. (Türme von Hanoi auf Wikipedia) Ziel des Spiels ist es, den kompletten Scheiben-Stapel (in unserem Beispiel gibt es genau zwei Scheiben) vom linken Stapel auf einen anderen Stapel zu versetzen. Hierbei gelten zwei Regeln:
- Es darf immer nur eine Scheibe aufs Mal bewegt werden.
- Die bewegte Scheibe darf nicht auf eine kleinere Scheibe gelegt werden.
Übungen
-
Überlegen Sie sich, wie Sie dieses Spiel in ein Planungsproblem überführen können.
Wie können Sie jeden Zustand in diesem Spiel eindeutig beschreiben?
Es gibt mehrere sinnvolle Antworten zu dieser Frage. Wichtig ist, dass jeder Zustand wirklich eindeutig beschrieben werden kann. Eine mögliche Notation wäre, wenn wir für die grössere Scheibe die Zahl 2, für die kleinere Scheibe die Zahl 1 verwenden würden. Leere Stapel geben wir mit einem _ (Unterstrich/Underscore) an. Nun geben wir für jeden Stapel von oben nach unten alle Scheiben an und trennen die Stapel jeweils mit einem ";". Der Startzustand wäre also:
12;_;_ - Zeichnen Sie den Graphen, für das Spiel. Starten Sie hierfür vom Zustand 12;_;_ (oder verwenden Sie Ihre eigene Notation). Spielen Sie das Spiel nach, indem Sie jeweils mit Münzen und drei Stapelplätzen vom Startzustand Stück für Stück alle Zustände "erkunden".
- Zeichnen Sie den Baum, für das Spiel. Starten Sie hierfür vom Zustand 12;_;_ (oder verwenden Sie Ihre eigene Notation). Spielen Sie das Spiel nach, indem Sie jeweils mit Münzen und drei Stapelplätzen vom Startzustand Stück für Stück alle Zustände "erkunden". Wenn Sie einen Zustand bereits einmal besucht haben, müssen Sie ihn nicht nochmals notieren. Wenn Sie bei einem Zielzustand ankommen, können Sie an einer anderen Stelle im Baum weiterfahren.