Der Backtracking-Algorithmus zählt eine Reihe von Teilkandidaten auf, die im Prinzip auf verschiedene Arten vervollständigt werden könnten, um alle möglichen Lösungen für das gegebene Problem zu erhalten. Die Vervollständigung erfolgt inkrementell durch eine Folge von Kandidatenerweiterungsschritten.
Konzeptionell werden die Teilkandidaten als Knoten einer Baumstruktur, dem Potentialsuchbaum, dargestellt. Jeder Teilkandidat ist der übergeordnete Kandidat der Kandidaten, die sich durch einen einzelnen Erweiterungsschritt davon unterscheiden; die Blätter des Baumes sind die Teilkandidaten, die nicht weiter verlängert werden können.
Der Backtracking-Algorithmus durchläuft diesen Suchbaum rekursiv von der Wurzel abwärts in der Tiefe 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 in c verwurzelte Unterbaum übersprungen (beschnitten). Andernfalls prüft der Algorithmus (1), ob c selbst eine gültige Lösung ist, und meldet sie gegebenenfalls dem Benutzer. und (2) listet rekursiv alle Teilbäume von c auf.
Daher ist der eigentliche Suchbaum, den der Algorithmus durchläuft, nur ein Teil des Potentialbaums. Die Gesamtkosten des Algorithmus sind die Anzahl der Knoten des tatsächlichen Baums mal die Kosten für das Erhalten und Verarbeiten jedes Knotens. Diese Tatsache sollte bei der Auswahl des potenziellen Suchbaums und der Implementierung des Beschneidungstests berücksichtigt werden.
PseudocodeEdit
Um Backtracking auf eine bestimmte Klasse von Problemen anzuwenden, muss man die Daten P für die bestimmte Instanz des Problems, das gelöst werden soll, und sechs prozedurale Parameter, root, reject, accept, first, next und output . Diese Prozeduren sollten die Instanzdaten P als Parameter verwenden und Folgendes tun:
- root(P): Gibt den Teilkandidaten an der Wurzel des Suchbaums zurück.
- reject(P, c): gibt true nur zurück, wenn der Teilkandidat c es nicht wert ist, abgeschlossen zu werden.
- akzeptieren (P, c): gibt true zurück, wenn c eine Lösung von P ist, andernfalls false.
- first(P,c): Generiert die erste Erweiterung des Kandidaten c.
- next(P,s): Generiert die nächste alternative Erweiterung eines Kandidaten nach der Erweiterung s.
- output(P,c): Verwenden Sie die Lösung c von P entsprechend der Anwendung.
Der Backtracking-Algorithmus reduziert das Problem auf den Aufruf backtrack(root(P)) , wobei backtrack die folgende rekursive Prozedur ist:
procedure backtrack(c) is if reject(P, c) then return if accept(P, c) then output(P, c) s ← first(P, c) while s ≠ NULL do backtrack(s) s ← next(P, s)
Überlegungen zur VerwendungBearbeiten
Die Zurückweisungsprozedur sollte eine boolesch bewertete Funktion sein, die nur dann true zurückgibt, wenn sicher ist, dass keine mögliche Erweiterung von c eine gültige Lösung für P ist. Ein falsches True-Ergebnis kann dazu führen, dass der bt-Prozedur einige gültige Lösungen fehlen. Die Prozedur kann davon ausgehen, dass reject(P,t) für jeden Vorfahren t von c im Suchbaum false zurückgibt.
Andererseits hängt die Effizienz des Backtracking-Algorithmus davon ab, dass reject true für Kandidaten zurückgibt, die so nah wie möglich an der Wurzel liegen. Wenn reject immer false zurückgibt, findet der Algorithmus weiterhin alle Lösungen, entspricht jedoch einer Brute-Force-Suche.
Die accept-Prozedur sollte true zurückgeben, wenn c eine vollständige und gültige Lösung für die Probleminstanz P ist, andernfalls false. Es kann davon ausgegangen werden, dass der Teilkandidat c und alle seine Vorfahren im Baum den Ablehnungstest bestanden haben.
Der obige allgemeine Pseudocode 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 zu, dass eine gültige Lösung für P weiter erweitert werden kann, um andere gültige Lösungen zu ergeben.
Die erste und die nächste Prozedur werden vom Backtracking-Algorithmus verwendet, um die Kinder eines Knotens c des Baums aufzuzählen, dh die Kandidaten, die sich von c um einen einzigen Erweiterungsschritt unterscheiden. Der Aufruf first(P,c) sollte das erste Kind von c in einer bestimmten Reihenfolge ergeben; und der Aufruf next(P,s) sollte das nächste Geschwister von Knoten s in dieser Reihenfolge zurückgeben. Beide Funktionen sollten einen eindeutigen „NULL“ -Kandidaten zurückgeben, wenn das angeforderte Kind nicht existiert.
Zusammen definieren die Funktionen root, first und next die Menge der Teilkandidaten und den potenziellen Suchbaum. Sie sollten so gewählt werden, dass jede Lösung von P irgendwo im Baum vorkommt und kein partieller Kandidat mehr als einmal vorkommt. Darüber hinaus sollten sie ein effizientes und effektives Ablehnungsprädikat zulassen.
Early stopping variantsEdit
Der obige Pseudocode ruft die Ausgabe für alle Kandidaten auf, die eine Lösung für die angegebene Instanz P . Der Algorithmus kann so geändert werden, dass er nach dem Finden der ersten Lösung oder einer bestimmten Anzahl von Lösungen angehalten wird. oder nach dem Testen einer bestimmten Anzahl von Teilkandidaten oder nach einer bestimmten CPU-Zeit.