Z tego samouczka dowiesz się, czym jest algorytm śledzenia wstecznego. Znajdziesz tu również przykład podejścia z wycofywaniem się.
Algorytm cofania to algorytm rozwiązywania problemów, który wykorzystuje podejście brutalnej siły w celu znalezienia pożądanego wyniku.
Podejście Brute force próbuje wszystkich możliwych rozwiązań i wybiera pożądane / najlepsze rozwiązania.
Termin cofanie sugeruje, że jeśli bieżące rozwiązanie nie jest odpowiednie, należy wycofać się i wypróbować inne rozwiązania. Dlatego w tym podejściu używana jest rekurencja.
To podejście służy do rozwiązywania problemów, które mają wiele rozwiązań. Jeśli chcesz optymalnego rozwiązania, musisz przejść do programowania dynamicznego.
Drzewo przestrzeni stanów
Drzewo stanu przestrzeni to drzewo przedstawiające wszystkie możliwe stany (rozwiązanie lub nierozwiązanie) problemu od korzenia jako stanu początkowego do liścia jako stanu końcowego.
Drzewo przestrzeni stanów
Algorytm cofania
Backtrack (x) jeśli x nie jest rozwiązaniem zwróć false jeśli x jest nowym rozwiązaniem dodaj do listy rozwiązań backtrack (rozwiń x)
Przykładowe podejście z nawrotem
Problem: Chcesz znaleźć wszystkie możliwe sposoby ustawienia 2 chłopców i 1 dziewczynki na 3 ławkach. Ograniczenie: dziewczyna nie powinna leżeć na środkowej ławce.
Rozwiązanie: w sumie jest ich 3! = 6 możliwości. Spróbujemy wszystkich możliwości i uzyskamy możliwe rozwiązania. Rekurencyjnie wypróbowujemy wszystkie możliwości.
Wszystkie możliwości to:
Wszystkie możliwości
Poniższe drzewo przestrzeni stanów pokazuje możliwe rozwiązania.
Drzewo stanów ze wszystkimi rozwiązaniami
Aplikacje algorytmów wycofywania
- Aby znaleźć wszystkie ścieżki Hamiltona obecne na wykresie.
- Aby rozwiązać problem królowej N.
- Labirynt rozwiązywania problemu.
- Problem z trasą Knighta.
