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:
Transportiere einen 4-Scheiben-Turm von A über C nach B.
Transportiere eine Scheibe von A nach C.
Transportiere einen 4-Scheiben-Turm von B über A nach C.
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 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.