Rekursion und Backtracking

Schlagwörter:
Referat, Hausaufgabe, Rekursion und Backtracking
Themengleiche Dokumente anzeigen

Beschreibung / Inhalt
Das Dokument behandelt die Themen Rekursion und Backtracking. Unter Rekursion wird verstanden, dass ein Problem in Teilprobleme zerlegt wird und diese wiederum weiter zerlegt werden, bis die Abbruchbedingung erfüllt ist und das Problem ausprogrammiert werden kann. Es werden verschiedene Arten von Rekursionen unterschieden und die Vor- und Nachteile von Rekursion und Iteration gegenübergestellt.

Backtracking ist ein Suchverfahren, bei dem durch Ausprobieren eine optimale Kombination gefunden wird. Das Verfahren wird am Beispiel eines Einbruchs in ein Haus erläutert. Es wird darauf hingewiesen, dass der Algorithmus optimiert werden kann, indem pro Knoten der höchste Wert, zu dem er führt, mitgespeichert wird.

Des Weiteren wird ein weiteres Problem behandelt, bei dem Backtracking eingesetzt wird: die Wegesuche in einem zusammenhängenden Graphen. Dabei wird mittels Rekursionen vorgegangen.

Die Beispiele werden in C dargestellt und erläutert.
Direkt das Referat aufrufen

Auszug aus Referat
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 ...
Direkt das Referat aufrufen

Autor:
Kategorie:
Sonstiges
Anzahl Wörter:
924
Art:
Referat
Sprache:
Deutsch
Bewertung dieser Hausaufgabe
Diese Hausaufgabe wurde bislang noch nicht bewertet.
Zurück