Backtracking
Copyright © Shutterstock / OpturaDesign
Was ist Backtracking?
Definition
Backtracking (Rückverfolgung) ist eine allgemeine algorithmische Technik, die die Suche nach jeder möglichen Kombination berücksichtigt, um ein Optimierungsproblem zu lösen. Backtracking wird auch als Tiefensuche oder Verzweigen und Binden bezeichnet.
Eine dynamische Programmierung und Greedy-Algorithmen können als Optimierung des Backtrackings betrachtet werden, weshalb diese Technik nützlich ist, um fortgeschrittene Konzepte zu verstehen.
Ziel
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. Die Rekursion ist beim Zurückverfolgen ein wichtiger Teil. Ein Backtracking Algorithmus endet, wenn für das erste Teilproblem kein Lösung mehr erzielt werden kann.
Konzeptionell werden die Teilkandidaten als Knoten einer Baumstruktur, dem potentiellen Suchbaum, dargestellt. Jeder Teilkandidat ist der “Elternteil” der Kandidaten, der sich von ihm durch einen einzigen Erweiterungsschritt unterscheidet: Die Blätter des Baumes sind die Teilkandidaten, die nicht weiter ausgedehnt werden können.
Der Backtracking Algorithmus durchläuft diesen Suchbaum rekursiv von der Wurzel abwärts in der Reihenfolge erster Ordnung. An jedem Knoten “c” prüft der Algorithmus, ob “c” zu einer gültigen Lösung vervollständigt werden kann. Wenn dies nicht möglich ist, wird der gesamte unter “c” verwurzelte Unterbaum übersprungen (beschnitten). Andernfalls prüft der Algorithmus, ob “c” selbst eine gültige Lösung ist und meldet dies dem Benutzer; er zählt rekursiv alle Unterbäume von “c” auf. Die zwei Tests und die untergeordneten Knoten jedes Knotens werden durch vom Benutzer gegebene Prozeduren definiert.
Daher ist der tatsächliche Suchbaum, der vom Algorithmus durchlaufen wird, nur ein Teil des Potentialbaums. Die Gesamtkosten des Algorithmus sind die Anzahl der Knoten des tatsächlichen Baums, multipliziert mit den Kosten des Erhaltens und Verarbeitens jeden Knotens. Diese Tatsache sollte berücksichtigt werden, wenn der potenzielle Suchbaum ausgewählt und der Beschneidungstest implementiert ist.
- root (P):
Den Teilkandidaten an der Wurzel des Suchbaums zurückgeben. - reject (P, c): Gibt nur dann “wahr/true” zurück, wenn der Teilkandidat “c” nicht vollständig ist.
- accept (P, c): Gibt “wahr/true” zurück, wenn “c” eine Lösung von “P” ist, ansonsten “falsch/false”.
- first (P, c): Erzeugt die erste Erweiterung des Kandidaten “c”.
- next (P, s): Erzeugt die nächste alternative Erweiterung eines Kandidaten nach der Erweiterung “s”.
- output (P, c): Verwendet je nach Anwendung die Lösung “c” von “P”..
Auf der anderen Seite hängt die Effizienz des Backtracking Algorithmus von der Zurückweisung ab, die für Kandidaten, die der Wurzel so nahe wie möglich sind, auf “wahr/true” zurückgeht. Wenn reject immer “falsch/false” zurückgibt, findet der Algorithmus immer noch alle Lösungen, aber es entspricht einer sogenannten Brute-Force-Suche.
Die accept-Prozedur sollte “wahr/true” zurückgeben, wenn “c” eine vollständige und gültige Lösung für die Probleminstanz “P” ist, andernfalls “falsch/true”. Es kann angenommen werden, dass der Teilkandidat “c” und alle seine Vorfahren in dem Baum den Abweisungstest bestanden haben.
Der obige allgemeine Psuedocode geht nicht davon aus, dass die gültigen Lösungen immer Blätter des potenziellen Suchbaums sind. Mit anderen Worten: Es gibt die Möglichkeit, dass eine gültige Lösung für “P” weiter ausgedehnt werden kann, um andere gültige Lösungen zu erhalten.
Die ersten und nächsten (first und next) Prozeduren werden vom Backtracking Algorithmus verwendet, um die untergeordneten Elemente eines Knotens “c” des Baums, aufzulisten. Das heißt, es sind die Kandidaten, die sich von “c” durch einen einzelnen Erweiterungsschritt unterscheiden. Der Aufruf “first” (P, c) sollte das erste Kind von “c” in einer bestimmten Reihenfolge ergeben. Der Aufruf “next” (P, s) sollte das nächste Geschwisterteil von Knoten “s” in dieser Reihenfolge zurückgeben. Beide Funktionen sollten einen eindeutigen “Null” -Kandidaten zurückgeben, der mit “^” bezeichnet wird, wenn das angeforderte Kind nicht existiert.
Zusammen definieren die Funktionen root, first und next den Satz von Teilkandidaten und den potenziellen Suchbaum. Sie sollten so gewählt werden, dass jede Lösung von “P” irgendwo im Baum auftritt und kein Teilkandidat mehr als einmal vorkommt. Darüber hinaus sollten sie ein effizientes und effektives Abschlussprädikat zulassen.
Fazit
Das Backtracking stellt eine Problemlösungsmethode dar. Hierfür wird das Versuch-und-Irrtum-Prinzip verwendet. Es werden Möglichkeiten einer Lösung so lange versucht, bis die gesuchte Lösung erzielt wurde.
Sie haben noch Fragen?
