In diesem Tutorial erfahren Sie, was ein Backtracking-Algorithmus ist. Außerdem finden Sie ein Beispiel für einen Backtracking-Ansatz.
Ein Backtracking-Algorithmus ist ein Problemlösungsalgorithmus, der einen Brute-Force-Ansatz verwendet, um die gewünschte Ausgabe zu finden.
Der Brute-Force-Ansatz probiert alle möglichen Lösungen aus und wählt die gewünschten / besten Lösungen aus.
Der Begriff Backtracking legt nahe, dass Sie, wenn die aktuelle Lösung nicht geeignet ist, andere Lösungen zurückverfolgen und ausprobieren. Daher wird bei diesem Ansatz eine Rekursion verwendet.
Dieser Ansatz wird verwendet, um Probleme mit mehreren Lösungen zu lösen. Wenn Sie eine optimale Lösung wünschen, müssen Sie sich für eine dynamische Programmierung entscheiden.
Zustandsraumbaum
Ein Raumzustandsbaum ist ein Baum, der alle möglichen Zustände (Lösung oder Nichtlösung) des Problems von der Wurzel als Anfangszustand bis zum Blatt als Endzustand darstellt.
Zustandsraumbaum
Backtracking-Algorithmus
Backtrack (x) wenn x keine Lösung ist return false wenn x eine neue Lösung ist, zur Liste der Lösungen hinzufügen backtrack (x erweitern)
Beispiel für einen Backtracking-Ansatz
Problem: Sie möchten alle Möglichkeiten finden, 2 Jungen und 1 Mädchen auf 3 Bänken anzuordnen. Einschränkung: Mädchen sollte nicht auf der mittleren Bank sein.
Lösung: Es gibt insgesamt 3! = 6 Möglichkeiten. Wir werden alle Möglichkeiten ausprobieren und die möglichen Lösungen finden. Wir versuchen rekursiv alle Möglichkeiten.
Alle Möglichkeiten sind:
Alle Möglichkeiten
Der folgende Zustandsraumbaum zeigt die möglichen Lösungen.
Zustandsbaum mit allen Lösungen
Backtracking-Algorithmus-Anwendungen
- So finden Sie alle in einem Diagramm vorhandenen Hamilton-Pfade.
- Um das N Queen Problem zu lösen.
- Labyrinth Problem lösen.
- Das Tourproblem des Ritters.
