www.wikidata.de-de.nina.az

Backtracking Der Begriff Rücksetzverfahren oder englisch Rückverfolgung bezeichnet eine Problemlösungsmethode innerhalb

Backtracking

Der Begriff Rücksetzverfahren oder englisch Backtracking (Rückverfolgung) bezeichnet eine Problemlösungsmethode innerhalb der Algorithmik.

Backtracking arbeitet nach dem Prinzip der Tiefensuche

Allgemeiner Algorithmus Bearbeiten

Backtracking geht nach dem Versuch-und-Irrtum-Prinzip (trial and error) vor, das heißt, es wird versucht, eine erreichte Teillösung zu einer Gesamtlösung auszubauen. Wenn absehbar ist, dass eine Teillösung nicht zu einer endgültigen Lösung führen kann, wird der letzte Schritt beziehungsweise werden die letzten Schritte zurückgenommen, und es werden stattdessen alternative Wege probiert. Auf diese Weise ist sichergestellt, dass alle in Frage kommenden Lösungswege ausprobiert werden können (Prinzip des Ariadnefadens). Mit Backtracking-Algorithmen wird eine vorhandene Lösung entweder gefunden (unter Umständen nach sehr langer Laufzeit), oder es kann definitiv ausgesagt werden, dass keine Lösung existiert. Backtracking wird meistens am einfachsten rekursiv implementiert und ist ein prototypischer Anwendungsfall von Rekursion. 

Funktion FindeLösung (Stufe, Vektor) 1. wiederhole, solange es noch neue Teil-Lösungsschritte gibt: a) wähle einen neuen Teil-Lösungsschritt; b) falls Wahl gültig ist: I) erweitere Vektor um Wahl; II) falls Vektor vollständig ist, return true; // Lösung gefunden! sonst: falls (FindeLösung(Stufe+1, Vektor)) return true; // Lösung! sonst mache Wahl rückgängig; // Sackgasse (Backtracking)! 2. Da es keinen neuen Teil-Lösungsschritt gibt: return false // Keine Lösung!

Zeitkomplexität Bearbeiten

Bei der Tiefensuche werden bei maximal möglichen Verzweigungen von jeder Teillösung aus und einem Lösungsbaum mit maximaler Tiefe von im schlechtesten Fall Knoten erweitert.

Die Tiefensuche und somit auch Backtracking haben im schlechtesten Fall mit und einem Verzweigungsgrad eine exponentielle Laufzeit. Je größer die Suchtiefe , desto länger dauert die Suche nach einer Lösung. Daher ist das Backtracking primär für Probleme mit einem kleinen Lösungsbaum geeignet.

Es gibt jedoch Methoden, mit welchen die Zeitkomplexität eines Backtracking-Algorithmus verringert werden kann. Diese sind unter anderem:

  • Heuristiken
  • Akzeptanz von Näherungslösungen und Fehlertoleranz
  • Durchschnittliche Eingabemenge

Beispiele Bearbeiten

Bekannte Probleme, die sich mit Backtracking lösen lassen, sind unter anderem:

Viele dieser Probleme sind NP-vollständig.

Prolog Bearbeiten

Die Programmiersprache Prolog benutzt Backtracking zur Antwort-Generierung. Dabei probiert der Interpreter alle Beweismöglichkeiten der Reihe nach durch. Entscheidungspunkte werden dabei als Choice Point bezeichnet. Der so genannte Cut-Operator ! kann benutzt werden, um Choice-Points zu verwerfen.

Literatur Bearbeiten

  • Robert Sedgewick: Algorithmen. 2. Auflage. Addison-Wesley, München 2002, ISBN 3-8273-7032-9.
  • Niklaus Wirth: Algorithmen und Datenstrukturen. 3., überarbeitete Auflage. Teubner, Stuttgart 1983, ISBN 3-519-02250-8.

Weblinks Bearbeiten

Commons: Backtracking – Sammlung von Bildern, Videos und Audiodateien
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Der Begriff Rucksetzverfahren oder englisch Backtracking Ruckverfolgung bezeichnet eine Problemlosungsmethode innerhalb der Algorithmik Backtracking arbeitet nach dem Prinzip der Tiefensuche Inhaltsverzeichnis 1 Allgemeiner Algorithmus 2 Zeitkomplexitat 3 Beispiele 4 Prolog 5 Literatur 6 WeblinksAllgemeiner Algorithmus BearbeitenBacktracking geht nach dem Versuch und Irrtum Prinzip trial and error vor das heisst es wird versucht eine erreichte Teillosung zu einer Gesamtlosung auszubauen Wenn absehbar ist dass eine Teillosung nicht zu einer endgultigen Losung fuhren kann wird der letzte Schritt beziehungsweise werden die letzten Schritte zuruckgenommen und es werden stattdessen alternative Wege probiert Auf diese Weise ist sichergestellt dass alle in Frage kommenden Losungswege ausprobiert werden konnen Prinzip des Ariadnefadens Mit Backtracking Algorithmen wird eine vorhandene Losung entweder gefunden unter Umstanden nach sehr langer Laufzeit oder es kann definitiv ausgesagt werden dass keine Losung existiert Backtracking wird meistens am einfachsten rekursiv implementiert und ist ein prototypischer Anwendungsfall von Rekursion Funktion FindeLosung Stufe Vektor 1 wiederhole solange es noch neue Teil Losungsschritte gibt a wahle einen neuen Teil Losungsschritt b falls Wahl gultig ist I erweitere Vektor um Wahl II falls Vektor vollstandig ist return true Losung gefunden sonst falls FindeLosung Stufe 1 Vektor return true Losung sonst mache Wahl ruckgangig Sackgasse Backtracking 2 Da es keinen neuen Teil Losungsschritt gibt return false Keine Losung Zeitkomplexitat BearbeitenBei der Tiefensuche werden bei maximal z displaystyle z nbsp moglichen Verzweigungen von jeder Teillosung aus und einem Losungsbaum mit maximaler Tiefe von N displaystyle N nbsp im schlechtesten Fall 1 z z 2 z 3 z N displaystyle 1 z z 2 z 3 dotsb z N nbsp Knoten erweitert Die Tiefensuche und somit auch Backtracking haben im schlechtesten Fall mit O z N displaystyle O z N nbsp und einem Verzweigungsgrad z gt 1 displaystyle z gt 1 nbsp eine exponentielle Laufzeit Je grosser die Suchtiefe n displaystyle n nbsp desto langer dauert die Suche nach einer Losung Daher ist das Backtracking primar fur Probleme mit einem kleinen Losungsbaum geeignet Es gibt jedoch Methoden mit welchen die Zeitkomplexitat eines Backtracking Algorithmus verringert werden kann Diese sind unter anderem Heuristiken Akzeptanz von Naherungslosungen und Fehlertoleranz Durchschnittliche EingabemengeBeispiele BearbeitenBekannte Probleme die sich mit Backtracking losen lassen sind unter anderem Damenproblem nbsp Losung des Damenproblems mit Hilfe von BacktrackingGegeben ist ein Schachbrett mit n n displaystyle n times n nbsp Feldern je n displaystyle n nbsp Spalten und Reihen Man positioniere nun N displaystyle N nbsp Damen so dass sie sich nicht gegenseitig schlagen konnen Das Damenproblem gehort zu der Klasse der Constraint Satisfaction Probleme Springerproblem Gegeben ist ein Schachbrett mit m n displaystyle m times n nbsp Feldern Ein Springer kann von einer bestimmten Position aus N 8 displaystyle N 8 nbsp verschiedene Sprunge ausfuhren falls diese nicht uber den Rand des Brettes hinausfuhren Gesucht ist ein Weg bei dem alle Felder genau einmal besucht werden Springerweg Mit Hilfe von Backtracking konnen alle moglichen Wege systematisch durchprobiert werden Ein Zug ist dabei gultig wenn das neue Feld innerhalb des Spielfeldes liegt und noch unbesucht ist Es gibt jedoch weitaus effizientere Verfahren fur die Losung dieses Problems Rucksackproblem Gegeben ist ein Rucksack mit der Tragfahigkeit B displaystyle B nbsp Weiterhin sind N displaystyle N nbsp Gegenstande mit Werten und Gewichten gegeben Nun sollen Gegenstande so ausgewahlt werden die in der Summe einen maximalen Wert ergeben aber deren Gesamtgewicht die Tragfahigkeit des Rucksacks nicht uberschreitet Farbeproblem Gegeben ist eine Landkarte mit B displaystyle B nbsp Landern welche mit N displaystyle N nbsp verschiedenen Farben eingefarbt werden sollen Gesucht ist eine Farbkombination bei welcher alle Lander die eine gemeinsame Grenze besitzen unterschiedlich eingefarbt sind Solitar Brettspiel Zu Beginn stehen 32 Steine Stifte oder Kugeln auf einem Brett davon werden in 31 Zugen je einer entfernt indem man ihn mit einem anderen Stein uberspringt Sudoku Die Zahlen von 1 bis 9 sollen nach gewissen Regeln in ein 9 9 displaystyle 9 times 9 nbsp Feld unterteilt in neun 3 3 displaystyle 3 times 3 nbsp Felder eingetragen werden Str8ts Die Zahlen von 1 bis 9 sollen nach gewissen Regeln in ein 9 9 displaystyle 9 times 9 nbsp Feld eingetragen werden Auch dieser Ratseltyp ist mit Backtracking gut zu losen Wegsuche von A nach B in einem Graphen Backtracking wird auch eingesetzt fur die Wegsuche von A nach B in einem Graphen etwa fur die Suche nach Verbindungen in einem Fahrplan oder zum Bestimmen einer Route in einem Routenplaner oder eines Weges durch ein Labyrinth Viele dieser Probleme sind NP vollstandig Prolog BearbeitenDie Programmiersprache Prolog benutzt Backtracking zur Antwort Generierung Dabei probiert der Interpreter alle Beweismoglichkeiten der Reihe nach durch Entscheidungspunkte werden dabei als Choice Point bezeichnet Der so genannte Cut Operator kann benutzt werden um Choice Points zu verwerfen Literatur BearbeitenRobert Sedgewick Algorithmen 2 Auflage Addison Wesley Munchen 2002 ISBN 3 8273 7032 9 Niklaus Wirth Algorithmen und Datenstrukturen 3 uberarbeitete Auflage Teubner Stuttgart 1983 ISBN 3 519 02250 8 Weblinks Bearbeiten nbsp Commons Backtracking Sammlung von Bildern Videos und Audiodateien Interaktiver Kurs zum Thema Backtracking vom Matheprisma Projekt an der Universitat Wuppertal Abgerufen von https de wikipedia org w index php title Backtracking amp oldid 237330081