Rekursiver Algorithmus für hanoieskes Problem
Neue Frage »

28.01.2014, 21:39 eman Auf diesen Beitrag antworten »
Rekursiver Algorithmus für hanoieskes Problem
Hallo allerseits,
für die Uni muß ich einen rekursiven Algorithmus für ein Problem implementieren, das ähnlich den Türmen von Hanoi ist. Gegeben sind zwei gleich große Türme, es gibt drei Stäbe und Ziel ist es die Positionen der beiden Türme zu tauschen, also wo der schwarze war, soll der weiße stehen, und andersherum. Regeln sind wie beim normalen Türme von Hanoi und es dürfen gleich große Scheiben aufeinander liegen.
Die Aufgabenstellung empfiehlt als status quo einen Zwischenstand, bei dem alle Scheiben rechts mit wechselnder Farbe sind (siehe Anhänge).

Die rekursive Lösungsfunktion soll das gleiche Format haben wie die vom normalen Hanoi-Problem, also etwa moveTower( Stab from, Stab to, Zahl i, Stab temp).

Folgendes habe ich nun seit ein paar Stunden erfolglos versucht: Für n=2 und n=3 explizite Lösungen probiert und versucht einen Rekursionsbaum aufzustellen. Leider ziemlich erfolglos...

Daher wende ich mich nun an euch und hoffe, daß der ein oder andere einen hilfreichen Rat hat.

Danke im Voraus,
eman
28.01.2014, 21:49 10001000Nick1 Auf diesen Beitrag antworten »

Bitte nicht beachten, hier stand Unsinn. unglücklich
28.01.2014, 23:07 HAL 9000 Auf diesen Beitrag antworten »

Geht es nur um irgendeinen Algorithmus, oder sogar um einen effizienten (d.h. mit minimaler Schrittzahl)?

Ersteres ist ganz gut machbar, letzteres scheint mir ungleich schwerer.
28.01.2014, 23:24 eman Auf diesen Beitrag antworten »

Es geht lediglich um irgendeinen Algorithmus. Leider stehe ich schon hierbei auf dem Schlauch.

Ab dem Zwischenstand (siehe Bild oben), habe ich mir ungefähr folgende Strategie überlegt (Pseudocode):

code: 
1:
2:
3:
4:
5:
6:
7:

moveTower( Stab from, Stab to, Zahl i, Stab temp){
falls (i>0){
     moveTower(from, temp, i-1, to);
     verschiebe from nach to;
     moveTower(temp, from, i-2, temp);
}


Wenn ich also die untersten beiden Scheiben in Zielposition bringen möchte, muß ich zuerst (i-1) Scheiben auf den andren Haufen bringen, dann die eigentliche Scheibe verschieben und dann wieder (i-2) Scheiben auf den Ausgangshaufen (rechhts) zurückschaufeln... das müßte theoretisch funktioneren, oder?

Nur wie komme ich zum sortierten Haufen rechts?
28.01.2014, 23:28 HAL 9000 Auf diesen Beitrag antworten »

Ich geb mal meine Idee an, zunächst das Problem zum Erstellen des "Zebraturms" in Bild 2:

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

mergeTowers ( Stab white, Stab black, Zahl i, Stab mixed)
{
    if (i > 0)
    {
        mergeTowers( white, black, i-1, mixed)
        move(white, black)
        moveTower(mixed, white, 2*i-2, black)
        move(black, mixed)
        move(black, mixed)
        moveTower(white, mixed, 2*i-2, black)
    }
}


Mit "move" meine ich einen Einzelschritt und mit "moveTower" die normale Hanoiturm-Prozedur. Tja, und zum Schluss alles "rückwärts", nur mit vertauschten Rollen der Stäbe für white und black.
29.01.2014, 00:02 eman Auf diesen Beitrag antworten »

Vielen Dank für deine schnelle Antwort, HAL!

Zitat:
Original von HAL 9000

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:

mergeTowers ( Stab white, Stab black, Zahl i, Stab mixed)
{
    if (i > 0)
    {
        mergeTowers( white, black, i-1, mixed)
        move(white, black)
        moveTower(mixed, white, 2*i-2, black)
        move(black, mixed)
        move(black, mixed)
        moveTower(white, mixed, 2*i-2, black)
    }
}



Ich bin einmal händisch die Schritte deines Algorithmus für i=2 durchgegangen, das endet leider in einem endlosen rekursiven bei moveTower( ..., 2*i -1, black), sobald man i=2 erreicht (und da muß man ja zwangsweise hin).
 Anzeige 
 
29.01.2014, 07:37 HAL 9000 Auf diesen Beitrag antworten »

Zitat:
Original von eman
Ich bin einmal händisch die Schritte deines Algorithmus für i=2 durchgegangen, das endet leider in einem endlosen rekursiven bei moveTower( ..., 2*i -1, black), sobald man i=2 erreicht

Das kann ich nur als Unfug bezeichnen. unglücklich

Erstens steht da moveTower( ..., 2*i -2, black), und zweitens ist moveTower die Hanoi-Prozedur, die bekanntlich nicht "endlos rekursiv" ist. Vielleicht verwechselst du ja moveTower mit der eigentlich hier definierten Hauptprozedur mergeTowers.


Als Ergänzung daher noch - obwohl ich schon angenommen und vorausgesetzt hatte, dass du die kennst - die normale Hanoi-Prozedur:
code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:

moveTower( Stab from, Stab to, Zahl j, Stab temp)
{
    if (j > 0)
    {
        moveTower(from, temp, j-1, to)
        move(from, to)
        moveTower(temp, to, j-1, from)
    }
}
29.01.2014, 09:47 eman Auf diesen Beitrag antworten »

Zitat:
Original von HAL 9000
Das kann ich nur als Unfug bezeichnen. unglücklich

Erstens steht da moveTower( ..., 2*i -2, black), und zweitens ist moveTower die Hanoi-Prozedur, die bekanntlich nicht "endlos rekursiv" ist. Vielleicht verwechselst du ja moveTower mit der eigentlich hier definierten Hauptprozedur mergeTowers.

Hallo HAL 9000,
entschuldige bitte meinen groben Unfug, ich habe tatsächlich moveTower mit mergeTower verwechselt...
Dein Algorithmus funktioniert tatsächlich wunderbar, auch wenn sich meinem bescheidenen Denkvermögen entzieht, wie du auf ihn gekommen bist.
Ich habe den Solver jetzt durch zweimaliges Aufrufen deines Zebraalgorithmus implementiert, etwas unschön mit Stack umstapeln und schmutzig implementiertem Richtungswechsel, aber es funktioniert. Man könnte den Algorithmus im Nachgang ein wenig beschleunigen, indem man Schritte, die sich gegenseitig aufhaben rauslöscht und Schritte die konsekutiv die gleiche Scheibe adressieren zusammenfaßt.

Ich danke dir tausendfach, HAL 9000!! Du hast meinen Tag gerettet! Freude

Edit: Den klassischen Türme von Hanoi-Algorithmus kenne ich natürlich, was mich aber nicht daran gehindert hat, ihn falsch zu implementieren ;-)
29.01.2014, 11:00 HAL 9000 Auf diesen Beitrag antworten »

Ja, die obige Prozedur ist noch ziemlich ineffizient. Deutlich besser wäre da

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

MergeTowers (Stab white, Stab black, Zahl i, Stab mixed)
{
    if (i > 0)
    {
        move(white, mixed)
        move(black, mixed)
        for (j = 1; j < i; j++)
        {
            move(white, black)
            moveDoubleTower(mixed, white, j, black)
            move(black, mixed)
            move(black, mixed)
            moveDoubleTower(white, mixed, j, black)
        }
    }
}

moveDoubleTower (Stab from, Stab to, Zahl j, Stab temp)
{
    if (j > 0)
    {
        moveDoubleTower(from, temp, j-1, to)
        move(from, to)
        move(from, to)
        moveDoubleTower(temp, to, j-1, from)
    }
}

moveDoubleTower macht folgendes: Es setzt den Zebraturm der Höhe 2j von Position from zu Position to um, dabei wird aber (im Gegensatz zum Original-Hanoi) die Reihenfolge wsws...ws in swsw...sw umgewandelt, bzw. umgekehrt! Da wir das ganze aber ja zweimal in einer Iteration aufrufen, hebt sich das wieder auf, und der Turm ist wieder in der "richtigen" Farbreihenfolge.

Das ganze benötigt nun nur noch Schritte, oben waren es noch Schritte. Optimal ist aber auch das noch nicht. Augenzwinkern


EDIT: Die komplette Prozedur wäre dann, alle Schritte nochmal in der umgekehrten Richtung durchzuführen, aber dabei black und white zu vertauschen - insgesamt also

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:

SwapTowers (Stab white, Stab black, Zahl i, Stab mixed)
{
    if (i > 0)
    {
        move(white, mixed)
        move(black, mixed)
        for (j = 1; j < i; j++)
        {
            move(white, black)
            moveDoubleTower(mixed, white, j, black)
            move(black, mixed)
            move(black, mixed)
            moveDoubleTower(white, mixed, j, black)
        }
        // jetzt die Rueckrichtung
        for (j = i-1; j > 0; j++)
        {
            moveDoubleTower(mixed, black, j, white)
            move(mixed, white)
            move(mixed, white)
            moveDoubleTower(black, mixed, j, white)
            move(white, black)
        }
        move(mixed, white)
        move(mixed, black)
    }
}



EDIT: Hmmm, ist viellleicht doch noch ein Denkfehler drin mit dieser Geschichte wsws...ws bzw. swsw...sw, also vergiss es erstmal.
29.01.2014, 11:42 eman Auf diesen Beitrag antworten »

Ja, dein letzter Algorithmus ist deutlich schneller und für mich verständlicher (da sich die Bedeutung von from, to und temp bzw. white, black und mixed nicht bei jedem Aufruf ändert); leider ist er allerdings nicht mehr rekursiv, wie die Aufgabenstellung es fordert. Lehrer
Wahrscheindlich kann man noch ein bißchen an Zügen dadurch wegzaubern, daß man die Mixed-Pyramide nur so groß macht, wie gerade nötig.

Nocheinmal danke für deine Hilfe!

Edit:
Zitat:
Hmmm, ist viellleicht doch noch ein Denkfehler drin mit dieser Geschichte wsws...ws bzw. swsw...sw, also vergiss es erstmal.

Also meine ein zu eins implementierung deines zweiten MergeTowers funktioniert einwandfrei.
29.01.2014, 11:45 HAL 9000 Auf diesen Beitrag antworten »

Mein letztes EDIT war unnötige Panikmache, es geht also doch, aber meine Beschreibung oben ist falsch: moveDoubleTower vertauscht nicht generell die w- und s-Scheiben gleicher Größe, sondern nur bei den beiden untersten Scheiben, d.h.

wswsws...ws wird zu swwsws...ws bzw. beim zweiten Aufruf dann swwsws...ws wieder zurück in wswsws...ws.


Und dann noch zu dem "Problem" ( Big Laugh ):

Zitat:
Original von eman
leider ist er allerdings nicht mehr rekursiv, wie die Aufgabenstellung es fordert. Lehrer

Da mein erster Wurf oben von mergeTowers sich selbst nur einmal (mit i-1 und ansonsten gleichen Aufrufparametern) aufruft, habe ich das gleich lieber in eine Schleife umgewandelt - da bin ich zu sehr "praktischer" Programmierer: Zuviel Iterationstiefe belastet den Stack zu sehr, d.h. wenn möglich, bitte vermeiden. Augenzwinkern

Inhaltlich äquivalent kannst du das ganze natürlich zu

code: 
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:

MergeTowers (Stab white, Stab black, Zahl i, Stab mixed)
{
    if (i == 1)
    {
        move(white, mixed)
        move(black, mixed)
    }
    else if (i > 1)
    {
        MergeTowers(white, black, i-1, mixed)
        move(white, black)
        moveDoubleTower(mixed, white, i-1, black)
        move(black, mixed)
        move(black, mixed)
        moveDoubleTower(white, mixed, i-1, black)
    }
}

umschreiben. Augenzwinkern
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »


MatheBoard » Hochschulmathematik » Sonstiges » Rekursiver Algorithmus für hanoieskes Problem