Algorytmy cofania są jak strategie rozwiązywania problemów, które pomagają zbadać różne opcje w celu znalezienia najlepszego rozwiązania. Pracują, wypróbowując różne ścieżki, a jeśli jedna nie działa, wycofują się i wypróbowują inną, dopóki nie znajdą tej właściwej. To jak układanie puzzli poprzez testowanie różnych elementów, aż będą idealnie do siebie pasować.
Cofanie się
Spis treści
- Co to jest algorytm śledzenia wstecznego?
- Jak działa algorytm cofania się?
- Przykład algorytmu cofania
- Kiedy stosować algorytm cofania?
- Zastosowania algorytmu cofania
- Podstawy algorytmu cofania
- Standardowe problemy dotyczące algorytmu wycofywania się
- Łatwe problemy w algorytmie cofania
- Średnie problemy z algorytmem cofania
- Trudne problemy z algorytmem cofania
Co to jest algorytm śledzenia wstecznego?
Cofanie się to algorytmiczna technika rozwiązywania problemów, która polega na stopniowym znajdowaniu rozwiązania poprzez próbę różne opcje I zguba jeśli prowadzą do a ślepy zaułek .
Jest powszechnie stosowany w sytuacjach, w których trzeba zbadać wiele możliwości rozwiązania problemu, na przykład szukając ścieżki w labiryncie lub rozwiązując zagadki, takie jak Sudoku . Po dotarciu do ślepego zaułka algorytm cofa się do poprzedniego punktu decyzji i bada inną ścieżkę, aż do znalezienia rozwiązania lub wyczerpania wszystkich możliwości.
Jak działa algorytm cofania się?
A algorytm cofania się działa poprzez rekurencyjne badanie wszystkich możliwych rozwiązań problemu. Rozpoczyna się od wyboru rozwiązania początkowego, a następnie bada wszystkie możliwe rozszerzenia tego rozwiązania. Jeśli rozszerzenie prowadzi do rozwiązania, algorytm zwraca to rozwiązanie. Jeśli rozszerzenie nie prowadzi do rozwiązania, algorytm powraca do poprzedniego rozwiązania i próbuje innego rozszerzenia.
Poniżej znajduje się ogólny zarys działania algorytmu cofania:
- Wybierz rozwiązanie początkowe.
- Poznaj wszystkie możliwe rozszerzenia obecnego rozwiązania.
- Jeśli rozszerzenie prowadzi do rozwiązania, zwróć to rozwiązanie.
- Jeśli rozszerzenie nie doprowadzi do rozwiązania, wróć do poprzedniego rozwiązania i wypróbuj inne rozszerzenie.
- Powtarzaj kroki 2–4, aż zostaną sprawdzone wszystkie możliwe rozwiązania.
Przykład algorytmu cofania
Przykład: Znalezienie najkrótszej ścieżki w labiryncie
Wejście: Labirynt reprezentowany jako tablica 2D, gdzie 0 reprezentuje otwartą przestrzeń i 1 reprezentuje ścianę.
Algorytm:
- Zacznij od punktu początkowego.
- Dla każdego z czterech możliwych kierunków (w górę, w dół, w lewo, w prawo) spróbuj poruszać się w tym kierunku.
- Jeśli poruszanie się w tym kierunku prowadzi do punktu końcowego, wróć obraną ścieżką.
- Jeśli ruch w tym kierunku nie prowadzi do punktu końcowego, wróć do poprzedniej pozycji i spróbuj w innym kierunku.
- Powtarzaj kroki 2-4, aż dojdziesz do punktu końcowego lub zbadasz wszystkie możliwe ścieżki.
Kiedy stosować algorytm cofania?
Algorytmy wycofywania najlepiej nadają się do rozwiązywania problemów, które mają następujące cechy:
- Istnieje wiele możliwych rozwiązań problemu.
- Problem można podzielić na mniejsze podproblemy.
- Podproblemy można rozwiązać niezależnie.
Zastosowania algorytmu cofania
Algorytmy wycofywania są wykorzystywane w wielu różnych zastosowaniach, w tym:
- Rozwiązywanie łamigłówek (np. Sudoku, krzyżówek)
- Znalezienie najkrótszej ścieżki w labiryncie
- Problemy z planowaniem
- Problemy z alokacją zasobów
- Problemy z optymalizacją sieci
Podstawy algorytmu cofania:
- Różnica między techniką Backtracking a techniką Branch-N-Bound
- Jaka jest różnica między cofaniem a rekurencją?
Standardowe problemy dotyczące algorytmu cofania:
- Problem z trasą Rycerza
- Szczur w labiryncie
- Problem z królową N | Cofanie się-3
- Problem z sumą podzbiorów
- m Problem z kolorowaniem
- Cykl Hamiltona
- Sudoku | Cofanie się-7
- Puzzle magnetyczne
- Usuń nieprawidłowe nawiasy
- Podejście polegające na wycofywaniu się w celu wygenerowania n-bitowych kodów Graya
- Napisz program, który wyświetli wszystkie permutacje danego ciągu znaków
Łatwe problemy z algorytmem cofania:
- Cofanie się w celu znalezienia wszystkich podzbiorów
- Sprawdź, czy dany ciąg jest ciągiem sumy
- Policz wszystkie możliwe ścieżki między dwoma wierzchołkami
- Znajdź wszystkie odrębne podzbiory danego zbioru
- Znajdź, czy istnieje ścieżka od źródła o długości większej niż k
- Wydrukuj wszystkie ścieżki z danego źródła do miejsca docelowego
- Wydrukuj wszystkie możliwe ciągi znaków, które można utworzyć, umieszczając spacje
Średnie problemy z algorytmem cofania:
- Przeciąganie liny
- Problem z 8 królową
- Suma kombinowana
- Algorytm Warnsdorffa dla problemu trasy Knighta
- Znajdź ścieżki od komórki narożnej do środkowej komórki w labiryncie
- Znajdź maksymalną możliwą liczbę, wykonując co najwyżej K zamian
- Szczur w labiryncie z dozwolonymi wieloma krokami lub skokami
- N Królowa w przestrzeni O(n).
Trudne problemy z algorytmem cofania:
- Zestaw mocy w porządku leksykograficznym
- Problem z dzieleniem wyrazów przy użyciu cofania
- Podział zbioru na K podzbiorów o jednakowej sumie
- Najdłuższa możliwa trasa w matrixie z przeszkodami
- Znajdź najkrótszą bezpieczną trasę na ścieżce z minami
- Wydrukuj wszystkie palindromiczne partycje ciągu
- Drukowanie wszystkich rozwiązań problemu N-Queen
- Wydrukuj wszystkie najdłuższe wspólne podsekwencje w porządku leksykograficznym
Szybkie linki :
- Naucz się struktury danych i algorytmów | Poradnik DSA
- 20 najpopularniejszych pytań do wywiadu na temat algorytmu śledzenia wstecznego
- „Filmy” na temat cofania się