Was ist Backtracking?
Backtracking ist ein Algorithmus zum Erfassen einiger oder aller Lösungen für gegebene Berechnungsprobleme, insbesondere für Constraint-Zufriedenheitsprobleme. Der Algorithmus kann nur für Probleme verwendet werden, die das Konzept einer ‚partiellen Kandidatenlösung‘ akzeptieren und ermöglicht einen schnellen Test, um zu sehen, ob die Kandidatenlösung eine vollständige Lösung sein kann. Backtracking wird als eine wichtige Technik zur Lösung von Constraint-Zufriedenheitsfragen und Rätseln angesehen. Es wird auch als eine großartige Technik zum Parsen angesehen und bildet auch die Basis vieler logischer Programmiersprachen.
Backtracking hilft bei der Lösung eines allgemeinen Problems, indem es eine Lösung für das erste Teilproblem findet und dann rekursiv versucht, andere Teilprobleme basierend auf der Lösung des ersten Problems zu lösen. Wenn das aktuelle Problem nicht gelöst werden kann, wird der Schritt rückgängig gemacht und die nächste mögliche Lösung wird auf die vorherigen Schritte angewendet und geht dann weiter. In der Tat ist eines der wichtigsten Dinge beim Zurückverfolgen Rekursion. Es wird auch als eine Methode der erschöpfenden Suche mit ‚Teile und herrsche‘ betrachtet. Ein Backtracking-Algorithmus endet, wenn für das erste Teilproblem keine Lösungen mehr vorhanden sind.
Backtracking ist ein Algorithmus, der helfen kann, Nichtdeterminismus zu implementieren. Es dauert eine Tiefensuche eines gegebenen Problemraums. Es wird hauptsächlich in logischen Programmiersprachen wie Prolog verwendet. Überall dort, wo Backtracking angewendet werden kann, ist es schneller als die Brute-Force-Technik, da es eine große Anzahl von Kandidaten mit einem einzigen Test eliminiert.