Türme von Hanoi

Hier entstehen die Türme von Hanoi in Millisekunden!

Gewidmet Harry Paul zum 91. Geburtstag

In der Informatik gelten die Türme von Hanoi (Wiki) als ein Paradebeispiel für ein Problem, das sich nur rekursiv (oder iterativ) lösen lässt. Die Zeit für die Berechnung einer bestimmten Position n wächst also exponentiell mit O(2ⁿ). In diesem Artikel wird eine explizite Lösung vorgestellt, mit der man jede Position n mit der gleichen Rechenzeit O(1) berechnen kann. Diese explizite Lösung wird in allen Animationen verwendet.

Für 10 Scheiben sieht das Umsortieren so aus (oben wird die Zahl der Züge angezeigt, mit 1 Sekunde Pause für Mersenne-Zahlen):

Angenommen die Mönche haben vor genau 91 Jahren damit begonnen, eine Scheibe pro Sekunde zu bewegen. Dann sehen die Positionen der Scheiben zu den Zeiten 91a-45s bis 91a+45s so aus (die oberste Scheibe (1) wird in jedem zweiten Zug bewegt, usw.):

Oder mit Scheiben: Die Startposition 0 (vor genau 91a) wird 5 Sekunden angezeigt, dann geht es im Sekundentakt weiter wie oben, also mit 91a-45s:

Herzlichen Glückwunsch!

Methode: Explizite Berechnung der Position der Scheiben zu vorgegebener Anzahl der Züge. Rechenzeit pro Position 50ms. Zum Vergleich: Die Zeit für rekursive Berechnung der Position 91*365*24*3600 = 2869776000 beträgt 6.7h.

Details: Die Standardprozedur zur rekursiven Berechnung der Positionen der Scheiben sieht in Maple so aus:

(1)

Mit vier Scheiben und den Positionen a,b und c erhält man z.B.

Dabei ist 1..4 die Nummer der Scheibe (1 für die kleinste Scheibe), die von der ersten (Start) auf die letzte (Ziel) Position bewegt wird (die mittlere Position od. Parkposition ist nur zur Vollständigkeit aufgeführt). "1,a,c,b" bedeutet also: bewege Scheibe 1 von a nach b, und "2,a,b,c": bewege Scheibe 2 von a nach c.

Man sieht an diesem Beispiel:
1. Scheiben mit ungerader Nummer bewegen sich zyklisch mit (a,b,c) und Scheiben mit gerader Nummer zyklisch mit (a,c,b).
2. Scheibe 1 wird in jedem zweiten Zug, Scheibe 2 wird in jedem vierten Zug, und Scheibe j wird in jedem 2^j-ten Zug bewegt.
3. Anmerkung: Falls als Zielstapel für den vollständigen Turm b oder c vorgegeben wird, kann das je nach Anzahl der Scheiben (gerade oder ungerade) leicht berücksichtigt werden.

Nachdem die Bewegung der Scheiben zyklisch ist, kann es sich nicht um ein Problem handeln, das nur rekursiv (oder iterativ) zu lösen ist. Es muss also eine explizite Lösung geben. Um diese explizite Lösung zu finden, muss man nur die Frage beantworten wie oft die Scheibe j bewegt wurde, wenn insgesamt n Züge gemacht wurden.

Mit einem einfachen Abzählverfahren findet man

(3)

Veranschaulichung für fünf Scheiben

Womit die Rechenzeit von O(2ⁿ) auf O(1) reduziert ist.

Bekanntermaßen lässt sich übrigens die Nummer der Scheibe, die bewegt werden muss, so berechnen (Rekursionsrelation):

oder so (explizit):

Nur weiß man dann nicht, wo sich die Scheibe befindet. Für die Rekursionsrelation findet man auch Darstellungen der Art (Abszisse: Nummer des Zuges, Ordinate: Nummer der Scheibe, die bewegt wird):

oder als Baum

Insbesondere die Baumdarstellung wird mit ihren Ästen von oben nach unten gelesen (Informatikbäume und Stammbäume haben ihre Wurzel oben :), also nicht in der Reihenfolge der Züge.
Die explizite Lösung lässt sich leichter finden, wenn man von links nach rechts liest (Zweierlogarithmus - um 1 nach oben verschoben - als "Einhüllende" in schwarz):

Download Worksheet (Minimalversion).

Noch mehr Links: Die mathematische Beschreibung dynamischer Systeme verwendet Systeme von Differentialgleichungen, die eng verwandt sind mit der Beschreibung atomarer Übergänge (Systeme mit zwei Zuständen) , siehe z.B. Spontane Emission | Kaskade | Photogalerie | Photonenemission | Weisskopf-Wigner

Moderne Physik mit Maple