Backtracking

Definition: Backtracking ist das Zurückverfolgen im Rahmen einer baumartigen Lösungssuche von einer Sackgasse aus zu einer vorhergehenden Stelle im Lösungsbaum, von der aus ein erneuter Lösungsversuch gestartet werden soll.
Also: Durchprobieren aller sinnvollen Möglichkeiten

Prinzip: “trial and error”

Einige Probleme, die mit Backtracking gelöst werden können:

- Labyrinthsuche
- Färbungsprobleme für Karten und Graphen
- Sudoku

- n-Damen-Problem
- Springerproblem
- Rucksackproblem (bei wenigen Gegenständen)

Arbeiten Sie die Seiten auf Mathe-Prisma zum Backtracking gründlich durch!

Im Labyrinth

Demonstration im Delphi-Programm

Prinzip
1. Bin ich hier am Ziel?
- Ja: Fertig!
- Nein: Weiter mit 2.!
2. War ich hier bereits? Ist das etwa eine Sackgasse?
- Ja: Zurück!
-- Nein: Weiter mit 3.!
3. Markiere diesen Weg!
4. Gehe den nächsten Weg!
5. War dieser Weg erfolgreich?
- Ja: Gib Erfolg zurück!
Nein: Versuche weitere Wege von hier aus!
6. Nimm die Markierung wieder weg!
7. Es gibt keine Lösung von hier aus.

AB L

Anwendungsbeispiele
- finde den Weg vom Eingang zum Ausgang
- Entscheidungsmöglichkeitenan jeder Kreuzung: gerade aus, rechts, links
- "Faden der Ariadne"

Der Backtracking Algorithmus ist der einfachste, um eine Lösung für das Labyrinth Problem zu finden. Dabei wird nicht der kürzeste Weg, sondern irgendein Weg durch das Labyrinth gesucht und ausgegeben. Es kann sein, daß dabei der kürzeste, der längste oder irgendeiner dazwischen gefunden wird.

Um den Weg durch das Labyrinth zu finden, geht der Backtracking Algorithmus bei einem Knoten eine Verbindung zu einem anderen Knoten und markiert diese Verbindung. Trifft der Algorithmus auf einen Knoten, der keine weiteren unmarkierten Verbindungen hat, dann wird dieser Knoten auf der Verbindung verlassen, mit der der Algorithmus auf diesen Knoten gelangte (Backtrack).

Der Algorithmus bricht ab, wenn er entweder den Knoten mit dem Ausgang gefunden hat, oder wenn er wieder am Knoten mit dem Eingang - kein Weg führt durch das Labyrinth - angelangt ist und keine unmarkierten Verbindungen vorhanden sind.

Damenproblem

- klassisches Schachproblem
- zuerst von M. Bezzel 1845 in einer Schachzeitung veröffentlicht
- sämtliche 92 Lösungen für 8 Damen 1850 durch den blinden Dr. Nauk publiziert
Allgemein formuliert: Wie viele Möglichkeiten gibt es, n Damen auf einem n x n großes Schachfeld so zu platzieren, ohne dass sich zwei oder mehr schlagen können?
Damenproblem mit 8 Damen
Hefteintrag - Quelltext zum Delphi-Programm (8 Damen), 2 Aufgaben Programm dazu

Das Springerproblem

Andere Problemstellungen

Karten sortieren - Visualisierung Nr. 1

Magische Quadrate