Der Backtracking -Algorithmus untersucht effizient einen Suchraum, indem Sie systematisch verschiedene Kombinationen ausprobieren und Pfade aufgeben, die garantiert nicht zu einer Lösung führen. Es funktioniert nach dem Prinzip der * Tiefen-First-Suche * mit einer entscheidenden Ergänzung:
Beschneidung .
Hier ist eine Aufschlüsselung darüber, wie es funktioniert:
1. Zustandsraumdarstellung: Das Problem wird als Baum oder Grafik dargestellt, bei dem jeder Knoten eine partielle Lösung darstellt. Der Stammknoten repräsentiert den Ausgangszustand, und Zweige stellen Entscheidungen oder Entscheidungen dar, die in jedem Schritt getroffen wurden. Die Blätter repräsentieren entweder vollständige Lösungen oder Sackgassen.
2. Rekursive Exploration (Tiefen-First-Suche): Der Algorithmus beginnt am Wurzelknoten und erforscht jeweils einen Zweig, so tief wie möglich (Tiefe-First). Dies bedeutet, dass es eine Reihe von Auswahlmöglichkeiten entspricht, bis es entweder eine Lösung findet oder eine Sackgasse trifft.
3. Einschränkungsprüfung/-versprechend: Bei jedem Knoten wird eine Überprüfung durchgeführt, um festzustellen, ob die aktuelle Teillösung noch "vielversprechend" ist - dh es ist möglich, sie in eine vollständige Lösung auszudehnen. Hier kommt die Effizienz ins Spiel. Wenn die aktuelle teilweise Lösung gegen die Einschränkungen des Problems verstößt (z. B. in einem Sudoku -Puzzle und eine Zahl, die bereits in der Zeile, in der Spalte oder in 3x3 Block befindet), weiß der Algorithmus, dass er diesen Zweig nicht weiter untersuchen muss. Dies ist das Beschneidung Schritt.
4. Backtracking: Wenn ein Knoten als nicht vielversprechend eingestuft wird oder wenn ein Blattknoten einen fehlgeschlagenen Versuch darstellt, eine Lösung zu finden, ist der Algorithmus "Backtracks" an den vorherigen Knoten (seinen Elternteil) und versucht einen anderen Zweig (eine andere Wahl). Dies beinhaltet die Rückgängigmachung der Entscheidungen, die in diesem Zweig getroffen wurden, und die Erforschung alternativer Möglichkeiten.
5. Lösung gefunden: Wenn ein Blattknoten eine vollständige und gültige Lösung darstellt, hat der Algorithmus eine Lösung gefunden und kann entweder anhalten (wenn das Finden einer Lösung ausreicht) oder weiter nach anderen Lösungen zu suchen, indem Sie andere Zweige zurückverfolgen und erforschen.
Beispiel:N-Queens Problem
Überlegen wir, ob wir N -Schachköniginnen auf ein N × N -Schachbrett so platzieren, dass sich keine zwei Queens gegenseitig bedrohen.
* Zustandsraum: Jeder Knoten im Baum stellt eine teilweise Platzierung von Königinnen auf der Tafel dar.
* Auswahl: Auf jeder Ebene des Baumes wird eine Auswahl getroffen, wo die nächste Königin in die Kolumne platziert werden soll.
* Einschränkung: Die Einschränkung ist, dass sich keine zwei Queens in derselben Zeile, derselben Spalte oder in derselben Diagonale befinden können.
* Beschneidung: Wenn die Platzierung einer Königin gegen die Einschränkung verstößt, wird dieser Zweig beschnitten. Der Algorithmus untersucht diesen Zweig nicht weiter unten.
* Backtracking: Wenn eine Platzierung zu einem Verstoß führt, fährt der Algorithmus in die vorherige Spalte zurück, entfernt die Königin und versucht eine andere Position in dieser Spalte.
Zusammenfassend: Die Effizienz von Backtracking ergibt sich aus der Fähigkeit, unnötige Teile des Suchraums zu untersuchen, indem intelligent Beschneidung von Zweigen beschnitten wird, die garantiert nicht zu einer Lösung führen. Dies reduziert die Berechnungszeit im Vergleich zu erschöpfenden Suchmethoden erheblich, die jede einzelne Kombination versuchen würden. Die Effektivität hängt davon ab, wie gut die "vielversprechende" Überprüfung ausgelegt ist, um nicht lebensfähige Pfade zu Beginn der Suche zu identifizieren und zu beseitigen.
