Rückzieher

Definition - Was bedeutet Backtracking?

Backtracking ist ein Algorithmus zum Erfassen einiger oder aller Lösungen für bestimmte Rechenprobleme, insbesondere für Probleme mit der Erfüllung von Einschränkungen. Der Algorithmus kann nur für Probleme verwendet werden, die das Konzept einer „Teilkandidatenlösung“ akzeptieren und einen schnellen Test ermöglichen, um festzustellen, ob die Kandidatenlösung eine vollständige Lösung sein kann. Das Zurückverfolgen wird als wichtige Technik zur Lösung von Problemen und Rätseln bei der Erfüllung von Einschränkungen angesehen. Es wird auch als eine großartige Technik zum Parsen angesehen und bildet auch die Grundlage vieler logischer Programmiersprachen.

Technische.me erklärt Backtracking

Backtracking hilft bei der Lösung eines Gesamtproblems, 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 behoben werden kann, wird der Schritt zurückverfolgt und die nächstmögliche Lösung auf die vorherigen Schritte angewendet. Anschließend wird fortgefahren. Tatsächlich ist die Rekursion eines der wichtigsten Dinge beim Zurückverfolgen. Es wird auch als eine Methode der erschöpfenden Suche unter Verwendung von Teilen und Erobern angesehen. Ein Backtracking-Algorithmus endet, wenn für das erste Unterproblem keine Lösungen mehr verfügbar sind.

Backtracking ist ein Algorithmus, mit dessen Hilfe der Nichtdeterminismus implementiert werden kann. Es wird eine Tiefensuche in einem bestimmten Themenbereich durchgeführt. 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 eine große Anzahl von Kandidaten mit einem einzigen Test eliminiert wird.