Türme von Hanoi mit vier Pfosten

Neue Frage »

07.10.2005, 15:25	SnIper	Auf diesen Beitrag antworten »
Wie sieht wohl das ganze aus wenn statt 3 Pfosten 4 Pfosten verwenden werden mit den Mindestanzahlen von Zügen???
07.10.2005, 15:27	SnIper	Auf diesen Beitrag antworten »
hanoi Hallo ihr kennt bestimmt das Spiel Turm von Hanoi. Wie sieht das ganze aus wenn man 4 Pfosten statt 3 verwendet? Bei 3 Pfosten sind es ja (2^n )-1 Möglichkeiten.
07.10.2005, 15:37	Mathespezialschüler	Auf diesen Beitrag antworten »
Verschoben Und woher willst du wissen, dass hier die meisten dieses Spiel kennen? Gruß MSS edit: Es wäre ganz schön gewesen, wenn du die Frage nur einmal gestellt hättest. Gruß MSS
07.10.2005, 16:44	Sciencefreak	Auf diesen Beitrag antworten »
Ich kenne das Spiel und kann dir als Tipp geben versuch das einfach mal für ein paar n und du wirst sehr schnell einen Zusammenhang sehen. Die technik für 4 Pfosten ist fast die gleiche wie für 3 und ich hoffe du meinst mit $\begin{eqnarray} 2^n-1 \end{eqnarray}$ Möglichkeiten die Anzahl der Züge die man mindestens braucht
07.10.2005, 17:39	riwe	Auf diesen Beitrag antworten »
und damit ihr seht, dass mir (fast) nichts zu blöd ist, das ganze - arthur möge mir verzeihen - in excel werner
07.10.2005, 18:05	AD	Auf diesen Beitrag antworten »
Sei $\begin{eqnarray} h_k(n) \end{eqnarray}$ die Mindest-Schrittanzahl für den Hanoiturm mit $\begin{eqnarray} k \end{eqnarray}$ Pfosten und $\begin{eqnarray} n \end{eqnarray}$ Steinen. Dann wissen wir $\begin{eqnarray} h_3(n)=2^n-1 \end{eqnarray}$ . Man kann leicht abschätzen $\begin{eqnarray} h_4(2n-1) &\leq& 2[h_3(n-1)+h_3(n-1)]+1 = 2^{n+1}-3\\ h_4(2n) &\leq& 2[h_3(n)+h_3(n-1)]+1 = 3[2^n-1] \end{eqnarray}$ für alle $\begin{eqnarray} n\geq 1 \end{eqnarray}$ . Ich denke sogar, dass statt < sogar = gilt, aber dazu habe ich noch keinen wasserdichten Beweis. @Werner Großmütig wie ich bin, verzeihe ich dir. EDIT: Ich korrigiere mich - es sind wohl doch bloß obere Schranken. EDIT2: Etwas genauere Abschätzungen bringen folgendes: $\begin{eqnarray} h_4(n) \leq \min\limits_{1\leq m\leq n-1} \left[ 2h_4(m)+h_3(n-m) \right] \end{eqnarray}$ Die ersten paar Werte: $\begin{eqnarray} \end{eqnarray}\begin{tabular}{\|l\|lllllllllll\|}\hline $n$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11\\ \hline $h_4(n)\leq$ & 1 & 3 & 5 & 9 & 13 & 17 & 25 & 33 & 41 & 49 & 65\\ \hline \end{tabular}\begin{eqnarray} \end{eqnarray}$ Das läuft auf $\begin{eqnarray} h_4\left( \frac{n(n+1)}{2}+k \right) \leq (n-1+k)2^n+1,\quad k=0,1,\ldots,n \end{eqnarray}$ hinaus. Aber ob das jetzt optimal ist, habe ich noch meine Zweifel.
Anzeige

07.10.2005, 18:56	riwe	Auf diesen Beitrag antworten »
[quote]Original von Arthur Dent @Werner Großmütig wie ich bin, verzeihe ich dir. ich danke dir werner
07.10.2005, 19:11	AD	Auf diesen Beitrag antworten »
Nachdem mir das Problem mit 4 Pfosten unbekannt war, habe ich ja oben etwas rumgebastelt. Jetzt konnte ich mich doch nicht mehr beherrschen und habe etwas recherchiert - Ergebnis: Laut http://mathworld.wolfram.com/TowerofHanoi.html kann ich bei meinen letzten Betrachtungen dann wohl doch = setzen.
07.10.2005, 19:35	Mathespezialschüler	Auf diesen Beitrag antworten »
Und damit auch alles Leser wissen, worum es geht, nun auch endlich mal eine Beschreibung des Spiels. Gruß MSS
07.10.2005, 21:52	SnIper	Auf diesen Beitrag antworten »
Danke für die netten und hilfreichen Antworten, jedoch verstehe ich den Lösungsansatz nicht genau. Könntet ihr in knappen Worten fassen wie man zu dem Lösungsansatz kommt?
07.10.2005, 23:11	AD	Auf diesen Beitrag antworten »
Ok, zentral ist erstmal das Verständnis der für alle $\begin{eqnarray} n\geq 2 \end{eqnarray}$ gültigen Rekursionsformel $\begin{eqnarray} h_4(n) \leq \min\limits_{1\leq m\leq n-1} \left[ 2h_4(m)+h_3(n-m) \right] \hspace{10ex} () \end{eqnarray}$ Erläuterung: Du willst $\begin{eqnarray} n \end{eqnarray}$ Steine von Pfosten 1 nach Pfosten 4 schaffen. Eine mögliche Strategie dafür ist, zunächst die obersten $\begin{eqnarray} m \end{eqnarray}$ Steine nach Pfosten 2 zu bringen. Dafür stehen alle 4 Pfosten zur Verfügung, also ist das in $\begin{eqnarray} h_4(m) \end{eqnarray}$ Schritten schaffbar. Die restlichen $\begin{eqnarray} n-m \end{eqnarray}$ Steine schaffst du jetzt von Pfosten 1 nach Pfosten 4 unter Verwendung des "Zwischenpfostens" 3 (Pfosten 2 ist hierzu nicht verfügbar!), das ist das ursprüngliche 3-Pfosten-Hanoiproblem, also schaffst du das in $\begin{eqnarray} h_3(n-m) \end{eqnarray}$ Schritten. Schließlich schaffst du die $\begin{eqnarray} m \end{eqnarray}$ Steine von Pfosten 2 nach Pfosten 4, was wiederum $\begin{eqnarray} h_4(m) \end{eqnarray}$ Schritte dauert. Summa summarum ergeben sich für diese ganz spezielle Strategie also $\begin{eqnarray} 2h_4(m)+h_3(n-m) \end{eqnarray}$ Schritte. Wir wissen aber bisher nicht, ob es nicht möglicherweise eine andere, bessere Strategie als diese gibt, also können wir daraus nur folgern $\begin{eqnarray} h_4(n) \leq 2h_4(m)+h_3(n-m) \end{eqnarray}$ . Nun kann man aber noch die Anzahl $\begin{eqnarray} m \end{eqnarray}$ zwischen $\begin{eqnarray} 1 \end{eqnarray}$ und $\begin{eqnarray} n-1 \end{eqnarray}$ variieren lassen, und davon dasjenige $\begin{eqnarray} m \end{eqnarray}$ mit der kleinsten Gesamtschrittzahl nehmen, daher noch die Minimumbildung, die letztendlich zu () führt. Beim ersten Durchlesen von http://mathworld.wolfram.com/TowerofHanoi.html hab ich oben glatt übersehen, dass die Gleichheit in () bisher nur vermutet wird, bewiesen hat sie noch keiner. Ein Gegenbeispiel wurde aber bisher wohl auch nicht gefunden. Und von dieser rekursiven Darstellung auf die explizite zu kommen, ist eine ganz andere Geschichte, die ich hier lieber erstmal ausblende. Jedenfalls kann man die angegebene Darstellung mit vollständiger Induktion unter Nutzung von () und $\begin{eqnarray} h_3(k)=2^k-1 \end{eqnarray*}$ beweisen.
08.10.2005, 12:01	SnIper	Auf diesen Beitrag antworten »
Hi Arthur und alle anderen danke für deine Beschreibung, sie hat mir echt geholfen das mit den 4 Pfosten mehr zu verstehen. Du hast erwähnt dass es einen Beweise gibt, dass (2^n)-1 die Mindestanzahl der Züge auf 3 Pfosten ist. Wo finde ich diesen Beweis??? Danke
08.10.2005, 12:31	riwe	Auf diesen Beitrag antworten »
z.b. hier werner
09.10.2005, 14:50	AD	Auf diesen Beitrag antworten »
Beim nochmaligen Überdenken kommt man mit dem obigen Prinzip auch für beliebige $\begin{eqnarray} k\geq 4 \end{eqnarray}$ Pfosten zum Resultat $\begin{eqnarray} H_k(1)=1;\quad H_k(n) = \min\limits_{1\leq m\leq n-1} \bigg[ 2H_k(m)+H_{k-1}(n-m) \bigg],\qquad n\geq 2,\,k\geq 4 \end{eqnarray}$ , wobei $\begin{eqnarray} H_k(n) \end{eqnarray}$ eine obere Schranke für die Minimalanzahl $\begin{eqnarray} h_k(n) \end{eqnarray}$ darstellen soll. Start für $\begin{eqnarray} k=3 \end{eqnarray}$ ist der gewöhnliche Hanoi-Turm $\begin{eqnarray} h_3(n)=H_3(n)=2^n-1 \end{eqnarray}$ . Für $\begin{eqnarray} k=4 \end{eqnarray}$ wird (wie oben erwähnt) $\begin{eqnarray} h_4(n)=H_4(n) \end{eqnarray}$ vermutet; wie das für $\begin{eqnarray} k\geq 5 \end{eqnarray}$ aussieht - keine Ahnung...

Neue Frage »

Antworten »

Türme von Hanoi mit vier Pfosten

Verwandte Themen