Induktion für minimale Züge Türme von Hanoi

26.04.2018, 07:56

NicoBe

Induktion für minimale Züge Türme von Hanoi

Hi,

ich denke, das Thema ist bekannt. Die herkömmliche Induktion zu diesem Thema ist mit auch bekannt, für mein momentanes Anliegen habe ich allerdings nichts in der Suchleiste gefunden. Falls es da doch etwas gibt, gerne löschen. smile

Es geht um die Türme von Hanoi: n Scheiben, die von Position 1 auf Position 2 über Position 3 verschoben werden sollen. Die Laufzeit dabei ist bekanntlich 2^n-1.

Das ganze kann mit folgendem Algorithmus im Pseudocode beschrieben werden:

1 if n > 0 then
2 Hanoi(n-1,from, via, to);
3 Schreibe: ”Bewege Scheibe von Position“ from ”nach“ to;
4 Hanoi(n-1, via, to, from);
5 fi

Doch wie kann ich jetzt mittels Induktion nachweisen, dass dieser Algorithmus wirklich in Minimalzeit läuft? Habe dazu noch nichts gefunden.

LG,
Nico

26.04.2018, 09:23

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von NicoBe
Doch wie kann ich jetzt mittels Induktion nachweisen, dass dieser Algorithmus wirklich in Minimalzeit läuft? Habe dazu noch nichts gefunden.

Man kann es auch mal mit selber nachdenken versuchen, ist wirklich nicht so schwer hier. Die nachzuweisende Behauptung lautet:

Zitat:

Jede erfolgreiche Versetzung eines Turmes mit $\begin{eqnarray*} n \end{eqnarray*}$ Scheiben benötigt mindestens $\begin{eqnarray*} 2^n-1 \end{eqnarray*}$ Züge.

und der Nachweis geschieht eben durch die angesprochene Vollständige Induktion.

Induktionsanfang sollte klar sein, und im Induktionsschritt $\begin{eqnarray*} n\to n+1 \end{eqnarray*}$ ist das entscheidende Argument:

Um den gesamten Turm mit $\begin{eqnarray*} (n+1) \end{eqnarray*}$ Scheiben von Position 1 nach 3 umzusetzen, muss irgendwann die unterste Scheibe einzeln auf Position 1 dastehen UND die Zielposition 3 leer sein. Das geht zwangsläufig nur dann, wenn die restlichen $\begin{eqnarray*} n \end{eqnarray*}$ Scheiben auf Position 2 stehen - und irgendwie müssen die ja vorher dahingekommen sein und danach auch wieder von da wegmüssen...

27.04.2018, 19:37

NicoBe

Auf diesen Beitrag antworten »

Hallo HAL 9000,
erstmal danke für die Antwort, die Idee leuchtet mir ein, nicht aber der genaue Ablauf.

Wenn ich die Induktion starte gehe ich ja über n. Damit kann ich problemlos darstellen, dass der Algorithmus in 2^n-1 läuft.

Nur wie zeigt mir die Induktion dann, dass das ganze auch die minimale Laufzeit des Algorithmusses ist?

LG und schönes Wochenende,
Nico

27.04.2018, 19:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von NicoBe
Nur wie zeigt mir die Induktion dann, dass das ganze auch die minimale Laufzeit des Algorithmusses ist?

Oben habe ich den Beweis dafür skizziert, dass jeder erfolgreiche Ablauf mindestens $\begin{eqnarray*} 2^n-1 \end{eqnarray*}$ Züge benötigt.

Dass es auch mit genau $\begin{eqnarray*} 2^n-1 \end{eqnarray*}$ Zügen geht, zeigt bereits dein Ablauf im Eröffnungsposting.

Beides zusammen ist doch der gesuchte Nachweis.

27.04.2018, 21:57

NicoBe

Auf diesen Beitrag antworten »

Okey, wenn ich das dann richtig verstehe, zeige ich zwei Induktionen:

1. Die Laufzeit ist >= 2^n-1
2. Die Laufzeit ist = 2^n-1

Lg,
Nico

27.04.2018, 22:10

HAL 9000

Auf diesen Beitrag antworten »

Ok, ich modifiziere noch mal meine Beschreibung oben, die ist tatsächlich nicht völlig zwingend: Kann ja sein, dass die unterste Scheibe zunächst noch woanders hin wandert und von dort dann erst zur Zielposition...

Zitat:

Um den gesamten Turm mit $\begin{eqnarray*} (n+1) \end{eqnarray*}$ Scheiben von Position 1 nach 3 umzusetzen, muss irgendwann die unterste Scheibe ihre Position 1 verlassen. Das geht nur, wenn die unterste Scheibe einzeln auf Position 1 dasteht UND irgendeine andere Position (z.B. die Zielposition 3) leer ist. Das geht zwangsläufig nur dann, wenn die restlichen $\begin{eqnarray*} n \end{eqnarray*}$ Scheiben auf der noch übrig bleibenden Position (im Beispiel dann Position 2) stehen - und irgendwie müssen die ja vorher dahingekommen sein und danach auch wieder von da wegmüssen...

27.04.2018, 22:34

NicoBe

Auf diesen Beitrag antworten »

Herzlichen Dank für die Antwort, leider komme ich damit gerade ebenso wenig weiter.

Trotzdem danke für deine Bemühungen!

Ich werde mich dann nochmal wo anders umsehen.

LG,
Nico

27.04.2018, 22:56

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von NicoBe
Herzlichen Dank für die Antwort, leider komme ich damit gerade ebenso wenig weiter.

Weil du nicht wirklich drüber nachdenkst. Na dann suche eben woanders, schade um die vertane Zeit.

Neue Frage »

Antworten »

Induktion für minimale Züge Türme von Hanoi

Verwandte Themen