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.

Info

Das Zurückverfolgen wird als eine wichtige Technik zur Lösung von Problemen und Rätseln im Zusammenhang mit der Beschränkungszufriedenheit angesehen.

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.

Sie haben noch Fragen?

Kontaktieren Sie uns



Free Account erstellen


Weitere Inhalte


Keine Kommentare vorhanden


Du hast eine Frage oder eine Meinung zum Artikel? Teile sie mit uns!

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind markiert *

*
*