Die Türme von Hanoi

Spielanleitung

Beim Knobelspiel "Türme von Hanoi" gilt es den geordneten Scheibenstapel vom Stab links auf den Stab rechts zu versetzen. Bewegt wird immer nur eine Scheibe auf einen der beiden anderen Stäbe. Dabei darf nie eine grössere Scheibe auf eine Kleinere zu liegen kommen.

Mit Drag'n drop werden die Scheiben verschoben.

Wie viele Bewegungen sind bei 4 Scheiben minimal notwendig? Wie viele bei 6 Scheiben.

Lösungshinweise

Bei 4 Scheiben sind bei optimalem Vorgehen 15 Bewegungen notwendig und bei 6 Scheiben deren 63. Die Anzahl minimal notwendiger Verschiebungen zeigt wie aufwändig die Lösung der Aufgabe ist.

Dank der Simulation lässt sich die Anzahl minimal notwendiger Bewegungen für bis zu 10 Scheiben ermitteln:

#Scheiben#Bewegungen
37
415
531
663
7123
8255
9511
101023

Aufwand

Die Anzahl notwendiger Bewegungen wächst mit zunehmender Anzahl Scheiben n rasch an. Die Anzahl Bewegungen bei n Scheiben kann mit der Formel 2n-1 berechnet werden.
Setzt man für die Bewegung einer Scheibe 1 Sekunde Aufwand ein, so wird klar, eine praktische Lösung der Aufgabe ist nur für kleine n möglich:

n2n-1Zeitaufwand
53131 Sekunden
10102317.1 Minuten
201'04857512.1 Tage
301.0737418E0934 Jahre
601.1529215E1836.6 Milliarden Jahre

Komplexität

Der "Kompliziertheit" eines Lösungsverfahrens wird in der Informatik Komplexität genannt. Je nach dem wie der Aufwand mit zunehmender Problemgrösse n anwächst, wird der Algorithmus einer Komplexitätsklasse zugeordnet (s. Tabelle).

Man sagt „schwere Probleme“ wachsen exponentiell oder schneller und „leichte Probleme“ können mit einem maximal polynomiellen Verfahren (Algorithmus) gelöst werden.

Komplexität O-Notation Kategorie Beispiel(e)
statisch O(1) leicht
logarithmisch O(log2(n)) leicht Binäre Suche
linear O(n) leicht Lineare Suche
n log n O(n * log2(n)) leicht Tournament-Sort, Merge-Sort, Quick-Sort
quadratisch O(n2) leicht Bubble-Sort, Insertion-Sort
Selection-Sort
polynomiell O(nk) für k ≥ 1 leicht Dijkstra Algorithmus
(Ameisen Algorithmus)
exponentiell O(dn) für d ≥ 1 schwer Türme von Hanoi
Fibonacci-Funktion rekursiv
faktoriell O(n!) schwer Problem des Handelsreisenden
(TSP Travelling Salesman Problem)