Rekursion und Backtracking

Rekursion und Backtracking

1.Rekursion

1.1 Allgemeines zu Rekursionen

Die Rekursion ist ein fundamentales Konzept, das in der Mathematik und in der Informatik im Einsatz ist. Zerlegt man ein Problem in Teilprobleme und erhält dann wieder das Problem von dem ausgegangen wurde, so handelt es sich hierbei um eine Rekursion.

Dies funktioniert so, das sich eine Funktion immer wieder selbst aufruft, und das Problem wieder in Teilprobleme zerlegt wird. Es wird so lange zerlegt, bis das Teilproblem so einfach ist, daß es ausprogrammiert werden kann. Der Funktion muß immer das Problem übergeben werden, welches in Teilprobleme zerlegt wird und dann wieder übergeben wird. Tritt das Problem nicht mehr auf, d.h. ist Abbruchbedingung ist bereits erfüllt wird mit Hilfe eines Rückgabewertes die Rekursion beendet. Ansonsten wird das Ergebnis des Aufrufs für die Berechnung des Rückgabewertes verwendet.

1.2 Beispiele

1.2.1 Ausgabe eines Binärbaumes (sog. Traversierung)

Eine Anwendung auf die Rekursionen regelrecht zugeschnitten sind, sind Binärbäume, deren iterative Programmierung ziemlich aufwendig wäre.

C-Funktion traverse: Es wird solange in den linken Ast des Knotens verzweigt, bis es keinen linken Ast mehr gibt. Dann wird der aktuelle Knoten ausgegeben und in den ev. Vorhandenen rechten Ast verzweigt. Gibt es auch keinen rechten Ast mehr, dann wird in den Knoten der übergeordneten Ebene zurückgegangen. Solange bis der ganze Baum ausgegeben wurde. Die Ausgabe der Knoten erfolgt nach der Numerierung. Der erste Knoten ist logischerweise links unten, dann zu seinem übergeordneten und dann zum untergeordneten rechten Knoten.

void traverse(KNOTEN *pknoten)

 

1.2.2 Fakultät einer Zahl

Die Fakultät einer Zahl x ist folgendermaßen definiert: x! = x * (x-1)!. Das wird solange fortgeführt, bis x-n den Wert 1 erreicht hat.

z.B: 5! = 5 * 4 * 3 * 2 *1

C-Funktion factorial: Berechnet die Fakultät einer Zahl.

Lösung mit Rekursion:

int factorial(int x)

Lösung mit Iteration(mit Schleifen):

int factorial( int x)

 
 

1.3 Arten von Rekursionen

1.3.1 Lineare Rekursion

Die Tiefe der möglichen Rekursion ist 1. Eine linear - rekursive Funktion ruft sich maximal einmal selbst auf. Diese Funktionen können leicht auch iterativ programmiert werden.
 

1.3.2 Kaskadenförmige Rekursion

Es kann vorkommen, daß sich die Funktion mehrmals selbst aufruft. Die Bearbeitung von Bäumen ist typischerweise kaskadenförmig und die Adaptierung in iterative Programmierung ist nicht so ohne weiteres möglich.
 

1.4 Gegenüberstellung Rekursion und Iteration

Grundsätzlich wird bei einer Rekursion die Funktion immer wieder aufgerufen bis die Abbruchbedingung erfüllt ist. Bei der Iteration wird das Problem mit Hilfe von Schleifen gelöst. Theoretisch kann jede(!) rekursive Funktion auch als iterative Funktion ausprogrammiert werden, jedoch gibt es Probleme für die sich die Rekursion besonders gut eignet, zum Beispiel Binärbäume.

Es gibt drei Kriterien:
 
 
 

Ob man nun Rekursionen oder Iterationen verwendet, hängt vom jeweiligen Problem ab und von der Wichtigkeit der jeweiligen Kriterium ab. Wenn es möglich ist, sollte man lineare Rekursionen in Iterationen umwandeln und kaskadenförmige Rekursionen belassen.
 
 

2. Backtracking

2.1 Allgemeines über Backtracking

Backtracking ist ein Suchverfahren, bei dem versucht wird, aus einer Reihe von Möglichkeiten durch einfaches Ausprobieren eine optimale Kombination zu ermitteln.

Wenn ein bestimmter Zweig den Prüfbedingungen nicht mehr entspricht, wird in diesem Zweig nicht mehr weitergesucht, sondern um 1 Knoten zurückgegangen und von dort wird der nächste Zweig getestet.

2.2 Einfaches Beispiel

Ein Verbrecher bricht in ein Haus ein, und findet dort 4 Dinge, die ihm gefallen. Er kann jedoch nur ein Maximalgewicht von 37 kg tragen und nun muß er sich entscheiden welche Dinge er mitnimmt. Mit Hilfe des Backtrackings wird dieses Problem optimal gelöst.

Gegenstand    A:  Edle Lampe 5 kg         Wert: 14
              B:  Hifi-Anlage 18 kg        Wert: 7
              C: Fernsehapparat 15 kg   Wert: 15
              D: Videorecorder 10 kg    Wert: 16
 

Die Zahlen hinter den Buchstaben bedeuten das Gewicht, die Zahlen darunter den Wert. Die durchgestrichenen Kästchen werden bei der Suche ignoriert. Die orangen Pfeile kennzeichnen die Suchreihenfolge. Der Weg mit doppelten Strichen kennzeichnet den optimalen Weg. Der Räuber wird Gegenstand A,C und D mitnehmen.

Algorithmus:

1. Zuerst wird der linke Zweig durchsucht
2. Wenn beim Aufsummieren der Gewichte das Maximalgewicht überschritten wird, wird der Ast nicht weiter verfolgt, sondern 1 Knoten zurückgegangen.
3. Wenn ein Endknoten erreicht wird, wird die Summe der Werte als Höchstwert gespeichert. Auch der Weg von der Wurzel zum Endknoten wird gespeichert.
4. Es wird wieder zurückgegangen und der nächste Zweig wird getestet.
5. Wenn wieder ein Endknoten erreicht ist, wird die Summe der Werte mit dem derzeitigen Höchstwert verglichen. Wenn sie höher ist, wird die neue Summe
    der Werte zum Höchstwert.

Nachteil dieses Algorithmusses ist, daß auch Aste oder Wege durchlaufen werden, die nicht zum Ziel führen. Das kann zu enorm hohen Rechenzeiten führen. Der Algorithmus kann verbessert werden, indem pro Knoten der höchste Wert, zu dem er führt mitgespeichert wird. Kommt der Algorithmus jetzt zu einem Knoten, der zu keinem größeren Wert als dem bestehenden Höchstwert führt, wird sofort zurückgegangen ('backgetrackt').

2.3 Weitere Beispiele

Wegesuche

Ein weiteres Problem, bei dem Backtracking eingesetzt wird, ist die sogenannte Wegesuche in einem zusammenhängenden Graphen.
Wird auch mittels Rekursionen gelöst.

suche(gefunden,A,B,Weg)
Hinzufügen von A zu Weg
Wenn A=B
   gefunden = TRUE
Sonst
   Wenn A besucht dann
        gefunden = FALSE
   Sonst
        A besucht = TRUE
        Für alle Nachbarn von A (solange nicht gefunden)
            suche gefunden,Nachbar, B , Weg
        EndFür
        A besucht = FALSE
   EndWenn
EndWenn
Wenn gefunden = FALSE
   Lösche A aus Weg       // Backtracking
EndWenn