Backtracking

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

Backtracking arbeitet nach dem Prinzip der Tiefensuche

Inhaltsverzeichnis

Allgemeiner Algorithmus

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 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 FindeLoesung (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 (FindeLoesung(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

Bei der Tiefensuche werden bei maximal z möglichen Verzweigungen von jeder Teillösung aus und einem Lösungsbaum mit maximaler Tiefe von N im schlechtesten Fall 1+z+z^2+z^3+\ldots+z^N Knoten erweitert.

Die Tiefensuche und somit auch Backtracking haben im schlechtesten Fall mit O(zN) eine exponentielle Laufzeit. Bei großer Suchtiefe n und Verzweigungsgrad z > 1 dauert die Suche somit oft sehr lange. 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

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

Damenproblem

Lösung des Damenproblems mit Hilfe von Backtracking

Gegeben ist ein Schachbrett mit n*n Feldern (je n Spalten und Reihen). Man positioniere nun N Damen so, dass sie sich nicht gegenseitig schlagen können. Das Damenproblem gehört zu der Klasse der Constraint-Satisfaction-Probleme.

Springerproblem

Gegeben ist ein „Schachbrett“ mit m\times n Feldern. Ein Springer kann von einer bestimmten Position aus N = 8 verschiedene Sprünge ausführen, falls diese nicht über den Rand des Brettes hinausführen. Gesucht ist ein Weg, bei dem alle Felder genau einmal besucht werden (Springerweg). Mit Hilfe von Backtracking können alle möglichen Wege systematisch durchprobiert werden. Ein Zug ist dabei gültig, wenn das neue Feld innerhalb des Spielfeldes liegt und noch unbesucht ist. Es gibt jedoch weitaus effizientere Verfahren für die Lösung dieses Problems.

Rucksackproblem

Gegeben ist ein Rucksack mit der Tragfähigkeit B. Weiterhin sind N Gegenstände mit Werten und Gewichten gegeben. Nun sollen Gegenstände so ausgewählt werden, die in der Summe einen maximalen Wert ergeben, aber deren Gesamtgewicht die Tragfähigkeit des Rucksacks nicht überschreitet.

Färbeproblem

Gegeben ist eine Landkarte mit B Ländern, welche mit N verschiedenen Farben eingefärbt werden sollen. Gesucht ist eine Farbkombination, bei welcher alle Länder, die eine gemeinsame Grenze besitzen, unterschiedlich eingefärbt sind.

Solitär-Brettspiel

Zu Beginn stehen 32 Steine (Stifte oder Kugeln) auf einem Brett; davon werden in 31 Zügen je einer entfernt, indem man ihn mit einem anderen Stein überspringt.

Sudoku

Die Zahlen von 1 bis 9 sollen nach gewissen Regeln in ein 9*9-Feld (unterteilt in neun 3*3-Felder) eingetragen werden.

Str8ts

Die Zahlen von 1 bis 9 sollen nach gewissen Regeln in ein 9*9-Feld eingetragen werden. Auch dieser Rätseltyp ist mit Backtracking gut zu lösen.

Wegsuche von A nach B in einem Graphen

Backtracking wird auch eingesetzt für die Wegsuche von A nach B in einem Graphen, etwa für die Suche nach Verbindungen in einem Fahrplan oder zum Bestimmen einer Route in einem Routenplaner oder eines Weges durch ein Labyrinth.

PROLOG

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

Weblinks


Wikimedia Foundation.

Synonyme:

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Backtracking — is a type of algorithm that is a refinement of brute force search. [cite web | url=http://www.cse.ohio state.edu/ gurari/course/cis680/cis680Ch19.html#QQ1 51 128 Backtracking algorithms | title=CIS 680: DATA STRUCTURES: Chapter 19: Backtracking… …   Wikipedia

  • Backtracking — Trial and Error Verfahren; Rücksetzalgorithmus * * * Back|tra|cking 〈[bæ̣ktrækıŋ] n.; od. s; unz.; EDV〉 Programmier bzw. Suchstrategie, die von bestimmten Problempunkten ausgehend Lösungswege entwickelt, wobei der bis dahin aktuelle (Daten… …   Universal-Lexikon

  • Backtracking — Retour sur trace Le retour sur trace, appelé aussi backtracking en anglais, consiste à revenir légèrement en arrière sur des décisions prises afin de sortir d un blocage. La méthode des essais et erreurs constitue un exemple simple de… …   Wikipédia en Français

  • backtracking — grįžimų metodas statusas T sritis informatika apibrėžtis Algoritmavimo metodas, kai sprendimas grindžiamas variantų tikrinimu ir, pasiekus aklavietę, grįžimu vienu žingsniu atgal. Grįžimų metodas labiausiai taikomas sprendžiant labirinto tipo… …   Enciklopedinis kompiuterijos žodynas

  • backtracking — The backwards movement of RNA polymerase along the DNA template to a state more stable than that encountered when some base pairs disrupt the attachment of the 3′ end from the active transcription site …   Medical dictionary

  • Backtracking — Back|tra|cking 〈[bæ̣ktrækıŋ] n.; Gen.: od. s; Pl.: unz.; EDV〉 Programmier bzw. Suchstrategie, die von bestimmten Problempunkten ausgehend Lösungswege entwickelt, wobei der bis dahin aktuelle (Daten )Bestand gesichert (u. gegebenenfalls… …   Lexikalische Deutsches Wörterbuch

  • Backtracking — Suchmethode. 1. Prinzip: An denjenigen Punkten des Suchvorgangs, an denen zur Fortsetzung der Suche eine Auswahlentscheidung zwischen mehreren Möglichkeiten getroffen werden muss, wird zunächst der aktuelle Zustand festgehalten, bevor man die… …   Lexikon der Economics

  • backtracking — v. go backwards; retrace one s footsteps or path …   English contemporary dictionary

  • backtracking — backˈtracking noun • • • Main Entry: ↑back …   Useful english dictionary

  • Backtracking-Verfahren —   [ bæktrækɪȖ , englisch »sich zurückziehen«], Versuch und Irrtum …   Universal-Lexikon

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”