Der Begriff Rücksetzverfahren oder englisch Backtracking (engl. Rückverfolgung) bezeichnet eine
Problemlösungsmethode innerhalb der
Algorithmik. 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.
Mehr unter Wikipedia.org...
Free Download Now!
