Die Türme von Hanoi

Die Türme von Hanoi sind ein Spiel mit drei Plätzen.
Dabei gilt als Bedingung, daß eine größere Scheibe nicht auf eine kleinere Scheibe gelegt werden darf.
Es darf jeweils nur eine Scheibe umgelegt werden,
und alle Scheiben sind verschieden groß.
Man startet das Spiel, in man alle Scheiben auf einen der drei Plätze legt.
Man startet also mit einer einzigen Pyramide.

Ziel ist es, die Pyramide von einem Platz auf einen anderen zu legen.

Die Türme von Hanoi sind ein Spiel,
für das es im Grunde nur eine determinierte Lösung gibt.
Nur einen einzigen Weg, der zum Ziel führt.
Wer Fehler macht, und dabei die Regeln beachtet,
geht in eine falsche Richtung, und muß diesen Weg wieder zurückgehen,
um dann die richtige Richtung einzuschlagen.

Es gibt noch ein kleines Problem bei diesem Spiel.
Je größer die Anzahl der Scheiben, je mehr Scheiben müssen bewegt werden.
Die Anzahl der nötigen Bewegungen kann gigantisch werden.

Der Sage nach haben Mönche in einem indischen Kloster dieses Spiel mit 64 Scheiben gespielt.
Ehe sie fertig werden konnten, sind sie, ihre Nachfolger, und der Tempel zu Staub zerfallen.

Ein Lösungsalgorithmus könnte so aussehen:

Funktion Hanoi (N, A, B, C)
Begin
     Wenn N größer als Null ist, dann tue folgendes
         Begin
            Rufe die Funktion Hanoi(N-1, A,C,B) auf.
            Verschiebe eine Scheibe von Platz A nach Platz B.
            Rufe die Funktion Hanoi(N-1,C,B,A) auf.
         End
End

Wenn man das in PHP macht, dann sieht es so aus:

<?php
 function  Hanoi ($N, $A, $B, $C)
   {
     if ($N>0)
      {
         Hanoi($N-1, $A, $C, $B);
         echo("Bewege eine Scheibe von $A nach $B<br>");
         Hanoi($N-1, $C, $B, $A);
      }
   }
 $N=4;
 echo("Bewege $N Scheiben von Platz A nach Platz B<br><br>");
 Hanoi($N, "Platz A", "Platz B","Platz C");
 echo("<br>Die Pyramide wurde von Platz A nach Platz B versetzt.");
?>

Für $N=4 produziert der Algorithmus folgende Ausgabe:

Bewege 4 Scheiben von Platz A nach Platz B

Bewege eine Scheibe von Platz A nach Platz C
Bewege eine Scheibe von Platz A nach Platz B
Bewege eine Scheibe von Platz C nach Platz B
Bewege eine Scheibe von Platz A nach Platz C
Bewege eine Scheibe von Platz B nach Platz A
Bewege eine Scheibe von Platz B nach Platz C
Bewege eine Scheibe von Platz A nach Platz C
Bewege eine Scheibe von Platz A nach Platz B
Bewege eine Scheibe von Platz C nach Platz B
Bewege eine Scheibe von Platz C nach Platz A
Bewege eine Scheibe von Platz B nach Platz A
Bewege eine Scheibe von Platz C nach Platz B
Bewege eine Scheibe von Platz A nach Platz C
Bewege eine Scheibe von Platz A nach Platz B
Bewege eine Scheibe von Platz C nach Platz B

Die Pyramide wurde von Platz A nach Platz B versetzt.

Der Algorithmus macht folgendes:
Er verschiebt eine Pyramide mit N Scheiben vom Platz A zum Platz B.
Dabei nimmt er Platz C zur Hilfe.
Ohne einen dritten Ausweichplatz ist das Spiel Türme von Hanoi nicht lösbar.

Dem ersten Eindruck nach glaubt man kaum, daß dieser kleine Algorithmus das Problem lösen kann.
Man kann sich auch nicht vorstellen, daß das Problem nennenswerten Aufwand benötigt.

Tatsächlich löst der Algorithmus das Problem auf kürzestem Wege.
Schneller geht nicht.

Mit 64 Scheiben benötigt der Algorithmus praktisch unendliche Zeit.
Für N=64 müssen wir mehr als 10 hoch 19 Scheiben verschieben.
Also Milliarden Jahre, selbst wenn wir jede Sekunde 100 Scheiben verschieben.

Der Algorithmus ist rekursiv.

Um zu verstehen, daß hier alles seine Richtigkeit hat,
kommt man nur mit induktiven Denken weiter.

Wie funktioniert induktives Denken?
Man tut einfach so, als wenn der Algorithmus korrekt ist, und seine Aufgabe erfüllt.
Das ist so eine Art Vertrauensvorschuß.
Und man definiert diese Annahme für einen beliebigen Wert von N Scheiben.
Dabei muß N ganzzahlig sein, und größer-gleich 1.

Nun starte ich den Algorithmus gedanklich mit
Hanoi (N+1,’Platz A‘,’Platz B‘,’Platz C‘);

Anschließend den Algorithmus gedanklich durchgehen,
Zeile für Zeile, Schritt für Schritt.
Der Algorithmus schiebt N Scheiben von A nach C,
eine Scheibe von A nach B,
und zum Schluss N Scheiben von C nach B.

Resultat:
Wenn der Algorithmus für ein bestimmtes N korrekt arbeitet folgt,
daß er auch für N+1 korrekt arbeitet.

Zum Schluß rufen wir den Algorithmus mit einer Scheibe auf.
Hanoi (1,’Platz A‘,’Platz B‘,’Platz C‘)
Auch in diesem Fall arbeitet der Algorithmus korrekt.

Damit ist der induktive Schluß vollzogen.
Der Algorithmus arbeitet damit für alle N korrekt.
Genauer gesagt für alle ganzzahligen N>0.

Das ist wirklich ein zulässiger Beweis für die Richtigkeit des Algorithmus!
Das leuchtet nicht unbedingt sofort ein, aber irgendwann kommt der AHA-Effekt,
und man hat die Induktion verstanden.

Zeitaufwand?

Nach dem induktiven Prinzip kann man auch beweisen, daß der Algorithmus
2^N – 1
Funktionsaufrufe produziert.

Induktionsanfang:
N=1:

2^N – 1 =1

Für N=1 habe ich nur einen Aufruf, und innerhalb des Algorithmus keine Aufrufe.
Also insgesamt einen Aufruf.
Der Induktionsanfang ist damit erledigt.

Jetzt der Induktionsschritt:
N auf N+1:
Wir rufen den Algorithmus mit dem Wert N+1 auf.
Innerhalb des Algorithmus rufen wir zweimal mit dem Wert N auf.
Das ergibt:

(2^N– 1)+(2^N-1)+1=

2*(2^N-1)+1=

(2^N+1-2)+1=

2^N+1-1

Der Induktionsschritt ist damit auch erledigt.

Damit ist bewiesen, der Algorithmus hat den Zeitaufwand 2^N – 1 für alle ganzzahligen N>0

Der Algorithmus hat also exponentielles Wachsum.