Coder Wiki | Algorithmen

Backtracking geht nach dem Versuch-und-Irrtum-Prinzip (trial and error) vor, d.h. 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, und es werden stattdessen alternative Wege probiert. Auf diese Weise ist sichergestellt, dass alle in Frage kommenden Lösungswege ausprobiert werden können. 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.

Beispielanwendungen

n-Dame Problem ?
Knapsack / Rucksack Problem

Informationen

Automatisches Backtracking ist fester Bestandteil der Programmiersprache Prolog und der PROLOG-Systeme.