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.
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 |
|---|---|
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| 6 | 63 |
| 7 | 123 |
| 8 | 255 |
| 9 | 511 |
| 10 | 1023 |
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:
| n | 2n-1 | Zeitaufwand |
|---|---|---|
| 5 | 31 | 31 Sekunden |
| 10 | 1023 | 17.1 Minuten |
| 20 | 1'048575 | 12.1 Tage |
| 30 | 1.0737418E09 | 34 Jahre |
| 60 | 1.1529215E18 | 36.6 Milliarden Jahre |
Die "Kompliziertheit" eines Lösungsverfahrens wird in der Informatik Komplexität genannt. Je nachdem 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 > 2 | 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) |