Fachkonzept - Rekursive Problemreduktion

Türme von Hanoi - Problemlösestrategie

Das Türme-von-Hanoi-Problem soll gelöst werden.

Problem: Transportiere einen 5-Scheiben-Turm von A über B nach C.

Lösung:

Türme von Hanoi - Anfangszustand
Transportiere einen 4-Scheiben-Turm von A über C nach B.
Türme von Hanoi - Zwischenzustand
Transportiere eine Scheibe von A nach C.
Türme von Hanoi - AZwischenzustand
Transportiere einen 4-Scheiben-Turm von B über A nach C.
Türme von Hanoi - Endzustand

Die Lösung zum Ausgangsproblem weist eine Besonderheit auf. Sie beschreibt nicht jeden einzelnen Scheibentransport. Die Lösung besteht vielmehr darin, das Ausgangsproblem auf ein entsprechendes Problem in verkleinerter Form zu reduzieren. Diese Problemlösestrategie erweist sich als sehr mächtig und wird daher mit einem Namen versehen.

Rekursive Problemreduktion ist eine Problemlösestrategie, bei der ein Problem auf ein strukturgleiches Problem (in verkleinerter Form) zurückgeführt wird.

Türme von Hanoi - Problemlösealgorithmus

Das oben beschriebene Problem wird zunächst etwas verallgemeinert.

Verallgemeinertes Problem: Transportiere einen n-Scheiben-Turm 
von einem Ausgangsort X über einen Hilfsort Y zu einem Zielort Z.

Der oben beschriebene Lösungsansatz wird jetzt zu einem Lösungsalgorithmus verallgemeinert.

ALGORITHMUS transportiere einen n-Scheiben-Turm von X über Y nach Z:
    wenn n > 1:
        transportiere einen (n-1)-Scheiben-Turm von X über Z nach Y
        transportiere eine Scheibe von X nach Z
        transportiere einen (n-1)-Scheiben-Turm von Y über X nach Z
    sonst:
        transportiere eine Scheibe von X nach Z 

Hier sind n, X, Y und Z Parameter, die bei konkreten Problemstellungen aktualisiert werden müssen.

Dass der Algorithmus tatsächlich das allgemeine Transportproblem löst, zeigt sich, wenn man sämtliche Problemreduktionsschritte ausführt. Wir verdeutlichen dies am Beispiel eines 3-Scheiben-Turms, indem wir schrittweise die Ausführungstiefe (man sagt auch Rekursionstiefe) schrittweise erhöhen.

Ausführungstiefe 1:

transportiere einen 3-Scheiben-Turm von A über B nach C:
    transportiere einen 2-Scheiben-Turm von A über C nach B
    transportiere eine Scheibe von A nach C
    transportiere einen 2-Scheiben-Turm von B über A nach C

Ausführungstiefe 2:

transportiere einen 3-Scheiben-Turm von A über B nach C:
    transportiere einen 2-Scheiben-Turm von A über C nach B:
        transportiere einen 1-Scheiben-Turm von A über B nach C
        transportiere eine Scheibe von A nach B
        transportiere einen 1-Scheiben-Turm von C über A nach B
    transportiere eine Scheibe von A nach C
    transportiere einen 2-Scheiben-Turm von B über A nach C:
        transportiere einen 1-Scheiben-Turm von B über C nach A
        transportiere eine Scheibe von B nach C
        transportiere einen 1-Scheiben-Turm von A über B nach C

Ausführungstiefe 3:

transportiere einen 3-Scheiben-Turm von A über B nach C:
    transportiere einen 2-Scheiben-Turm von A über C nach B:
        transportiere einen 1-Scheiben-Turm von A über B nach C:
            transportiere eine Scheibe von A nach C
        transportiere eine Scheibe von A nach B
        transportiere einen 1-Scheiben-Turm von C über A nach B:
            transportiere eine Scheibe von C nach B
    transportiere eine Scheibe von A nach C
    transportiere einen 2-Scheiben-Turm von B über A nach C:
        transportiere einen 1-Scheiben-Turm von B über C nach A:
            transportiere eine Scheibe von B nach A
        transportiere eine Scheibe von B nach C
        transportiere einen 1-Scheiben-Turm von A über B nach C:
            transportiere eine Scheibe von A nach C

Wenn man jetzt alle Aufrufe des Algorithmus weglässt, dann ergibt sich eine Folge von Basisaktionen, die letztlich das Problem löst.

            transportiere eine Scheibe von A nach C
        transportiere eine Scheibe von A nach B
            transportiere eine Scheibe von C nach B
    transportiere eine Scheibe von A nach C
            transportiere eine Scheibe von B nach A
        transportiere eine Scheibe von B nach C
            transportiere eine Scheibe von A nach C

Rekursive Algorithmen

Die Besonderheit des oben beschriebenen Algorithmus zur Lösung des Türme-von-Hanoi-Problems besteht darin, dass der Algorithmus sich selbst aufruft. Solche Algorithmen werden rekursiv ("zurücklaufend") genannt.

Ein rekursiver Algorithmus ruft sich (eventuell über Umwege) selbst auf und nutzt sich so selbst zur Beschreibung der Lösung des gegebenen Problems.

Diese Art der algorthimschen Lösungsbeschreibung ist (in der Regel) nur dann sinnvoll, wenn der Algorithmus bei den Selbstaufrufen sogenannte Reduktionsschritte durchführt, d.h.: Der Algorithmus darf sich in den Rekursionsschritten nur in verkleinerter Form nutzen, wobei die Verkleinerung nach endlich vielen Schritten zu einem Rekursionsanfang führen muss. Dieser Rekursionsangfang muss vom Algorithmus dann direkt gelöst werden.

Um Rekursion als Problemlösestrategie nutzen zu können, benötigt man ein Ausführsystem, das in der Lage sind, rekursive Algorithmen wiederholt aufzurufen und auf diese Weise die eigentliche Lösung zu generieren. Alle gängigen Programmiersysteme erlauben eine Implementierung rekursiver Algorithmen.

Rekursion ist eine mächtige und gerne genutzte Strategie beim Problemlösen. Wenn der Problemkontext es zulässt, dann kann man das Problemlöseverfahren sehr einfach und kompakt über eine Problemreduktion beschreiben. Die wiederholte Ausführung der Reduktionsschritte - und damit die Erzeugung der eigentlichen Lösung - überlässt man dem Ausführsystem.

X

Fehler melden

X

Suche