Fachkonzept - Rekursive Problemreduktion

Türme von Hanoi - Lösung im Basisfall

Das Türme-von-Hanoi-Problem für drei Scheiben kann in sieben Zügen gelöst werden:

ALGORITHMUS - Transportiere einen 3-Scheiben-Turm von A nach C (über B):
    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.

Allgemeiner können 3-Scheiben-Türme nach diesem Muster auch von einem beliebigen Turm X zu einem beliebigen anderen Turm Z verschoben werden:

ALGORITHMUS - Transportiere einen 3-Scheiben-Turm von X nach Z (über Y):
    Transportiere eine Scheibe von X nach Z.
    Transportiere eine Scheibe von X nach Y.
    Transportiere eine Scheibe von Z nach Y.
    Transportiere eine Scheibe von X nach Z.
    Transportiere eine Scheibe von Y nach X.
    Transportiere eine Scheibe von Y nach Z.
    Transportiere eine Scheibe von X nach Z.

Die Hervorhebung von X, Z und Y soll deutlich machen, dass es sich hier um Parameter des Algorithmus handelt, für die jeweils der Name eines Turms (also A, B oder C) eingesetzt wird.

Türme von Hanoi - Rekursive Problemreduktion

Das Türme-von-Hanoi-Problem für vier Scheiben kann mithilfe der Lösung für drei Scheiben gelöst werden.

ALGORITHMUS - Transportiere einen 4-Scheiben-Turm von A nach C (über B):
    › Transportiere einen 3-Scheiben-Turm von A nach B (über C).
    » Transportiere eine Scheibe von A nach C.
    › Transportiere einen 3-Scheiben-Turm von B nach C (über A).

Hier kommt uns zugute, dass wir einen Algorithmus für beliebige Türme X, Y und Z angegeben haben: Dadurch ist nämlich bekannt, wie wir jeweils den 3-Scheiben-Turm transportieren können.

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.

Türme von Hanoi - Problemlösealgorithmus

Wie im Fall von drei Scheiben kann das Vorgehen für "von A nach B (über C)" auch auf den Fall "von X nach Z (über Y)" übertragen werden:

ALGORITHMUS - Transportiere einen 4-Scheiben-Turm von X nach Z (über Y):
    › Transportiere einen 3-Scheiben-Turm von X nach Y (über Z).
    » Transportiere eine Scheibe von X nach Z.
    › Transportiere einen 3-Scheiben-Turm von Y nach Z (über X).

Diese verallgemeinerte Lösung für den 4-Scheiben-Turm ermöglicht wiederum eine Strategie für fünf Scheiben:

ALGORITHMUS - Transportiere einen 5-Scheiben-Turm von X nach Z (über Y):
    › Transportiere einen 4-Scheiben-Turm von X nach Y (über Z).
    » Transportiere eine Scheibe von X nach Z.
    › Transportiere einen 4-Scheiben-Turm von Y nach Z (über X).

Allgemein kann eine Strategie für einen n-Scheiben-Turm immer anhand des Falls von (n-1)-Scheiben-Türmen beschrieben werden:

STRATEGIE - Transportiere einen n-Scheiben-Turm X nach Z (über Y):
    › Transportiere einen (n-1)-Scheiben-Turm von X nach Y (über Z).
    » Transportiere eine Scheibe von X nach Z.
    › Transportiere einen (n-1)-Scheiben-Turm von Y nach Z (über X).

Zu einem Algorithmus wird die Strategie aber erst, wenn für den ersten und den letzten Schritt schon ein Algorithmus für (n-1)-Scheiben-Türme definiert ist.

Damit wir nicht für jeden Wert von n einen eigenen Algorithmus definieren müssen, nutzen wir einen Trick: Wir machen die Anzahl der Scheiben n zu einem zusätzlichen Parameter des Algorithmus. Der Algorithmus ruft sich in seiner eigenen Definition selbst auf - allerdings mit dem kleineren Wert n-1. Dadurch sinkt der Wert in jedem Aufruf immer weiter. Früher oder später landet der Algorithmus dann bei einem Aufruf mit dem Parameterwert n = 3. In diesem Fall wird dann die Basisstrategie für drei Scheiben angewendet.

ALGORITHMUS - Transportiere einen n-Scheiben-Turm von X nach Z (über Y):
    wenn n > 3:
        › Transportiere einen (n-1)-Scheiben-Turm von X nach Y (über Z).
        » Transportiere eine Scheibe von X nach Z.
        › Transportiere einen (n-1)-Scheiben-Turm von Y nach Z (über X).
    sonst:
        Transportiere eine Scheibe von X nach Z.
        Transportiere eine Scheibe von X nach Y.
        Transportiere eine Scheibe von Z nach Y.
        Transportiere eine Scheibe von X nach Z.
        Transportiere eine Scheibe von Y nach X.
        Transportiere eine Scheibe von Y nach Z.
        Transportiere eine Scheibe von X nach Z.

Etwas kürzer und allgemeiner wird der Algorithmus noch, wenn wir den Basisfall erst beim 1-Scheiben-Turm (also bei n = 1) ansetzen:

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

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 nach C (über B):
    › Transportiere einen 2-Scheiben-Turm von A nach B (über C).
    » Transportiere eine Scheibe von A nach C.
    › Transportiere einen 2-Scheiben-Turm von B nach C (über A).

Ausführungstiefe 2:

› Transportiere einen 3-Scheiben-Turm von A nach C (über B):
    › Transportiere einen 2-Scheiben-Turm von A nach B (über C):
        › Transportiere einen 1-Scheiben-Turm von A nach C (über B).
        » Transportiere eine Scheibe von A nach B.
        › Transportiere einen 1-Scheiben-Turm von C nach B (über A).
    » Transportiere eine Scheibe von A nach C.
    › Transportiere einen 2-Scheiben-Turm von B nach C (über A):
        › Transportiere einen 1-Scheiben-Turm von B nach A (über C).
        » Transportiere eine Scheibe von B nach C.
        › Transportiere einen 1-Scheiben-Turm von A nach C (über B).

Ausführungstiefe 3:

› Transportiere einen 3-Scheiben-Turm von A nach C (über B):
    › Transportiere einen 2-Scheiben-Turm von A nach B (über C):
        › Transportiere einen 1-Scheiben-Turm von A nach C (über B):
            » Transportiere eine Scheibe von A nach C.
        » Transportiere eine Scheibe von A nach B.
        › Transportiere einen 1-Scheiben-Turm von C nach B (über A):
            » Transportiere eine Scheibe von C nach B.
    » Transportiere eine Scheibe von A nach C.
    › Transportiere einen 2-Scheiben-Turm von B nach C (über A):
        › Transportiere einen 1-Scheiben-Turm von B nach A (über C):
            » Transportiere eine Scheibe von B nach A.
        » Transportiere eine Scheibe von B nach C.
        › Transportiere einen 1-Scheiben-Turm von A nach C (über B):
            » 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.

Diese Art der algorithmischen 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 Rekursionsanfang 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 ist, 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.