Willkommen in Manus Zeitforum
InformationenAnmelden Registrieren

Erweiterte Suche

Türme von Hanoi - Kopfnussknacker gesucht

Thema erstellt von Skeptika 
Beiträge: 254, Mitglied seit 10 Jahren
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?
Signatur:
978-3842349889
[Gäste dürfen nur lesen]
Beiträge: 2.998, Mitglied seit 15 Jahren
Ich hab die Lösung:

Sind n Scheiben vorgegeben, so braucht man mindestens 2n-1 Schritte.

Aber ich will mich nicht mit fremden Federn schmücken.

Die Lösung fand ich unter Türme von Hanoi
2 Scheiben: 22-1 = 3
3 Scheiben: 23-1 = 7
4 Scheiben: 24-1 = 15
..... usw.

Also... immer mal googeln, da findet man (fast) alles
Signatur:
Wer jung ist, meint, er müsste die Welt retten :smiley8:
Der Erfahrene erkennt, dass er nicht alle Probleme lösen kann
:smiley3:
Beitrag zuletzt bearbeitet von Hans-m am 16.05.2014 um 13:24 Uhr.
[Gäste dürfen nur lesen]
Beiträge: 254, Mitglied seit 10 Jahren
Hans-m schrieb in Beitrag Nr. 2148-2:
Ich hab die Lösung:

Sind n Scheiben vorgegeben, so braucht man mindestens 2n-1 Schritte.

Aber ich will mich nicht mit fremden Federn schmücken.

Die Lösung fand ich unter Türme von Hanoi
2 Scheiben: 22-1 = 3
3 Scheiben: 23-1 = 7
4 Scheiben: 24-1 = 15
..... usw.

Also... immer mal googeln, da findet man (fast) alles

Das ist ja nicht einmal die Hälfte dessen, was ich gefragt hatte :-)

Ich zitiere mich selber:
Skeptika schrieb in Beitrag Nr. 2148-1:
Ein Algorithmus sollte also für die Eingabe der Scheibenmenge die Anzahl benötigter Züge und die Zugfolge ausgeben.

und
Skeptika schrieb in Beitrag Nr. 2148-1:
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?

Also, immer genau lesen, dann versteht man auch die Fragen :-)
Signatur:
978-3842349889
[Gäste dürfen nur lesen]
In diesem Forum dürfen nur Mitglieder schreiben. Hier kannst du dich anmelden
Zum Seitenanfang Nach oben