A2.2 Backtracking

Autoren: Urs Battaglia, Harald Pierhöfer

Für viele Probleme in der Informatik gibt es keine effizienten Algorithmen. Der einfachste Ansatz zur Lösung eines Problems besteht im Probieren aller potenziellen Lösungen, bis die richtige gefunden ist.
Backtracking (Rücksetzverfahren) ist ein systematisches Versuch-und-Irrtum-Prinzip (trial and error). Es wird versucht, eine erreichte Teillösung schrittweise 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 bzw. die letzten Schritte zurückgenommen (nach vorn wenn möglich, zurück wenn nötig), und es werden stattdessen alternative Wege probiert.

1. Backtracking ist eine „Brute-Force-Suche“ welche je nach Grösse des Problems sehr lange dauern kann.
2. Durch das Ausprobieren aller möglicher Lösungswegge wird sichergestellt, dass der Algorithmus mit einer korrekten Lösung endet, oder aber bestätigt, dass überhaupt keine Lösung existiert.
3. Ein Algorithmus kann wahlweisee eine, mehrere oder auch alle Lösungen eines Problems bestimmen.
4. Mittels Backtracking entstehen relativ „dumme“ Algorithmen, welche spezielle Eigenschaften eines Problems nur teilweise berücksichtigen. Die Algorithmen sind daher vergleichsweise langsam, dafür aber stabil, vielseitig und zielsicher.
5. Die Wahl der Datenstruktur bestimmt stark die effizienz des Ansatzes — JH

1. Ich weiss, nach welchem Prinzip das Backtracking-Verfahren den Lösungsbaum durchsucht.
2. Ich kann einige Beispiele aufzählen, in welchen mit dem Backtracking-Verfahren die Lösung gefunden werden kann.
3. Ich weiss, dass Backtracking iterativ oder auch rekursiv programmiert werden kann, und bin in der Lage, für beide Varianten ein Grundgerüst (in Pseudocode) anzugeben.
4. Ich weiss, wie die Laufzeit eines Backtracking-Verfahrens im schlechtesten Fall ansteigt, und was dies für grosse Suchbäume bedeutet.
5. Eventeull: Ich kenne Möglichkeiten, die Laufzeit zu verkürzen

• Damenproblem
• Springerproblem
• Färbeproblem
• Rucksackproblem
• Solitär („Stäbchenhüpfen“)
• Magisches-Quadrat
• Sudoku
• Kartenspiel (korrektes Legen von 9 Karten zu einem Quadrat)
• Tangram
• Traveling Salesman für kleine Graphen

• A2 Rekursion
• P3 Closures: Methoden, Prozeduren und Funktionen

• Backtracking mit Heuristiken (Vortrag)

• Mit dem Faden der Ariadne aus dem Labyrinth. — Paul Miotti 2008/06/24
• Fehlende Problemdefinition → Intelligente Suche im Lösungsraus — JH
• Unterscheiden zwischen Entscheidungs- vs. Optimierungsproblem — JH