Der Turm Hanois (hat auch den Turm von Brahmas Turm oder Lucas, und manchmal pluralised genannt), ist ein mathematisches Spiel oder Rätsel. Es besteht aus drei Stangen und mehreren Platten verschiedener Größen, die auf jede Stange gleiten können. Das Rätsel fängt mit den Platten in einem ordentlichen Stapel an, der der Größe auf einer Stange, das kleinste oben in aufsteigender Reihenfolge ist, so eine konische Gestalt machend.

Das Ziel des Rätsels ist, den kompletten Stapel zu einer anderen Stange zu bewegen, den folgenden Regeln folgend:

• Nur eine Platte kann auf einmal bewegt werden.
• Jede Bewegung besteht daraus, die obere Platte von einer der Stangen zu nehmen und es auf eine andere Stange oben auf den anderen Platten gleiten zu lassen, die bereits auf dieser Stange da sein können.
• Keine Platte darf oben auf einer kleineren Platte gelegt werden.

Mit drei Platten kann das Rätsel in sieben Bewegungen gelöst werden.

Ursprünge

Das Rätsel wurde vom französischen Mathematiker Édouard Lucas 1883 erfunden. Es gibt eine Legende über einen Indianertempel, der ein großes Zimmer mit drei abgenutzten Posten darin umgeben durch 64 goldene Platten enthält. Brahmane-Priester, den Befehl einer alten Vorhersage vorspielend, haben diese Platten in Übereinstimmung mit den Regeln des Rätsels seit dieser Zeit bewegt. Das Rätsel ist deshalb auch bekannt als der Turm des Rätsels von Brahma. Gemäß der Legende, wenn die letzte Bewegung des Rätsels vollendet wird, wird die Welt enden. Es ist nicht klar, ob Lucas diese Legende erfunden hat oder dadurch begeistert wurde.

Wenn die Legende wahr wäre, und wenn die Priester im Stande wären, Platten an einer Rate von einer pro Sekunde mit der kleinsten Zahl von Bewegungen zu bewegen, würden sie 21 Sekunden oder ungefähr 585 Milliarden Jahre oder 18,446,744,073,709,551,615 Umdrehungen brauchen fertig zu sein.

Es gibt viele Schwankungen auf dieser Legende. Zum Beispiel, in einem tellings, ist der Tempel ein Kloster, und die Priester sind Mönche. Wie man sagen kann, sind der Tempel oder das Kloster in verschiedenen Teilen der Welt — einschließlich Hanois, Vietnam, und können mit jeder Religion vereinigt werden. In einigen Versionen werden andere Elemente wie die Tatsache eingeführt, dass der Turm am Anfang der Welt geschaffen wurde, oder dass die Priester oder Mönche nur eine Bewegung pro Tag machen können.

Lösung

Das Rätsel kann mit jeder Zahl von Platten gespielt werden, obwohl viele Spielzeugversionen ungefähr sieben bis neun von ihnen haben. Das Spiel scheint unmöglich vielen Anfängern, noch ist mit einem einfachen Algorithmus lösbar. Die Zahl von Bewegungen, die erforderlich sind, einen Turm des Hanoier Rätsels zu lösen, ist 2 - 1, wo n die Zahl von Platten ist.

Wiederholende Lösung

Die folgende Lösung ist eine einfache Lösung für das Spielzeugrätsel.

Abwechselnde Bewegungen zwischen dem kleinsten Stück und einem nichtkleinsten Stück. Wenn Sie das kleinste Stück bewegen, bewegen Sie es immer zur folgenden Position in derselben Richtung (nach rechts, wenn die Startzahl von Stücken sogar nach links ist, wenn die Startzahl von Stücken seltsam ist). Wenn es keine Turm-Position in der gewählten Richtung gibt, bewegen Sie das Stück zum entgegengesetzten Ende, aber dann setzen Sie fort, sich in der richtigen Richtung zu bewegen. Zum Beispiel, wenn Sie mit drei Stücken anfangen würden, würden Sie das kleinste Stück zum entgegengesetzten Ende bewegen, dann in der linken Richtung danach weitermachen. Wenn die Umdrehung ist, das nichtkleinste Stück zu bewegen, gibt es nur eine gesetzliche Bewegung. Das Tun davon wird das Rätsel mit wenigster Zahl von Bewegungen vollenden, um so zu tun.

Es sollte vielleicht bemerkt werden, dass das als ein auffallend elegantes Regelwerk umgeschrieben werden kann:

Einfachere Behauptung der wiederholenden Lösung

Wenn Sie

zwischen dem kleinsten und den nächst-kleinsten Platten abwechseln, folgen Sie den Schritten für den passenden Fall:

Für eine gerade Zahl von Platten:

• machen Sie die gesetzliche Bewegung zwischen Haken A und B
• machen Sie die gesetzliche Bewegung zwischen Haken A und C
• machen Sie die gesetzliche Bewegung zwischen Haken B und C
• wiederholen Sie sich bis zu ganzem

Für eine ungerade Zahl von Platten:

machen Sie die gesetzliche Bewegung zwischen Haken A und C machen Sie die gesetzliche Bewegung zwischen Haken A und B machen Sie die gesetzliche Bewegung zwischen Haken B und C wiederholen Sie sich bis zu ganzem

In jedem Fall werden insgesamt 2-1 Bewegungen gemacht.

Gleichwertige wiederholende Lösung

Eine andere Weise, die einzigartige optimale wiederholende Lösung zu erzeugen, ist, die Platten 1 durch n zu numerieren, der zum kleinsten am größten ist. Wenn n seltsam ist, ist die erste Bewegung vom Anfang bis den Schluss-Haken, und wenn n sogar die erste Bewegung ist, ist vom Anfang bis den Verwenden-Haken.

Fügen Sie jetzt die Einschränkung hinzu, dass keine sonderbare Platte direkt auf einer sonderbaren Platte gelegt werden darf, und keine gleiche Platte direkt auf einer gleichen Platte gelegt werden darf. Mit dieser Extraeinschränkung und der offensichtlichen Regel, nie Ihre letzte Bewegung aufzumachen, gibt es nur eine Bewegung andauernd. Die Folge dieser einzigartigen Bewegungen ist eine optimale Lösung des Problems, das zur wiederholenden Lösung gleichwertig ist, die oben beschrieben ist.

Rekursive Lösung

Ein Schlüssel zum Lösen dieses Rätsels soll anerkennen, dass es durch das Zerbrechen des Problems unten in eine Sammlung von kleineren Problemen und weiter das Zerbrechen jener Probleme unten in noch kleinere Probleme gelöst werden kann, bis eine Lösung erreicht wird. Das folgende Verfahren demonstriert diese Annäherung.

• etikettieren Sie die Haken A, B, C — diese Etiketten können sich an verschiedenen Schritten bewegen
• lassen Sie n die Gesamtzahl von Scheiben sein
• numerieren Sie die Scheiben von 1 (am kleinsten, höchst) zu n (am größten, allerunterst)

N Scheiben vom Haken zu bewegen, um C anzupflocken:

1. bewegen Sie n1 Scheiben von bis B. Das verlässt Scheibe n allein auf dem Haken Ein
2. bewegen Sie Scheibe n von bis C
3. bewegen Sie n1 Scheiben von B bis C, so sitzen sie auf der Scheibe n

Der obengenannte ist ein rekursiver Algorithmus: Um Schritte 1 und 3 auszuführen, wenden Sie denselben Algorithmus wieder für n1 an. Das komplette Verfahren ist eine begrenzte Zahl von Schritten, seitdem an einem Punkt wird der Algorithmus für n = 1 erforderlich sein. Dieser Schritt, eine einzelne Scheibe vom Haken bewegend, um B anzupflocken, ist trivial. Diese Annäherung kann ein strenger mathematischer Formalismus mit der Theorie der dynamischen Programmierung gegeben werden, und wird häufig als ein Beispiel von recursion verwendet, wenn man Programmierung unterrichtet.

Logische Analyse der rekursiven Lösung

Als in vielen mathematischen Rätseln, eine Lösung findend, wird leichter durch das Beheben eines ein bisschen allgemeineren Problems gemacht: Wie man einen Turm von h (h=height) bewegt, pflocken Platten von einem Starthaken (f=from) auf einen Bestimmungsort C (t=to), B an der restliche dritte Haken und das Annehmen tf zu sein. Bemerken Sie erstens, dass das Problem für Versetzungen der Namen der Haken (symmetrische Gruppe S) symmetrisch ist. Wenn eine Lösung bekannt ist, sich vom Haken bewegend, um C anzupflocken, dann, durch die Umbenennung der Haken, kann dieselbe Lösung für jede andere Wahl des Startens und Bestimmungsort-Hakens verwendet werden. Wenn es nur eine Platte gibt (oder sogar niemand überhaupt), ist das Problem trivial. Wenn h=1, dann einfach bewegen die Platte vom Haken, um C anzupflocken. Wenn h> 1, dann irgendwo entlang der Folge von Bewegungen, die größte Platte vom Haken zu einem anderen Haken bewegt werden muss, um vorzugsweise C anzupflocken. Die einzige Situation, die diese Bewegung erlaubt, besteht darin, wenn alle kleineren h-1 Platten auf dem Haken B sind. Folglich zuerst müssen alle h-1 kleineren Platten von bis B gehen. Bewegen Sie nachher die größte Platte und bewegen Sie schließlich die h-1 kleineren Platten vom Haken B, um C anzupflocken. Die Anwesenheit der größten Platte behindert keine Bewegung der h-1 kleineren Platten und kann provisorisch ignoriert werden. Jetzt wird das Problem auf das Bewegen h-1 Platten von einem Haken bis einen anderen, zuerst von bis B und nachher von B bis C reduziert, aber dieselbe Methode kann beide Male durch die Umbenennung der Haken verwendet werden. Dieselbe Strategie kann verwendet werden, um das h-1 Problem auf h-2, h-3 und so weiter zu reduzieren, bis nur eine Platte verlassen wird. Das wird recursion genannt. Dieser Algorithmus kann schematized wie folgt sein. Identifizieren Sie die Platten in der Größenordnung von der zunehmenden Größe durch die natürlichen Zahlen von 0 bis zu, aber nicht einschließlich h. Folglich ist Platte 0 die kleinste und Platte h-1 die größte.

Der folgende ist ein Verfahren, für einen Turm von h Platten von einem Haken auf einen Haken C mit B zu bewegen, der restliche dritte Haken zu sein:

• Schritt 1: Wenn h> der 1 dann erste Gebrauch dieses Verfahren, um die h-1 kleineren Platten vom Haken zu bewegen, um B anzupflocken.
• Schritt 2: Jetzt kann die größte Platte, d. h. Platte h-1 vom Haken bewegt werden, um C anzupflocken.
• Schritt 3: Wenn h> 1 andererseits Gebrauch dieses Verfahren, um die h-1 kleineren Platten vom Haken B zu bewegen, um C anzupflocken.

Mittels der mathematischen Induktion wird es leicht bewiesen, dass das obengenannte Verfahren die minimale Zahl von Bewegungen möglich verlangt, und dass die erzeugte Lösung die einzige mit dieser minimalen Zahl von Bewegungen ist. Mit Wiederauftreten-Beziehungen kann die genaue Zahl von Bewegungen, die diese Lösung verlangt, berechnet werden durch:. Dieses Ergebnis wird durch die Anmerkung erhalten, dass Schritte 1 und 3 Bewegungen nehmen, und Schritt 2 eine Bewegung nimmt, gebend.

Nichtrekursive Lösung

Die Liste von Bewegungen für einen Turm, der von einem Haken auf einen anderen, wie erzeugt, durch den rekursiven Algorithmus wird trägt, hat viele Regelmäßigkeit. Wenn sie die Bewegungen aufzählt, die von 1, die Ordnungszahl der während der Bewegung zu bewegenden Platte anfangen, ist M die Zahl von Zeiten M kann durch 2 geteilt werden. Folglich schließt jede sonderbare Bewegung die kleinste Platte ein. Es kann auch bemerkt werden, dass die kleinste Platte die Haken f, t, r, f, t, r usw. für die sonderbare Höhe des Turms überquert und die Haken f, r, t, f, r, t usw. für sogar die Höhe des Turms überquert. Das stellt den folgenden Algorithmus zur Verfügung, der leichter, mit der Hand ausgeführt ist als der rekursive Algorithmus.

In abwechselnden Bewegungen:

• bewegen Sie die kleinste Platte zum Haken es ist nicht kürzlich hergekommen.
• bewegen Sie eine andere Platte gesetzlich (es wird eine Möglichkeit geben nur)

Für die allererste Bewegung geht die kleinste Platte, um t anzupflocken, wenn h seltsam ist und r anzupflocken, wenn h gleich ist.

Bemerken Sie auch dass:

• Platten, deren Ordnungszahlen Bewegung der geraden Bitzahl in demselben Sinn wie die kleinste Platte haben.
• Platten, deren Ordnungszahlen sonderbare Paritätsbewegung im entgegengesetzten Sinn haben.
• Wenn h sogar ist, ist der restliche dritte Haken während aufeinander folgender Bewegungen t, r, f, t, r, f usw.
• Wenn h seltsam ist, ist der restliche dritte Haken während aufeinander folgender Bewegungen r, t, f, r, t, f usw.

Mit diesen Kenntnissen kann eine Reihe von Platten in der Mitte einer optimalen Lösung ohne mehr Zustandinformation wieder erlangt werden als die Positionen jeder Platte:

• Nennen Sie die Bewegungen ausführlich berichtet über 'einer natürlichen' Bewegung einer Platte.
• Untersuchen Sie die kleinste Spitzenplatte, die nicht Platte 0 ist, und bemerken Sie, wie seine einzige (gesetzliche) Bewegung sein würde: (Wenn es keine solche Scheibe gibt, dann sind wir entweder an der ersten oder letzten Bewegung).
• Wenn diese Bewegung 'die natürliche' Bewegung der Platte ist, dann ist die Scheibe nicht bewegt worden seit der letzten Scheibe sollten 0 Bewegung und diese Bewegung genommen werden.
• Wenn diese Bewegung nicht 'die natürliche' Bewegung der Platte ist, dann bewegen Sie Platte 0.

Binäre Lösungen

Plattenpositionen können mehr direkt von der Dualzahl bestimmt werden (stützen Sie 2) die Darstellung der Bewegungszahl (der anfängliche Staat, der Bewegung #0, mit allen Ziffern 0 und dem Endstaat ist #21, mit allen Ziffern 1 zu sein) mit den folgenden Regeln:

• Es gibt eine binäre Ziffer (Bit) für jede Platte
• Das bedeutendste (leftmost) hat gebissen vertritt die größte Platte. Ein Wert von 0 zeigt an, dass die größte Platte auf dem anfänglichen Haken ist, während 1 anzeigt, dass es auf dem Endhaken ist.
• Der bitstring wird vom linken bis Recht gelesen, und jedes Bit kann verwendet werden, um die Position der entsprechenden Platte zu bestimmen.
• Ein bisschen mit demselben Wert wie bedeutet der vorherige, dass die entsprechende Platte auf der Spitze die vorherige Platte auf demselben Haken aufgeschobert wird.
• (Das heißt: Eine gerade Folge 1's oder die Mittel von 0's, dass die entsprechenden Platten alle auf demselben Haken sind).
• Ein bisschen mit einem verschiedenen Wert zu den vorherigen-Mitteln, dass die entsprechende Platte eine Position nach links oder Recht auf das vorherige ist. Ob es verlassen wird oder Recht durch diese Regel bestimmt wird:
• Nehmen Sie an, dass der anfängliche Haken links ist und der Endhaken rechts ist.
• Nehmen Sie auch "Verpackung" - so die richtigen Haken-Zählungen als ein Haken an, der des linken Hakens, und umgekehrt "verlassen" ist".
• Lassen Sie n die Zahl von größeren Platten sein, die auf demselben Haken wie ihre erste größere Platte gelegen werden und 1 beitragen, wenn die größte Platte auf dem linken Haken ist. Wenn n sogar ist, wird die Platte ein Haken nach links gelegen, wenn n seltsam ist, hat die Platte einen Haken nach rechts ausfindig gemacht.

Zum Beispiel, in einem 8-Platten-Hanoi:

• Bewegen Sie 0
• Die größte Platte ist 0, so ist es auf dem linken (anfänglichen) Haken.
• Alle anderen Platten sind 0 ebenso, so werden sie obendrein aufgeschobert. Folglich sind alle Platten auf dem anfänglichen Haken.
• Bewegen Sie 2-1
• Die größte Platte ist 1, so ist es auf dem richtigen (endgültigen) Haken.
• Alle anderen Platten sind 1 ebenso, so werden sie obendrein aufgeschobert. Folglich sind alle Platten auf dem Endhaken, und das Rätsel ist abgeschlossen.
• Bewegen Sie sich 011011000 = 216

Die größte Platte ist 1, so ist es auf dem richtigen (endgültigen) Haken.

• Platte zwei ist auch 1, so wird sie obendrein auf dem richtigen Haken aufgeschobert.
• Platte drei ist 0, so ist es auf einem anderen Haken. Da n (n=3) seltsam ist, ist es ein Haken nach rechts, d. h. auf dem linken Haken.
• Platte vier ist 1, so ist es auf einem anderen Haken. Da n sogar (n=2) ist, ist es ein Haken nach links, d. h. auf dem richtigen Haken.
• Platte fünf ist auch 1, so wird sie obendrein auf dem richtigen Haken aufgeschobert.
• Platte sechs ist 0, so ist es auf einem anderen Haken. Da n (n=5) seltsam ist, ist die Platte ein Haken nach rechts, d. h. auf dem linken Haken.
• Platten sieben und acht sind auch 0, so werden sie obendrein auf dem linken Haken aufgeschobert.

Die Quelle und Bestimmungsort-Haken für die Mth-Bewegung können auch elegant von der binären Darstellung der M das Verwenden bitwise Operationen gefunden werden. Um die Syntax der C Programmiersprache zu verwenden, bewegen Sie sich M ist vom Haken bis Haken, wo die Platten auf dem Haken 0 und Schluss auf dem Haken 1 oder 2 je nachdem, wie beginnen, ob die Zahl von Platten sogar oder seltsam ist. Eine andere Formulierung ist vom Haken bis Haken.

Außerdem wird die zu bewegende Platte durch die Zahl von Zeiten bestimmt der Bewegungspunkt der Klagebegründung (m) kann durch 2 (d. h. die Zahl von Nullbit am Recht) geteilt werden, die erste Bewegung als 1 aufzählend und die Platten durch die Nummern 0, 1, 2 usw. in der Größenordnung von der zunehmenden Größe identifizierend. Das erlaubt einer sehr schnellen nichtrekursiven Computerdurchführung, die Positionen der Platten nach der M Bewegungen ohne Berücksichtigung jeder vorherigen Bewegung oder Vertriebs von Platten zu finden.

Die Zählung, die Nullen (ctz) Operation schleppt, die die Zahl von Konsekutivnullen am Ende einer Binärzahl aufzählt, gibt eine einfache Lösung des Problems: Die Platten werden von der Null, und an der Bewegung M numeriert, Plattenzahl ctz (m) wird die minimale mögliche Entfernung nach rechts bewegt (zurück ringsherum nach links, wie erforderlich, kreisend).

Graue Codelösung

Das binäre Ziffer-System von Codes von Gray gibt eine Alternative weg, das Rätsel zu lösen. Im System von Gray werden Zahlen in einer binären Kombination von 0s und 1s ausgedrückt, aber anstatt ein Standardstellungsziffer-System zu sein, funktioniert Code von Gray auf der Proposition, dass sich jeder Wert von seinem Vorgänger durch nur einen (und genau einen) geändertes Bit unterscheidet. Die Zahl der Bit-Gegenwart im Code von Gray ist wichtig, und Hauptnullen sind unterschiedlich in Stellungssystemen nicht fakultativ.

Wenn man im Code von Gray von wenig Größe zählt, die der Zahl von Platten in einem besonderen Turm Hanois gleich ist, an der Null beginnt und zusammenzählt, dann hat sich das Bit geändert jede Bewegung entspricht der Platte, um sich zu bewegen, wo das "am wenigsten bedeutende Bit" die kleinste Platte ist und das "bedeutendste Bit" am größten ist.

:Counting-Bewegungen von 1 und das Identifizieren der Platten durch Zahlen, die von 0 in der Größenordnung von der zunehmenden Größe, der Ordnungszahl der Platte anfangen, die während der Bewegung zu bewegen ist, M ist die Zahl von Zeiten M, können durch 2 geteilt werden.

Diese Technik identifiziert sich, welche Platte zu bewegen, aber nicht, wohin man es dazu bewegt. Für die kleinste Platte gibt es immer zwei Möglichkeiten. Für die anderen Platten gibt es immer eine Möglichkeit, außer, wenn alle Platten auf demselben Haken sind, aber in diesem Fall ist entweder es die kleinste Platte, die bewegt werden muss oder das Ziel, ist bereits erreicht worden. Glücklicherweise gibt es eine Regel, die wirklich sagt, wohin man die kleinste Platte dazu bewegt. Lassen Sie f der Starthaken, t der Bestimmungsort-Haken und r der restliche dritte Haken sein. Wenn die Zahl von Platten, die kleinsten Plattenzyklen entlang den Haken in der Ordnung f-> t-> r-> f-> t-> r usw. seltsam ist. Wenn die Zahl von Platten sogar ist, muss das umgekehrt werden: f-> r-> t-> f-> r-> t usw.

Sehlösung

Eine Sehlösung kann durch das Schauen nah auf ein Lineal mit Reichsmaßen entdeckt werden. Diese werden normalerweise in progressiv kleinere Zeichen von 1 Zoll, 1/2 Zoll, 1/4 Zoll, 1/8 Zoll, 1/16 Zoll und 1/32 zöllige Abteilungen unterteilt. Wie man betrachten kann, entsprechen diese den progressiv kleineren Scheiben.

Mit der kleinsten Abteilung entsprechend der kleinsten Scheibe, jedem Schritt entlang den Lineal-Shows beginnend, welche Scheibe als nächstes bewegt wird. Ein allgemeines Lineal mit 1/32 zölligen Abteilungen kann verwendet werden, um einen Turm des Hanoier Rätsels mit bis zu sechs Scheiben zu lösen.

Bemerken Sie, dass das nur einen Schlüssel für die Folge von Scheibe-Bewegungen, nicht ihre Richtung zur Verfügung stellt. Wie erwähnt, früher sollte die kleinste Scheibe immer durch Haken A, B, C, dann zurück zu (oder C, B, A, dann zurück zu C) periodisch wiederholt werden.

Grafische Darstellung

Das Spiel kann durch einen ungeleiteten Graphen, die Knoten vertreten werden, die Vertrieb von Platten und den Rändern vertreten, die Bewegungen vertreten. Für eine Platte ist der Graph ein Dreieck:

Der Graph für 2 Platten ist 3 in einem größeren Dreieck eingeordnete Dreiecke:

Die Knoten an den Scheitelpunkten des äußersten Dreiecks vertreten Vertrieb mit allen Platten auf demselben Haken.

Für h+1 Platten, nehmen Sie den Graphen von h Platten und ersetzen Sie jedes kleine Dreieck durch den Graphen für 2 Platten.

Für 3 Platten ist der Graph:

• nennen Sie die Haken a, b und c
• Listenplattenpositionen vom linken bis direkt in der Größenordnung von der zunehmenden Größe

Die Seiten des äußersten Dreiecks vertreten die kürzesten Weisen, einen Turm von einem Haken bis einen anderen zu bewegen. Der Rand in der Mitte der Seiten des größten Dreiecks vertritt eine Bewegung der größten Platte. Der Rand in der Mitte der Seiten jedes folgenden kleineren Dreiecks vertritt eine Bewegung jeder folgenden kleineren Platte. Die Seiten der kleinsten Dreiecke vertreten Bewegungen der kleinsten Platte.

Im Allgemeinen, für ein Rätsel mit n Platten, gibt es 3 Knoten im Graphen; jeder Knoten hat drei Ränder zu anderen Knoten außer den drei Eckknoten, die zwei haben: Es ist immer möglich, die kleinste Platte zu demjenigen der zwei anderen Haken zu bewegen; und es ist möglich, eine Platte zwischen jenen zwei Haken außer in der Situation zu bewegen, wo alle Platten auf einem Haken aufgeschobert werden. Die Eckknoten vertreten die drei Fälle, wo alle Platten auf einem Haken aufgeschobert werden. Das Diagramm für n + 1 Platten wird durch die Einnahme von drei Kopien des N-Plattendiagramms — jedem erhalten, alle Staaten und Bewegungen der kleineren Platten für eine besondere Position der neuen größten Platte vertretend — und sich ihnen an den Ecken mit drei neuen Rändern anschließend, die nur drei Gelegenheiten vertretend, die größte Platte zu bewegen. Die resultierende Zahl hat so 3 Knoten und hat noch drei Ecken, die mit nur zwei Rändern bleiben.

Da mehr Platten hinzugefügt werden, wird die Graph-Darstellung des Spiels der Zahl von Fractal, Dreieck von Sierpiński ähneln. Es ist klar, dass die große Mehrheit von Positionen im Rätsel nie erreicht wird, wenn sie die kürzestmögliche Lösung verwenden wird; tatsächlich, wenn die Priester der Legende die längstmögliche Lösung verwenden (ohne jede Position wieder zu besuchen), wird es sie 3 &minus nehmen; 1 Bewegungen, oder mehr als 10 Jahre.

Der längste nichtwiederholende Weg für drei Platten kann durch das Auslöschen der unbenutzten Ränder vergegenwärtigt werden:

Beiläufig kann dieser längste nichtwiederholende Pfad durch das Verbieten aller Bewegungen von bis b erhalten werden.

Der kreisförmige Pfad von Hamiltonian für drei Platten ist:

Die Graphen zeigen klar dass:

• Von jedem willkürlichen Vertrieb von Platten gibt es genau eine kürzeste Weise, alle Platten auf einen der drei Haken überzugehen.
• Zwischen jedem Paar des willkürlichen Vertriebs von Platten gibt es einen oder zwei verschiedene kürzeste Pfade.
• Von jedem willkürlichen Vertrieb von Platten gibt es ein oder zwei verschiedene längste nicht sich selbsttreffende Pfade, um alle Platten zu einem der drei Haken zu bewegen.
• Zwischen jedem Paar des willkürlichen Vertriebs von Platten gibt es ein oder zwei verschiedene längste nicht sich selbsttreffende Pfade.
• Lassen Sie N die Zahl von sich nicht selbsttreffenden Pfaden sein, für einen Turm von h Platten von einem Haken bis einen anderen zu bewegen. Dann:
• N = 2
• N = (N) + (N).
• Zum Beispiel: N 

1.5456×10

Anwendungen

Der Turm Hanois wird oft in der psychologischen Forschung über das Problem-Lösen verwendet. Dort auch besteht eine Variante dieser Aufgabe genannt der Turm Londons für die neuropsychological Diagnose und Behandlung von Exekutivfunktionen.

Der Turm Hanois wird auch als Aushilfsfolge-Schema verwendet, wenn man Computerdatenunterstützungen durchführt, wo vielfache Bänder/Medien beteiligt werden.

Wie oben erwähnt ist der Turm Hanois populär, um rekursive Algorithmen zum Anfang zu unterrichten, Studenten programmierend. Eine bildliche Version dieses Rätsels wird in den emacs Redakteur programmiert, der durch das Schreiben von M-x Hanoi zugegriffen ist. Es gibt auch einen in der Einleitung geschriebenen Beispielalgorithmus.

Der Turm Hanois wird auch als ein Test durch neuropsychologists verwendet, der versucht, frontale Lappen-Defizite zu bewerten.

Allgemeine kürzeste Pfade und die Nummer 466/885

Eine neugierige Generalisation der ursprünglichen Absicht des Rätsels ist, von einer gegebenen Konfiguration der Platten anzufangen, wo alle Platten nicht notwendigerweise auf demselben Haken sind, und in eine minimale Zahl von Bewegungen an einer anderen gegebenen Konfiguration anzukommen. Im Allgemeinen kann es ziemlich schwierig sein, eine kürzeste Folge von Bewegungen zu schätzen, um dieses Problem zu beheben. Eine Lösung wurde von Andreas Hinz vorgeschlagen, und basiert auf der Beobachtung, dass in einer kürzesten Folge von Bewegungen sich die größte Platte, die bewegt werden muss (offensichtlich kann man alle größten Platten ignorieren, die denselben Haken sowohl in den anfänglichen als auch in endgültigen Konfigurationen besetzen werden), entweder genau einmal oder genau zweimal bewegen wird.

Die mit diesem verallgemeinerten Problem verbundene Mathematik wird noch interessanter, wenn man die durchschnittliche Zahl von Bewegungen in einer kürzesten Folge von Bewegungen zwischen zwei anfänglichen und endgültigen Plattenkonfigurationen denkt, die aufs Geratewohl gewählt werden. Hinz und Chan Hat-Tung haben unabhängig entdeckt

(sieh auch,

Kapitel 1, p. 14)

dass die durchschnittliche Zahl von Bewegungen in einem N-Plattenturm durch die folgende genaue Formel gegeben wird:

:

\left (\frac {12} {29} + \frac {18} {1003 }\\sqrt {17 }\\Recht) \left (\frac {5 +\sqrt {17}} {18 }\\Recht) ^n +

\left (\frac {12} {29} - \frac {18} {1003 }\\sqrt {17 }\\Recht) \left (\frac {5-\sqrt {17}} {18 }\\Recht) ^n. </math>

Bemerken Sie, dass für großen genug n nur die ersten und zweiten Begriffe zur Null nicht zusammenlaufen, so bekommen wir einen asymptotischen Ausdruck: als. So intuitiv konnten wir den Bruchteil dessen interpretieren, weil das Darstellen des Verhältnisses des Arbeits-leisten muss, wenn es von einer zufällig gewählten Konfiguration bis eine andere zufällig gewählte Konfiguration hinsichtlich der Schwierigkeit der Notwendigkeit geht, den "schwierigsten" Pfad der Länge zu durchqueren, die das Bewegen aller Platten von einem Haken bis einen anderen einschließt. Eine alternative Erklärung für das Äußere des unveränderlichen 466/885, sowie ein neuer und etwas verbesserter Algorithmus, für den kürzesten Pfad zu schätzen, wurde von Romik gegeben.

Schwankungen

Das zyklische Hanoi

Das zyklische Hanoi ist eine Schwankung Hanois, in dem jede Platte in derselben zyklischen Richtung in den meisten Fällen im Uhrzeigersinn bewegt werden muss. Zum Beispiel, in Anbetracht einer drei Standardhaken-Einstellung, kann eine gegebene Platte vom Haken bewegt werden, um B, dann von B bis C, C zu A usw. anzupflocken. Das kann mit zwei gegenseitig rekursiven Verfahren gelöst werden:

N Scheiben im Uhrzeigersinn vom Haken zu bewegen, um C anzupflocken:

1. bewegen Sie n  1 Scheiben im Uhrzeigersinn von zu C
2. bewegen Sie Scheibe #n von bis B
3. bewegen Sie n  1 Scheiben gegen den Uhrzeigersinn von C bis Einen
4. bewegen Sie Scheibe #n von B bis C

bewegen Sie n  1 Scheiben im Uhrzeigersinn von zu C

N Scheiben gegen den Uhrzeigersinn vom Haken zu bewegen, um C anzupflocken:

1. bewegen Sie n  1 Scheiben im Uhrzeigersinn von zu B
2. bewegen Sie Scheibe #n von bis C
3. bewegen Sie n  1 Scheiben im Uhrzeigersinn von B bis C

Vier Haken und darüber hinaus

Obwohl die Drei-Haken-Version eine einfache rekursive Lösung, wie entworfen, oben hat, die optimale Lösung für den Turm des Hanoier Problems mit vier Haken (hat das Rätsel von Reve genannt), ganz zu schweigen von mehr Haken, ist noch ein offenes Problem. Das ist ein gutes Beispiel dessen, wie ein einfaches, lösbares Problem drastisch schwieriger durch das geringe Lösen von einer der Problem-Einschränkungen gemacht werden kann.

Die Tatsache, dass das Problem mit vier oder mehr Haken ein offenes Problem ist, deutet nicht an, dass kein Algorithmus besteht, um (ganzer) die optimalen Lösungen zu finden. Vertreten Sie einfach das Spiel durch einen ungeleiteten Graphen, die Knoten, die Vertrieb von Platten und den Rändern sind, die Bewegungen sind, und verwenden Sie Breite zuerst suchen, um einen (oder alle) kürzesten Pfad (E) zu finden, der einen Turm von einem Haken auf einen anderen bewegt. Jedoch, sogar schlau durchgeführt auf dem schnellsten jetzt verfügbaren Computer, stellt dieser Algorithmus keinen Weg effektiv rechnender Lösungen für die große Anzahl von Platten zur Verfügung; das Programm würde mehr Zeit und Gedächtnis verlangen als verfügbar. Folglich, sogar einen Algorithmus habend, bleibt es unbekannt, wie viele Bewegungen eine optimale Lösung verlangt, und wie viele optimale Lösungen für 1000 Platten und 10 Haken bestehen.

Obwohl es genau nicht bekannt ist, wie viele Bewegungen gemacht werden müssen, gibt es einige asymptotische Ergebnisse. Es gibt auch "gewagt - optimale Lösung, die" durch den Algorithmus von Frame-Stewart gegeben ist, entdeckt unabhängig durch den Rahmen und Stewart 1941. Die zusammenhängende offene Vermutung von Frame-Stewart behauptet, dass der Algorithmus von Frame-Stewart immer eine optimale Lösung gibt. Der optimality des Algorithmus von Frame-Stewart ist für 4 Haken mit bis zu 30 Platten rechenbetont nachgeprüft worden.

Für andere Varianten des Vier-Haken-Turms des Hanoier Problems, sieh das Überblick-Papier von Paul Stockmeyer.

Algorithmus von Frame-Stewart

Der Algorithmus von Frame-Stewart, eine vermutlich optimale Lösung für vier (oder noch mehr) Haken gebend, wird unten beschrieben:

• Lassen Sie, die Zahl von Platten zu sein.
• Lassen Sie, die Zahl von Haken zu sein.
• Definieren Sie, um die minimale Zahl von Bewegungen zu sein, die erforderlich sind überzuwechseln, n Platten mit r pflockt an

Der Algorithmus kann rekursiv beschrieben werden:

1. Für einige,

1. Ohne den Haken zu stören, der jetzt die Spitzenplatten enthält, übertragen Sie die restlichen Platten dem Bestimmungsort-Haken mit nur die restlichen Haken, Bewegungen nehmend.
2. Übertragen Sie schließlich die Spitzenplatten dem Bestimmungsort-Haken, Bewegungen nehmend.

Der komplette Prozess nimmt Bewegungen. Deshalb sollte die Zählung aufgepickt werden, für den diese Menge minimal ist.

Wie man

wagt, ist dieser Algorithmus (mit der obengenannten Wahl für) optimal, und keine Gegenbeispiele sind bekannt.

Mehrstapel-Türme Hanois

Amerikanische offene Victor Mascolo ausgegebene Nummer 7,566,057 gibt Mehrstapel-Turm von Hanoier Rätseln mit zwei oder mehr Stapeln bekannt und pflockt doppelt so viele als Stapel an. Nach dem Anfang auf einem besonderen Haken versetzt jeder Stapel und wird durch einen verschiedenen farbigen Stapel auf einem anderen Haken versetzt, wenn das Rätsel gelöst wird. Platten einer Farbe haben auch einen anderen Haken, der alle anderen Farben ausschließt, so dass es drei Haken gibt, die für jede Farbenplatte, zwei verfügbar sind, die mit anderen Farben und derjenigen geteilt werden, die nicht geteilt wird. Auf den geteilten Haken darf eine Platte nicht auf einer verschiedenen farbigen Platte derselben Größe, eine Möglichkeit gelegt werden, die im Standardrätsel nicht entsteht.

Das einfachste Mehrstapel-Spiel, der Turm Hanois (2 &times; 4), hat zwei Stapel und vier Haken, und es verlangt 3 [T (n)] bewegt sich, um zu lösen, wo T (n) die Zahl von Bewegungen ist, musste ein einzelnes klassisches Stapel-Werk von n Platten lösen. Das Spiel geht in der Wippe Mode mit der längeren und längeren Reihe von Bewegungen dieser Stellvertreter zwischen Farben weiter. Es schließt in der Rückwippe Mode mit kürzer und kürzer solche Reihe von Bewegungen. Mit der zweiten Reihe von drei Bewegungen anfangend, werden diese abwechselnden Reihen von Bewegungen, die in der Länge für die erste Hälfte des Spiels und den Längen doppelt sind, halbiert, weil das Spiel aufhört. Die Lösung schließt Nisten ein Algorithmus ein, der für den Turm Hanois in einen Algorithmus passend ist, der anzeigt, wenn man zwischen Farben umschaltet. Wenn es k Stapel von n Platten pro Kopf in einem Spiel und k> 2 gibt, verlangt er k [T (n)] + T (n &minus; 1) + 1 Bewegungen, um sie umzusiedeln.

Die Hinzufügung eines zentral gelegenen universalen Hakens, der für Platten von allen Stapeln offen ist, wandelt sich um diese schobern Turm von Hanoier Rätseln mehrauf, um die Rätsel von Reve, wie beschrieben, in der vorhergehenden Abteilung mehraufzuschobern. In diesen Spielen kann sich jeder Stapel unter vier Haken, derselben Kombination drei in den 2 &times bewegen; 4 Spiel plus der universale Haupthaken. Das einfachste Spiel dieser Art (2 &times; 5) hat zwei Stapel und fünf Haken. Eine Lösung hat gemutmaßt, um optimal zu sein, schachtelt die optimale Lösung der 2 &times ineinander; 4 Rätsel mit der gewagten optimalen Lösung des Rätsels von Reve. Es nimmt R (n) + 2R (n &minus; 1) + 2 Bewegungen, wo R (n) die Zahl von Bewegungen in der Lösung des gewagten optimalen Reves für einen Stapel von n Platten ist.

In der populären Kultur

In der Sciencefictionsgeschichte "Inhalieren Jetzt" durch Eric Frank Russell, der Mensch ist ein Gefangener auf einem Planeten, wo die lokale Gewohnheit den Gefangenen ein Spiel soll spielen lassen, bis es gewonnen oder verloren wird, und dann Ausführung unmittelbar ist. Der Held weiß, dass ein Rettungsschiff ein Jahr nehmen könnte oder mehr anzukommen, so beschließt, Türme Hanois mit 64 Platten zu spielen. Diese Geschichte spielt auf die Legende über die buddhistischen Mönche an, die das Spiel bis zum Ende der Welt spielen.)

Im 1966-Arzt, Der Geschichte Der Himmlische Toymaker, der Titelbengel den Arzt zwingt, einen zehnteiligen 1023-Bewegungen-Turm des Hanoier Spiels genannt Das Trilogic Spiel mit den Stücken zu spielen, die eine Pyramide-Gestalt, wenn aufgeschobert, bilden.

Im 2011-Film Anstieg des Planeten der Menschenaffen wird das Rätsel, das im Film als der "Turm von Lucas" genannt ist, als ein Test verwendet, um die Intelligenz von Menschenaffen zu studieren.

Das Rätsel wird regelmäßig im Abenteuer und den Rätsel-Spielen gezeigt. Da es leicht ist, und leicht erkannt durchzuführen, ist es gut passend, um als ein Rätsel in einem größeren grafischen Spiel (z.B und Massenwirkung) zu verwenden. Einige Durchführungen verwenden gerade Platten, aber andere verkleiden das Rätsel in einer anderen Form. Es gibt eine Arkade-Version durch Sega/Andamiro.

Das Problem wird als ein Teil einer Belohnungsherausforderung in a gezeigt. Beide Spieler (Ozzy Lusth und Benjamin "Trainer" Wade) strengen sich an zu verstehen, wie man das Rätsel löst und von ihren Mitstamm-Mitgliedern geholfen wird.

Siehe auch

• Baguenaudier
• Recursion (Informatik)

Zeichen

Außenverbindungen