Schule 
Studium 
Ausbildung 
Karteikarten 
StudySmarter AI 
Notizen 
Lernplan 
Spaced Repetition 
Lernsets 
Finde einen Job 
Ausbildungen 
Magazine 
Mobile App 
Für Unternehmen 
Springe zu einem wichtigen Kapitel
Damit Du das nächste Mal besser Bescheid weißt, lernst Du in diesem Artikel alles Wichtige über das Backtracking.
Backtracking Bedeutung
Das Backtracking gehört zu den Methoden der Problemlösung in der Informatik. Es zeichnet sich primär dadurch aus, dass das Problem zerlegt und jede mögliche Lösung für ein Problem systematisch ausprobiert wird. Man bezeichnet die Methode auch als Tiefensuche.1
Manchmal hört man im Kontext des Backtracking auch das Schlagwort "Trial-and-Error". Das trifft den Kern des Backtracking sehr gut, da bewusst Fehlversuche in Kauf genommen werden, um am Ende die korrekte Lösung oder korrekten Lösungen zu finden.
Schrittweises Backtracking
Der Algorithmus, auf dem das Backtracking basiert, sorgt für ein systematisches Ausprobieren aller möglichen Lösungen, bis eine dieser gefunden wurde, oder festzustellen ist, dass eine solche für das spezifische Problem nicht existiert.
Dadruch, dass die Möglichkeiten in einzelnen Schritten durchlaufen werden, spricht man auch von schrittweisem Backtracking.2
Backtracking Algorithmus
Wie schon erwähnt, liegt die Methodik des Backtracking darin, alle Möglichkeiten rekursiv auszuprobieren und so an einem gewissen Punkt auf die richtige Lösung zu stoßen.
Um das einmal zu verdeutlichen, kannst Du ein bekanntes Anwendungsbeispiel für das Backtracking zur Hilfe nehmen: das N-Damen-Problem.
N-Damen-Problem
Kurz zusammengefasst geht es bei diesem schachmathematischen Problem darum, eine bestimmte Anzahl (n) von Damen auf ein Schachbrett mit einer gewissen Größe (n mal n) zu platzieren. Dabei dürfen keine Damen auf der gleichen senkrechten oder waagerechten Reihe sowie auf der gleichen Diagonale stehen.
In der Regel wird dieses Problem auf einem 8x8 Schachbrett mit 8 Damen veranschaulicht. Der Einfachheit halber lernst Du das Problem hier auf einem 4x4 Schachbrett mit 4 Damen kennen.
Die erste Dame kann konfliktfrei platziert werden. Da das Feld oben links die erste Möglichkeit der Platzierung darstellt, wird die erste Dame dort platziert.
Die zweite Dame kann nicht in der gleichen Spalte wie die erste platziert werden. Dadurch fallen die drei verbleibenden Felder der 1. Spalte durch den Algorithmus durch und werden nicht zum Teil der Lösung. Die Dame muss also mindestens in der 2. Spalte platziert werden.
In Feld 1 und 2 der zweiten Spalte kann die Dame auch nicht platziert werden, da sonst wieder 2 Damen in einer Reihe bzw. Diagonale stehen würden, was durch die Regeln verboten wird. Auch diese beiden Felder fallen also durch den Algorithmus und sind nicht Teil der Lösung.
Im 3. Feld der 2. Spalte kann die Dame erstmals stehen, ohne eine Regel zu verletzen. Dementsprechend wird sie dort platziert.
Bei der dritten Dame wird ebenso vorgegangen: In Spalte 2 kann sie aufgrund der Regeln nicht stehen. Im 1. Feld der 3. Spalte würde sie mit der ersten Dame in Konflikt geraten. Auf den anderen Feldern der 3. Spalte würde sie mit der 2. Dame kollidieren. Daher muss zur 2. Dame zurückgekehrt und ihre Position geändert werden. Sie kann nur noch um 1 Feld nach unten verschoben werden, also wird genau das getan. Danach kann die dritte Dame auf dem 2. Feld der 3. Spalte ohne Konflikte platziert werden.
Nur noch eine Dame übrig. Kann ja nicht so schwer sein, oder? Tatsächlich gibt es aktuell auf den verbleibenden Feldern keine Möglichkeit, die vierte Dame konfliktfrei zu platzieren. Das ist der Punkt, an dem das Backtracking über mehrere Schritte hinweg durchgeführt werden muss.
Da die 4. Dame keine sichere Platzierung erhalten kann, muss eine oder mehrere der bisherigen Lösungskomponenten falsch sein. Um herauszufinden, welche korrekt sind, wird schrittweise zu den vorhergehenden Schritten zurückgekehrt und die verbleibenden Möglichkeiten ausprobiert.
Die dritte Dame kann weder im 3. noch im 4. Feld stehen. Also wird sie vorerst entfernt und später erneut auf mögliche Positionen getestet. Da es für die 2. Dame auch keine weitere sichere Platzierung gibt, wird auch sie vom Brett genommen.
Nun steht nur noch die erste Dame auf dem Brett, da bis zu diesem Punkt zurückgegangen wurde. Diese wird jetzt um eine Position nach unten verschoben.
Die zweite Dame wird wieder platziert. Auf den ersten 3 Feldern der zweiten Spalte findet sie keinen sicheren Platz, auf dem vierten Feld steht sie jedoch sicher, also kann die dritte Dame platziert werden. Schon auf dem 1. Feld kann sie konfliktfrei positioniert werden.
Fehlt nur noch die vierte Dame: Auf den ersten beiden Feldern der vierten Spalte steht sie in Konflikt mit anderen Damen. Auf dem dritten Feld steht sie – wie alle anderen Damen auch – in einer konfliktfreien Position. Damit ist das Problem gelöst.
Backtracking Beispiel
Neben dem N-Damen-Problem existieren einige andere gängige Beispiele, welche mithilfe von Backtracking gelöst werden können.
Diese Beispiele für das Backtracking können auch Probleme genannt werden, konkret mithilfe von Backtracking lösbare Probleme.
Backtracking im Labyrinth
Ein sehr bekanntes Beispiel steht am Anfang dieser Erklärung – das Labyrinth. Natürlich kann man planlos durch ein solches laufen und darauf hoffen, das Ziel zu finden. Mithilfe des Backtracking und einer gewissen strukturierten Herangehensweise geht dies allerdings einfacher und vielleicht sogar schneller.
Bevor Du das Labyrinth betrittst, überlegst Du Dir, in welche Richtung Du an jeder Kreuzung zuerst gehen willst, beispielsweise links. Sollte diese Richtung in eine Sackgasse führen, gehst Du zur vorherigen Kreuzung zurück. Dann nimmst Du den Weg, der am weitesten links liegt, jedoch nicht den, den Du schon genommen hast. Das führst Du fort, bis Du die nächste Kreuzung erreichst. Sollten alle Abzweige einer Kreuzung in eine Sackgasse führen, musst Du zur Kreuzung davor zurück, und die restlichen Abzweige ausprobieren.
Backtracking in anderen Problemen
Ein weiteres Problem aus der Schachwelt kann ebenfalls durch Backtracking gelöst werden. Beim Springerproblem liegt das Ziel darin, ohne das Spielbrett zu verlassen, mit gültigen Zügen jedes Feld des Brettes genau einmal zu besuchen.
Das Backtracking ist hier nicht die effizienteste Lösungsmethode, jedoch findet man so früher oder später sicher zu einer Lösung.
Auch durch Backtracking lösbar ist das Färbeproblem. Ziel ist es, eine bestimmte Anzahl von Ländern auf einer Landkarte in einer bestimmten Anzahl unterschiedlicher Farben zu färben. Dabei dürfen Länder mit einer gemeinsamen Grenze nicht in der gleichen Farbe angemalt werden.
Backtracking und Rekursion
Die zwei gängigsten Problemlösungsverfahren der Algorithmik sind Backtracking und Rekursion. Tatsächlich ist es so, dass die Rekursion eine Implementierung von Backtracking nutzen kann, um zur Lösung von Problemen zu kommen. Damit Du einen kurzen Überblick erhältst, folgt nun eine schnelle Einführung in die Rekursion.
Die Rekursion ist eine Strategie zur Problemlösung, welche oft in der Informatik angewandt wird. Im Prinzip basiert sie auf dem sich selbst Aufrufen einer Funktion oder Prozedur, wodurch diese wiederholt angewandt wird.
Um einen Algorithmus zu implementieren, der Backtracking anwendet, kann der Code einen rekursiven Selbstaufruf einer Funktion beinhalten. Dies ist die gängigste Form der Implementierung eines Backtracking-Algorithmus. Die Abbruchbedingung dieser ist dann erreicht, wenn keine ungetesteten möglichen Lösungen mehr zur Verfügung stehen. Dann gibt es keine Lösung für das Problem.
Durch die Zerlegung des Problems, welche durch die Rekursion automatisch gegeben ist, wird das Backtracking recht effizient auf den zu lösenden Sachverhalt angewandt.
Eine andere Möglichkeit der Implementierung liegt darin, eine Iteration einer Funktion zu verwenden.
Backtracking – Das Wichtigste
- Backtracking Bedeutung: Backtracking ist ein Problemlösungsverfahren der Algorithmik.
- Schrittweises Backtracking: Probleme systematisch nach einer Lösung durchsuchen.
- Backtracking Algorithmus: Probleme werden in kleinere, leichter zu lösende Teilprobleme zerlegt und diese nach möglichen Lösungen durchsucht.
- Backtracking Beispiel: Bekannte Probleme, die mit Backtracking gelöst werden können, sind:
- das N-Damen-Problem
- das Färbeproblem
- das Finden des Ausgangs eines Labyrinths
- Backtracking Rekursion: Implementiert werden kann Backtracking z. B. mithilfe von Rekursion.
Nachweise
- Niklaus Wirth (1983). Algorithmen und Datenstrukturen. Teubner.
- Robert Sedgewick (2000). Algorithmen. Addison-Wesley.
Lerne schneller mit den 2 Karteikarten zu Backtracking
Melde dich kostenlos an, um Zugriff auf all unsere Karteikarten zu erhalten.
Häufig gestellte Fragen zum Thema Backtracking
Was ist Backtracking?
Das Backtracking gehört zu den Methoden der Problemlösung in der Informatik. Sie zeichnet sich primär dadurch aus, dass das Problem zerlegt und jede mögliche Lösung für ein Problem systematisch ausprobiert wird.
Wie funktioniert Backtracking?
Mit Backtracking-Algorithmen wird eine vorhandene Lösung durch systematisches Probieren gefunden oder es kann definitiv festgestellt werden, dass es keine Lösung für das Problem gibt.
Über StudySmarter
StudySmarter ist ein weltweit anerkanntes Bildungstechnologie-Unternehmen, das eine ganzheitliche Lernplattform für Schüler und Studenten aller Altersstufen und Bildungsniveaus bietet. Unsere Plattform unterstützt das Lernen in einer breiten Palette von Fächern, einschließlich MINT, Sozialwissenschaften und Sprachen, und hilft den Schülern auch, weltweit verschiedene Tests und Prüfungen wie GCSE, A Level, SAT, ACT, Abitur und mehr erfolgreich zu meistern. Wir bieten eine umfangreiche Bibliothek von Lernmaterialien, einschließlich interaktiver Karteikarten, umfassender Lehrbuchlösungen und detaillierter Erklärungen. Die fortschrittliche Technologie und Werkzeuge, die wir zur Verfügung stellen, helfen Schülern, ihre eigenen Lernmaterialien zu erstellen. Die Inhalte von StudySmarter sind nicht nur von Experten geprüft, sondern werden auch regelmäßig aktualisiert, um Genauigkeit und Relevanz zu gewährleisten.
Erfahre mehr