Backtracking ist eine allgemeine algorithmische Technik, mit der Probleme rekursiv gelöst werden, indem versucht wird, eine Lösung in schrittweisen Störungen zu erstellen. Wenn der Algorithmus zu einem bestimmten Zeitpunkt feststellt, dass der aktuelle Ansatz nicht zu einer gültigen Lösung führen kann (er trifft eine "Sackgasse"), "Backtracks" - er entblößt den letzten Schritt oder mehrere Schritte und versucht einen anderen Ansatz. Dieser Prozess wird fortgesetzt, bis eine Lösung gefunden wurde oder alle Möglichkeiten untersucht wurden.
Denken Sie daran, wie ein Labyrinth zu erkunden:
* Sie beginnen am Eingang und versuchen einen Weg.
* Wenn Sie eine Sackgasse erreichen, kehren Sie zur letzten Kreuzung zurück und versuchen einen anderen Weg.
* Sie tun dies weiter, bis Sie den Ausgang (Lösung) finden oder alle Pfade untersucht haben.
Schlüsselmerkmale des Backtracking:
* rekursiv: Backtracking -Algorithmen sind von Natur aus rekursiv. Jeder rekursive Anruf untersucht einen anderen Zweig des Lösungsraums.
* Versuch und Fehler: Es ist ein Versuchs- und Erroransatz. Es probiert verschiedene Optionen aus und verworfen diejenigen, die nicht zu einer Lösung führen.
* Zustandsraum Erkundung: Der Algorithmus untersucht systematisch den gesamten Zustandsraum (alle möglichen Lösungen) und verwendet häufig eine Baumstruktur, um die Suche darzustellen.
* Beschneidung: Ein entscheidender Aspekt ist die Fähigkeit, die Zweige des Suchbaums frühzeitig zu beschneiden, wenn festgestellt wird, dass sie nicht zu einer gültigen Lösung führen können. Dies verbessert die Effizienz erheblich.
Gemeinsame Anwendungen von Backtracking:
* Finden Sie alle möglichen Permutationen eines Satzes: Erzeugen Sie alle möglichen Elementanordnungen.
* Lösen des N-Queens-Problems: Nehmen Sie N -Schachköniginnen auf ein N × N -Schachbrett, damit sich keine zwei Königinnen drohen.
* Sudoku -Rätsel lösen: Ausfüllen der leeren Zellen eines Sudoku -Netzes gemäß den Spielregeln.
* alle Teilmengen eines Satzes generieren: Finden Sie alle möglichen Kombinationen von Elementen aus einem Satz.
* Graph-Traversalalgorithmen (z. B. Tiefensuche): Erforschen Sie alle Wege in einer Grafik.
* Begrenzungszufriedenheitsprobleme: Probleme, bei denen Lösungen eine Reihe von Einschränkungen erfüllen müssen.
Beispiel (vereinfachtes N-Queens):
Stellen Sie sich vor, Sie legen zwei Queens auf ein 2x2 -Schachbrett. Ein Backtracking -Algorithmus würde:
1. Versuchen Sie, die erste Königin in die obere linke Ecke zu platzieren.
2. Versuchen Sie, die zweite Königin in die obere rechte Ecke zu platzieren. Dies ist ungültig (Queens greifen sich gegenseitig an).
3. Backtrack:Entfernen Sie die zweite Königin.
4. Versuchen Sie, die zweite Königin in die untere linke Ecke zu legen. Dies ist ungültig.
5. Backtrack:Entfernen Sie die zweite Königin.
6. Backtrack:Entfernen Sie die erste Königin.
7. Versuchen Sie, die erste Königin in die obere rechte Ecke zu platzieren ... und so weiter, bis eine Lösung (oder das Fehlen davon) gefunden wurde.
Im Wesentlichen ist Backtracking eine leistungsstarke, aber potenziell rechenintensive Technik zur Lösung von Problemen, bei denen der Lösungsraum groß ist und systematisch untersucht werden muss. Die Effektivität hängt davon ab, wie effizient der Algorithmus den Suchraum beschneiden kann.
