In seinem Buch "
Das Affenpuzzle und weitere bad news" zeigt der Autor David Harel die Grenzen des mit Computern Berechenbaren auf und behauptet, dass es keinen Algorithmus für die Lösung der "
Türme von Hanoi" gibt, welcher die Anforderungen lt. Definition des Begriffes "Algorithmus" erfüllt.
Die Anforderungen sind zunächst:
1. Ein Algorithmus muss für eine beliebige Eingabe eine Lösung ausgeben
2. Der Algorithmus muss das Ergebnis in einer endlichen Zeit liefern.
Ein Algorithmus sollte also für die Eingabe der
Scheibenmenge die
Anzahl benötigter Züge und die
Zugfolge ausgeben.
In diesem Beispiel tragen die drei Säulen die Bezeichnung A, B und C, S ist die Anzahl der Scheiben und Z die Anzahl der benötigten Züge.
Beispiel 1:
Eingabe:
S = 1
Ausgabe:
Z = 1 [AC]
(bedeutet, in eienem Zug wird die Scheibe von A nach C bewegt)
Beispiel 2:
Eingabe:
S = 2
Ausgabe:
Z = 3 [AB AC BC]
(Scheibe 1 von A nach B, Scheibe 2 von A nach C, Scheibe 1 von B nach C)
Beispiel 3:
Eingabe:
S = 3
Ausgabe:
Z = 7 AC AB CB AC BA BC AC]
Nun mag man denken, dass doch sehr wohl ein Algorithus existiert, der die Anzahl der Züge vorab berechnen und die einzelnen Zugfolgen ausgeben kann (was auch stimmt), nur erkennt man auch, dass es aufgrund der Natur des Problems eine Obergrenze für die Eingabe S gibt...
Damit trifft Punkt 1 für die Definition des Algorithmus (s.o.) nicht zu.
Was ich mich nun frage: Kann man die Aufgabe nicht derart zerlegen, dass man in Abhängigkeit von der Eingabe die Ausgabe in mehrere einzelne Abschnitte unterteilt, die man dann parallel berechnet?
Beispiel:
Eingabe:
S = 5
Ausgabe:
Z = 31
Part 1:
[AC] (Zug 1)
Part 2:
[AB CB AC BA BC AC AB CB CA BA CB AC AB CB AC] (Züge 2 bis 15)
Part 3:
[BA BC AC BA CB CA BA BC AC AB CB AC BA BC AC] (Züge 16 bis 31)
Theoretisch könnten also 3 Computer parallel die Zugfolgen berechnen (wobei Computer 1 nicht viel zu tun hat), wodurch sich die Rechenzeit halbiert. Bei größeren Eingaben könnten so theoretisch auch ein paar hunderttausend Trilliarden Computer parallel rechnen und wenigstens die Eingabe etwas größerer Zahlen ermöglichen. Die Endlichkeit, also die Obergrenze wird dadurch zwar nicht aufgehoben, aber ein Stück nach hinten verlagert.
Meine Frage für die Kopfnussknacker unter uns hier: Wie könnte man nach einer Eingabe S sofort feststellen, wie die Spielsituation zu einem bestimmten Zeitpunkt aussieht, um von dort aus die nächste Zugfolge auszugeben?
[Gäste dürfen nur lesen]