Backtracking

Beim Backtracking, auf Deutsch das Rücksetztverfahren, handelt es sich um eine Problemlösungsmethode, die auf einem Algorithmus basiert. Es werden einige oder alle Lösungen für bestimmte Berechnungsprobleme gesucht.

Anwendung

Der Algorithmus versucht zuerst ein Teilproblem zu lösen und dann wird versucht rekursiv, die anderen Teilprobleme auf Basis des erst gelösten Problems zu lösen. Wenn das momentane Problem nicht gelöst werden kann, wird eine andere Lösung gesucht, welche auf die vorherigen Probleme angewendet werden kann.

Das Backtracking kann nur bei Problemen angewendet werden, welche das Konzept der partiellen Kandidatenlösung akzeptieren und ermöglicht somit einen schnellen Test, ob die Kandidatenlösung eine vollständige Lösung für die einzelnen Probleme darstellt.

Wann wird Backtracking in der Regel eingesetzt?

Backtrackingansätze werden bei drei Arten von Problemen eingesetzt:

• Entscheidungsproblem – Hier suchen wir nach einer realisierbaren Lösung.
• Optimierungsproblem – Dabei suchen wir nach der besten Lösung.
• Aufzählungsproblem – Hier finden wir alle möglichen Lösungen.