Artikel pedia
| Home | Kontakt | Artikel einreichen | Oberseite 50 artikel | Oberseite 50 autors
 
 


Artikel kategorien
Letztes fugte hinzu
    Ms-access

   Instrumentation + schnittstellen

   Pc tuning - volle kraft voraus für ihr system

   Informatorische grundlagen

   Javascript

   Interne sortieralgorithmen - der kern der sache

   Plotter und sonstige drucker

   Frage 20 (rössl priska)

   Internet - programmierung

   Monitore

   Semesterarbeit und spezialgebiet für informatik

   Erörterungs zum thema

   Inhaltsverzeichnis

   Einführung in die entwicklung ganzheitlicher informationssysteme:

   Titel dokument
alle kategorien

  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) {     if(pknoten-left) traverse(pknoten-left);     knoten_ausgeben(pknoten);     if(pknoten-right) traverse(pknot-right); }   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) {     if(x==1) return 1;     return x * factorial(x-1); } Lösung mit Iteration(mit Schleifen): int factorial( int x) {     for(int factor=1; x 1; x--) factor = factor * x;     return factor; }     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:       Kriterium Rekursion Iteration Laufzeit langsam schneller Speicher viel wenig Aufwand gering höher   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 Äste 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

Suchen artikel im kategorien
Schlüsselwort
  
Kategorien
  
  
   Zusammenfassung Der Vorleser

   sachtextanalyse

   interpretation zwist

   Fabel interpretation

   literarische charakteristik

   interpretation bender heimkehr

   felix lateinbuch

   interpretation der taucher von schiller

   textbeschreibung

   charakterisierung eduard selicke
Anmerkungen:

* Name:

* Email:

URL:


* Diskussion: (NO HTML)




| impressum | datenschutz

© Copyright Artikelpedia.com