Türme von Hanoi

aus Wikipedia, der freien Enzyklopädie

Die Türme von Hanoi sind ein mathematisches Knobel- und Geduldsspiel.

Inhaltsverzeichnis 1 Aufbau 2 Geschichte 3 Zugfolgen für kleine Türme 4 Rekursiver Algorithmus 5 Iterativer Algorithmus 6 Optimalität der Algorithmen 7 Eigenschaften optimaler Zugfolgen 8 Praktische Unlösbarkeit 9 Weblinks

[Bearbeiten] Aufbau

Das Spiel besteht aus drei Stäben A, B und C, auf die mehrere gelochte Scheiben gelegt werden, alle verschieden groß. Zu Beginn liegen alle Scheiben auf Stab A, der Größe nach geordnet, mit der größten Scheibe unten und der kleinsten oben. Ziel des Spiels ist es, den kompletten Scheiben-Stapel von A nach C zu versetzen.

Bei jedem Zug darf die oberste Scheibe eines beliebigen Stabes auf einen der beiden anderen Stäbe gelegt werden, vorausgesetzt, dort liegt nicht schon eine kleinere Scheibe. Folglich sind zu jedem Zeitpunkt des Spieles die Scheiben auf jedem Feld der Größe nach geordnet.

[Bearbeiten] Geschichte

Vermutlich wurde das Spiel 1883 vom französischen Mathematiker Edouard Lucas erfunden. Er dachte sich dazu die Geschichte aus, dass indische Mönche im großen Tempel zu Benares, im Mittelpunkt der Welt, einen Turm aus 64 goldenen Scheiben versetzen müssten, und wenn ihnen das gelungen sei, wäre das Ende der Welt gekommen.

In der Geschichte lösen die Mönche das Problem folgendermaßen: Der älteste Mönch erhält die Aufgabe, den Turm aus 64 Scheiben zu versetzen. Da er die komplexe Aufgabe nicht bewältigen kann, gibt er dem zweitältesten Mönch die Aufgabe, die oberen 63 Scheiben auf einen Hilfsplatz zu versetzen. Er selbst (der Älteste) würde dann die große letzte Scheibe zum Ziel bringen. Dann könnte der Zweitälteste wieder die 63 Scheiben vom Hilfsplatz zum Ziel bringen.

Der zweitälteste Mönch fühlt sich der Aufgabe ebenfalls nicht gewachsen. So gibt er dem drittältesten Mönch den Auftrag, die oberen 62 Scheiben zu transportieren, und zwar auf den endgültigen Platz. Er selbst (der Zweitälteste) würde dann die zweitletzte Scheibe an den Hilfsplatz bringen. Schließlich würde er wieder den Drittältesten beauftragen, die 62 Scheiben vom Zielfeld zum Hilfsplatz zu schaffen. Dies setzt sich nun bis zum 64. Mönch (dem Jüngsten) fort, der die obenauf liegende kleinste Scheibe alleine verschieben kann.

Da es 64 Mönche im Kloster gibt und alle viel Zeit haben, können sie die Aufgabe in endlicher, wenn auch sehr langer Zeit erledigen.

[Bearbeiten] Zugfolgen für kleine Türme

Das Spiel kann mit einer beliebigen Anzahl von Scheiben gespielt werden. Zur Erläuterung werden die Scheiben von der kleinsten bis zur größten mit S₁ bis S_n bezeichnet, wobei n die Anzahl der Scheiben ist. Die Angabe S₁-AC bedeutet zum Beispiel, dass die Scheibe S₁ vom Stab A auf den Stab C verschoben wird.

Der triviale Fall mit n=1, also mit einer Scheibe, ist in einem Zug lösbar. Es genügt der Zug S₁-AC.

Der Fall n=2, also mit zwei Scheiben, ist ebenfalls einfach. Zuerst wird die obere kleine Scheibe auf den Stab B gelegt, anschließend die untere größere Scheibe auf den Stab C und abschließend die kleine Scheibe vom Stab B auf den Stab C gelegt. Die Aufgabe wird also durch die folgenden drei Züge gelöst:

S₁-AB | S₂-AC | S₁-BC.

Für den Fall n=3, also mit drei Scheiben, kann folgende Vorüberlegung angestellt werden. Um die größte, also unten liegende, Scheibe nach C bewegen zu können, muss der 2-Stapel (Stapel aus zwei Scheiben) darüber auf B bewegt werden. Um diesen 2-Stapel nach B zu bewegen, muss der 1-Stapel darüber, also die oberste, kleinste Scheibe, zunächst nach C bewegt werden. Anschließend kann die mittlere Scheibe nach B und die kleinste Scheibe von C nach B bewegt werden. Es ergibt sich also die Zugfolge:

S₁-AC | S₂-AB | S₁-CB

Diese Zugfolge entspricht also dem Fall mit zwei Scheiben, wobei jedoch die Stäbe B und C vertauschte Rollen spielen.

Jetzt kann die dritte, unterste Scheibe nach rechts verschoben werden. Dies entspricht dem Zug:

S₃-AC

Zum Schluss muss der 2-Stapel von der Mitte nach rechts verschoben werden, um die Aufgabe zu lösen. Dies funktioniert genauso wie die Zugfolge am Anfang, nur dass Stab A mit Stab B, Stab B mit Stab C und Stab C mit Stab A vertauschte Rollen spielen. Es bleibt also die Zugfolge:

S₁-BA | S₂-BC | S₁-AC

auszuführen. Insgesamt werden also sieben Spielzüge benötigt.

Allgemein kann für jede zusätzliche Scheibe zuerst der Stapel mit einer Scheibe auf B, dann die unterste Scheibe nach C und anschließend der Stapel von B nach C weiterbewegt werden. Für den Fall n=4, also mit vier Scheiben, ergibt sich also die Zugfolge mit den 15 Lösungsschritten:

S₁-AB | S₂-AC | S₁-BC | S₃-AB | S₁-CA | S₂-CB | S₁-AB

S₄-AC

S₁-BC | S₂-BA | S₁-CA | S₃-BC | S₁-AB | S₂-AC | S₁-BC

[Bearbeiten] Rekursiver Algorithmus

Die Geschichte um die Mönche und die Zugfolgen für kleine Scheibenanzahlen führen direkt zu einem rekursiven Algorithmus zur Lösung des Spiels. Da sich ein Computerprogramm zur Lösung des Spiels mit wenigen Zeilen schreiben lässt, ist Türme von Hanoi ein klassisches Beispiel für diese Art der Problemlösung.

Der Algorithmus besteht im Wesentlichen aus einer Funktion bewege, die vier Parameter besitzt. Mit i ist die Anzahl der zu verschiebenden Scheiben bezeichnet, mit a der Stab von dem verschoben werden soll, mit b der Stab, der als Zwischenziel dient und mit c der Stab, auf den die Scheiben verschoben werden sollen. Zur Lösung des eigentlichen Problems wird bewege mit i=n, a=A, b=B und c=C aufgerufen.

Die Funktion bewege löst ein Teilproblem dadurch, dass es dieses in drei einfachere Probleme aufteilt, sofern der zu verschiebende Turm mindestens die Höhe 1 besitzt. Andernfalls ist die Funktion bewege untätig. Die drei Teilprobleme werden sequentiell ausgeführt. Zunächst wird der um eine Scheibe kleinere Turm von c auf das Zwischenziel b verschoben, indem sich die Funktion bewege selbst mit den entsprechenden Parametern aufruft. Die Stäbe b und c tauschen dabei ihre Rollen. Anschließend wird die einzig verbliebene Scheibe von a nach c verschoben. Zum Abschluss wird der zuvor auf b verschobene Turm auf seinen Bestimmungsort c verschoben, wobei hier a und b die Rollen tauschen.

funktion bewege (Zahl i, Stab a, Stab b, Stab c) {
    falls (i > 0) {
       bewege(i-1, a, c, b);
       verschiebe oberste Scheibe von a nach c;
       bewege(i-1, b, a, c);
    }
}

So verhält sich die Funktion bei drei Scheiben
(die Stäbe wurden durchnummeriert, links: 1, mitte: 2, rechts: 3.
Der Bewegungsablauf ist exakt wie im Bild oben):

bewege(3,1,2,3) {
    bewege(2,1,3,2) {
        bewege(1,1,2,3) {
            bewege(0,1,3,2){};
            verschiebe oberste Scheibe von 1 nach 3;
            bewege(0,2,1,3){};
        };
        verschiebe oberste Scheibe von 1 nach 2;
        bewege(1,3,1,2){
            bewege(0,3,2,1){};
            verschiebe oberste Scheibe von 3 nach 2;
            bewege(0,1,3,2){};
        };
    };
    verschiebe oberste Scheibe von 1 nach 3;
    bewege(2,2,1,3){
        bewege(1,2,3,1){
            bewege(0,2,1,3){};
            verschiebe oberste Scheibe von 2 nach 1;
            bewege(0,3,2,1){};
        };
        verschiebe oberste Scheibe von 2 nach 3;
        bewege(1,1,2,3){
            bewege(0,1,3,2){};
            verschiebe oberste Scheibe von 1 nach 3;
            bewege(0,2,1,3){};
        };
    };
};

Die Korrektheit des Algorithmus ist zwar intuitiv glaubhaft, formal aber nicht trivial beweisbar. Im Wesentlichen müssen zwei Dinge gezeigt werden. Zum einen müssen die Teillösungen korrekt arbeiten. Zum anderen ist zu zeigen, dass diese überhaupt durchgeführt werden können. Schließlich darf keine der Scheiben, die bei Teillösungen nicht betrachtet werden, den Transport verhindern. Dass dem tatsächlich so ist, folgt aus der Eigenschaft, dass die Funktion bewege bei jeder Teillösung immer nur die kleinsten i Scheiben bewegt. Sowohl diese Eigenschaft, als auch die Korrektheit der Teillösungen, lässt sich durch vollständige Induktion zeigen.

[Bearbeiten] Iterativer Algorithmus

Buneman und Levy haben 1980 einen iterativen Algorithmus beschrieben, der die gleiche Zugfolge generiert. Bei diesem ist die Korrektheit zwar nicht sofort erkennbar, die Handlungsweise aber ohne das Konzept der Rekursion verständlich. Es sei vorausgesetzt, dass die Stäbe A, B und C bei gerader Scheibenanzahl im Uhrzeigersinn auf einem Kreis angeordnet sind, sonst entgegen dem Uhrzeigersinn. Die Scheiben befinden sich zum Anfang alle auf Stab A, am Ende auf Stab C.

Solange sich auf wenigstens einem der beiden Stäbe A und B Scheiben befinden, wird erst die kleinste Scheibe (S₁) im Uhrzeigersinn und anschließend, sofern dies möglich ist, eine von S₁ verschiedene Scheibe verschoben. Als Pseudocode notiert ergibt sich also folgender Algorithmus:

solange (Stab A oder B enthalten Scheiben) {
    Verschiebe S1 im Uhrzeigersinn um einen Platz;
    falls (eine von S1 verschiedene Scheibe ist verschiebbar)
        Verschiebe eine von S1 verschiedene Scheibe;
}

So verhält sich die Funktion bei drei Scheiben (vergleiche Bild oben).

Um mit dem Bild zu synchronisieren, wird S₁ um zwei , statt um ein Feld im Uhrzeigersinn verschoben:

Anfangsposition:
A=3,2,1 | B=0,0,0 | C=0,0,0

Erster Durchlauf:
A=3,2,0 | B=0,0,0 | C=1,0,0 // S1 von A nach C
A=3,0,0 | B=2,0,0 | C=1,0,0 // S2 von A nach B

Zweiter Durchlauf: 
A=3,0,0 | B=2,1,0 | C=0,0,0 // S1 von C nach B
A=0,0,0 | B=2,1,0 | C=3,0,0 // S3 von A nach C

Dritter Durchlauf:
A=1,0,0 | B=2,0,0 | C=3,0,0 // S1 von B nach A
A=1,0,0 | B=0,0,0 | C=3,2,0 // S2 von B nach C

Letzter Durchlauf
A=0,0,0 | B=0,0,0 | C=3,2,1 // S1 von A nach C

Endposition:
A=0,0,0 | B=0,0,0 | C=3,2,1

Der zweite Zug innerhalb der Schleife ist bis auf den letzten Schleifendurchgang immer möglich und auch eindeutig. Um dies einzusehen, sei der Stab, auf dem S₁ liegt mit a und von den beiden verbliebenen Stäben denjenigen mit der kleineren obenaufliegenden Scheibe mit b, der anderen mit c bezeichnet. Offensichtlich kann die oberste Scheibe von b auf c verschoben werden. Dies ist zugleich die einzige Möglichkeit, eine Scheibe verschieden von S₁ zu verschieben. Denn weder die oberste Scheibe von b noch von c kann auf a verschoben werden, da dort mit S₁ die kleinste Scheibe liegt. Auch ein Verschieben der obersten Scheibe von c nach b ist nach Wahl der Bezeichnungen der Stäbe nicht möglich. Der Fall, dass keine andere Scheibe als S₁ verschiebbar ist, tritt nur dann ein, wenn alle Scheiben wieder auf einem Stab liegen, das Ziel also bereits erreicht ist.

[Bearbeiten] Optimalität der Algorithmen

Es gibt für jede Scheibenanzahl nur einen optimalen Lösungsweg für das Problem, also nur eine kürzeste Zugfolge. Diese wird von beiden Algorithmen durchlaufen. In diesem Sinne sind die Algorithmen also optimal.

Für den rekursiven Algorithmus lässt sich dies leicht einsehen. Bevor die unterste Scheibe eines (Teil-)Turmes verschoben werden kann, müssen alle darüberliegenden Scheiben auf das Zwischenziel verschoben werden (dort müssen sie natürlich in geordneter Reihenfolge landen). Erst dann kann die unterste Scheibe auf den Zielstab verschoben werden. Denn nur dann liegt diese frei und nur wenn alle ursprünglich über dieser Scheibe liegenden Scheiben auf dem Zwischenziel liegen, kann keine dieser kleineren Scheiben das verschieben der untersten Scheibe auf das Ziel blockieren.

Für die Optimalität des iterativen Algorithmus genügt es zu zeigen, dass die durch den rekursiven Algorithmus bestimmte Zugfolge den Bedingungen des iterativen Algorithmus genügt. Dies ergibt sich aus der folgenden Überlegung: Das Versetzen eines nichtleeren Teilturmes beginnt und endet jeweils mit einer Bewegung der kleinsten Scheibe. In der rekursiven Funktion wird also unmittelbar vor und unmittelbar nach dem Verschieben der i-ten Scheibe die kleinste Scheibe bewegt. Da jede Bewegung einer Scheibe auf dieser Anweisung beruht und die kleinste Scheibe aufgrund der Optimalität niemals zweimal direkt hintereinander bewegt wird, wird sie in jedem zweiten Zug versetzt. Die zyklische Richtung, in der die beiden Teiltürme in einem Aufruf der Funktion versetzt werden, ist für die beiden rekursiven Aufrufe a-c-b und b-a-c der Funktion dieselbe, nämlich der Richtung a-b-c entgegengesetzt. Infolgedessen ist die zyklische Richtung für alle Aufrufe mit i = 1 dieselbe, das heißt die kleinste Scheibe wird immer in derselben Richtung bewegt. Somit erzeugt der rekursive Algorithmus dieselbe Zugfolge wie der iterative.

Der iterative Algorithmus führt auch dann zur Lösung, wenn die Stäbe falsch auf dem Kreis angeordnet werden. Im Falle einer falschen Anordnung werden die Scheiben aber zuerst auf Stab B verschoben. Da in dieser Situation die Abbruchbedingung nicht erfüllt ist, wird anschließend weiter auf C verschoben. Der Algorithmus benötigt in diesem Fall damit doppelt so viele Züge, ist dann also nicht optimal.

Für eine optimale Zugfolge sind folgende Bedingungen notwendig und hinreichend:

1. Eine bestimmte Spielsituation darf nicht erneut erreicht werden.
2. Die zuletzt bewegte Scheibe darf nicht gleich noch einmal bewegt werden.

Die oben angegeben Zugfolgen für kleine Scheibenanzahlen sind optimal, entsprechen also genau den Zugfolgen, die von den Algorithmen erzeugt werden.

[Bearbeiten] Eigenschaften optimaler Zugfolgen

Für optimale Zugfolgen lassen sich eine ganze Reihe von Eigenschaften herleiten. Wegen der Optimalität des rekursiven Algorithmus ist dies besonders leicht anhand seiner Funktionsweise möglich.

Sei n wieder die Anzahl der Scheiben. Die Anzahl der Züge der optimalen Lösung ist dann 2ⁿ − 1. Dies lässt sich leicht induktiv zeigen. Für eine einzelne Scheibe ist dies sicher richtig, denn diese muss nur von A nach C verschoben werden, die optimale Zugfolge besteht also, wie behauptet, aus einem Zug. Für größere Scheibenanzahlen wird die Anzahl der Züge durch Summation der Züge für die Teilprobleme nachgewiesen. Die Zuganzahl entspricht also dem Doppelten der minimalen Zuganzahl für den um eine Scheibe kleineren Turm, da dieser zweimal bewegt werden muss, plus den einen Zug, um die größte Scheibe zu bewegen. Wie behauptet folgt:

Es lässt sich leicht bestimmen, wie oft und bei welchen Zügen eine Scheibe bei einer optimalen Zugfolge bewegt wird. Allgemein gilt, dass die Scheibe S_k genau 2^{n − k} mal bewegt wird. Dabei wird sie beim Zug 2^{k − 1} das erste Mal und dann nach jeweils 2^{n − k} Zügen erneut bewegt. Die kleinste Scheibe S₁ wird bei jedem zweiten Zug bewegt, beginnend mit dem ersten Zug. Die zweitkleinste Scheibe S₂ wird bei jedem vierten Zug bewegt, beginnend mit dem zweiten Zug. Die größte Scheibe S_n wird einmal bewegt, und zwar beim mittleren, also dem 2^{n − 1}-ten Zug. Die zweitgrößte Scheibe S_{n − 1} wird zweimal bewegt, und zwar nach dem ersten und dritten Viertel der um 1 erhöhten Zugfolge, also bei den Zügen 2^{n − 2} und . Auf diese Weise ist es möglich, an jedem Punkt der Zugfolge zu bestimmen, welche Scheibe als nächstes bewegt werden muss.

[Bearbeiten] Praktische Unlösbarkeit

Wie im vorangegangenen Abschnitt gezeigt, werden selbst bei optimaler Zugfolge 2ⁿ − 1 Züge zur Lösung der Aufgabe benötigt, wobei n die Anzahl der Scheiben ist.

Anzahl Scheiben	Benötigte Zeit
5	31 Sekunden
10	17 Minuten
20	12 Tage
30	34 Jahre
40	348 Jahrhunderte
50	35 Millionen Jahre

Selbst für kleine n wird die Aufgabe damit praktisch unlösbar. In diesem Zusammenhang wird auch von einem exponentiellen Wachstum der Komplexität des Problems gesprochen.

Unter der Annahme, dass die Mönche eine Scheibe pro Sekunde verschieben können und dass sie bis zur Vollendung der Aufgabe kontinuierlich und ohne Pause durcharbeiten, lässt sie die Dauer zur Lösung des Problems wie in nebenstehender Tabelle abschätzen.

Diese zeigt, dass bereits für relativ kleine Türme der Aufwand zu deren Verschiebung so groß wäre, dass die Aufgabe praktisch nicht mehr zu bewältigen ist, insbesondere wenn man bedenkt, dass unser Universum schätzungsweise gerade mal 13,5 Milliarden Jahre alt ist, für n=64 die Aufgabe aber bereits 584 Milliarden Jahre beanspruchen würde.

[Bearbeiten] Weblinks

• Hanoi Tutorial mit illustrierter Anwendung zur Erstellung von Lösungen und kommentiertem Algorithmus
• mister-mueller - Anschauliche Darstellung mit einer ausführlichen Erklärung.
• hanoimania - Implementation in 110 verschiedenen Programmiersprachen.
• Towers of Hanoi bei Wolfram Research - Zusammenhang zu verschiedenen mathematischen Fachgebieten
• "Towers of Hanoi" von Apostolos Syropoulos - mit vielen weiteren Algorithmen
• Online-Spiel der Hanoi Türme - zum selber ausprobieren