Algorytm śledzenia wstecznego

Czym jest algorytm Backtracking?

Backtracking to algorytm, który wyszukuje możliwe kombinacje w celu rozwiązania problemy obliczeniowe. Stopniowo buduje kandydatów i usuwa tych, którzy nie spełniają podanych ograniczeń. Ta technika jest bardzo przydatna w sytuacjach, gdy trzeba wybrać wykonalne rozwiązanie spośród wielu możliwych wyników.

Ten algorytm jest uważany za lepszy i bardziej wydajny niż podejście Brute Force. W przeciwieństwie do Bruteforce, które próbuje wszystkich możliwych rozwiązań, Backtracking koncentruje się na znalezieniu tylko jednego ostatecznego rozwiązania zgodnie z podanymi Ograniczenia. Oszczędza również czas i pamięć, cofając ostatni krok (backtrack) i próbując innej opcji po dotarciu do ślepego zaułka. Ponadto zatrzymuje się, gdy tylko zostanie znalezione prawidłowe rozwiązanie.

Backtracking jest szeroko stosowaną techniką, ponieważ może rozwiązywać złożone problemy bez wyczerpującego zużycia zasobów. Jest szczególnie użyteczny w przypadku problemów, w których należy spełnić liczne ograniczenia, takie jak Sudoku, problem królowej n i harmonogramowanie. Poprzez inteligentne nawigowanie przez potencjalne rozwiązania, backtracking może znaleźć odpowiedź, która spełnia wszystkie warunki. Dzięki temu jest nieoceniony w przypadku zadań wymagających zarówno precyzji, jak i wydajności.

Jak działa algorytm Backtrackingu?

Algorytmy backtrackingu to technika rozwiązywania problemów polegająca na znajdowaniu prawidłowych rozwiązań krok po kroku. Jeśli ograniczenia kroku nie spełniają pewnych warunków, algorytm wraca do poprzedniego kroku.

Następnie kontynuuje z innymi możliwymi kombinacjami, które spełniają podane ograniczenia. Ponieważ istnieje wiele możliwych kombinacji, wybiera jedną z najbardziej satysfakcjonujących opcji i rozwiązuje problem sekwencyjnie. Ta technika algorytmiczna jest przydatna, gdy trzeba rozwiązać jedną lub więcej możliwych opcji. Wycofanie oznacza anulowanie wyboru, gdy pojawi się sytuacja, która nie daje prawidłowego rozwiązania.

Algorytm cofania się w celu rozwiązania problemu składa się z następujących kroków:

Krok 1) Inicjalizacja: Zacznij od pustego/częściowego rozwiązania początkowego.

Krok 2) Wybór: Na podstawie określonych kryteriów i ograniczeń wybierz jedną opcję rozszerzenia bieżącego rozwiązania.

Krok 3) Eksploracja:Rozwiąż rekurencyjnie, biorąc pod uwagę wybranego kandydata i kontynuując proces rozwiązywania problemu.

Krok 4) Sprawdzenie ograniczeń: Sprawdź, czy obecne częściowe rozwiązanie narusza jakiekolwiek ograniczenia na każdym kroku. Jeśli tak, wróć do poprzedniego kroku i wypróbuj innego kandydata.

Krok 5) ZakończenieProces cofania się zatrzymuje się, gdy zostanie znalezione prawidłowe rozwiązanie lub gdy zostaną wyczerpane wszystkie kombinacje.

Krok 6) Cofanie się: Jeśli bieżąca opcja nie rozwiązuje danego problemu, wraca do poprzedniego stanu. Następnie rozważa nową opcję, aby rozwiązać dany problem.

Krok 7) Powtórz: Kontynuuj wykonywanie tych kroków, aż do rozwiązania problemu lub sprawdzenia wszystkich opcji.

Rekurencyjna natura algorytmu backtrackingu

Algorytmy backtrackingu są z natury rekurencyjne. Oznacza to, że algorytm wywołuje sam siebie z różnymi parametrami, dopóki nie znajdzie rozwiązania lub nie przetestuje wszystkich możliwości:

def find_solutions(n, other_params):
    if found_a_solution():
        increment_solutions_found()
        display_solution()
        if solutions_found >= solution_target:
            exit_program()
        return	

    for val in range(first, last+1):
        if is_valid(val, n):
            apply_value(val, n)
            find_solutions(n + 1, other_params)
            remove_value(val, n)

Powszechne terminy związane z problemami z cofaniem się

Oto kilka podstawowych pojęć związanych z techniką Backtrackingu:

• Wektor rozwiązania: Reprezentuje rozwiązania jako n-krotki, takie jak (X1, X2, …, Xn).
• ograniczenia:Zasady ograniczające wartości X, jawne i ukryte.
• Przestrzeń rozwiązań: Wszystkie prawidłowe wartości X spełniające jawne ograniczenia.
• Drzewo przestrzeni stanów:Przedstawia przestrzeń rozwiązań w postaci drzewa.
• Przestrzeń stanów:Opisuje ścieżki w drzewie przestrzeni stanów.
• Stan problemu:Węzły w drzewie poszukiwań reprezentujące rozwiązania cząstkowe.
• Stany rozwiązań:Stany tworzące poprawne krotki rozwiązań w S.
• Odpowiedź Stany:Spełnij ukryte ograniczenia i uzyskaj pożądane rozwiązania.
• Obiecujący węzeł:Prowadzi do pożądanych rozwiązań i pozostaje wykonalne.
• Węzeł nieobiecujący:Prowadzi do niemożliwych do osiągnięcia stanów, nie będących przedmiotem dalszych badań.
• Węzeł aktywny:Wygenerowano z udziałem nieodkrytych dzieci.
• Węzeł E:Żywy węzeł z trwającą generacją potomków.
• Martwy węzeł:Nie wygenerowano dalszego rozszerzenia liczby dzieci.
• Generowanie węzłów w trybie „głębokość-najpierw”:Używa najnowszego aktywnego węzła jako kolejnego węzła elektronicznego.
• Funkcja ograniczająca:Maksymalizuje lub minimalizuje B(x1, x2, …, Xa) w celu optymalizacji.
• Drzewa statyczne:Formuła drzewa niezależna od instancji problemu.
• Dynamiczne drzewa:Formuła drzewa zmienia się w zależności od przypadku problemu.

Kiedy stosować algorytm backtrackingu?

Możemy zastosować technikę Backtrackingu do rozwiązania złożonego problemu, gdy:

• Istnieje wiele możliwości wyboru: Backtracking jest odpowiedni, jeśli na każdym etapie procesu rozwiązywania problemu istnieje wiele opcji. Opcje te mogą dotyczyć wyboru elementów i ruchów.
• Brak wyraźnego najlepszego wyboru:Jeśli nie ma wystarczających informacji do dokonania najlepszego wyboru spośród dostępnych opcji, można wykorzystać algorytm Backtracking.
• Decyzja pociąga za sobą więcej wyborów: Możesz wybrać technika cofania się, pozwalająca na systematyczne przeglądanie wyborów.
• Trzeba zbadać wszystkie możliwe rozwiązania:Metoda backtrackingu polega na systematycznym badaniu wszystkich rozwiązań poprzez podejmowanie serii decyzji opartych na sobie nawzajem.

Rodzaje problemów z cofaniem się

Istnieją trzy rodzaje problemów w algorytmach backtrackingu: problemy decyzyjne, problemy optymalizacyjne i problemy enumeracyjne. Poznajmy je poniżej.

1. Problem decyzyjny: W tego typu problemie celem jest ustalenie, czy istnieje wykonalne rozwiązanie. Sprawdzamy odpowiedzi „tak” i „nie”. Na przykład problem n-heens. Jest to problem decyzyjny, który bada prawdopodobieństwo umieszczenia n hetmanów na szachownicy n × n bez atakowania się nawzajem.
2. Problem optymalizacji: W problemach optymalizacji celem jest znalezienie najlepszego możliwego rozwiązania spośród wielu opcji. Może to obejmować określenie maksymalnych i minimalnych wartości pewnej funkcji lub zmiennej. Na przykład rozważ problem plecaka, w którym celem jest maksymalizacja całkowitej wartości przedmiotów w torbie przy jednoczesnym przestrzeganiu limitu wagowego.
3. Problem z wyliczeniem: Jego celem jest znalezienie wszystkich możliwych rozwiązań danego problemu. Wypisujemy każdą prawidłową opcję bez żadnych pominięć. Przykładem może być wygenerowanie wszystkich możliwych kombinacji liter z danego zestawu znaków.

Zastosowania Backtrackingu i Przykłady

Istnieją różne zastosowania Backtrackingu. Niektóre z nich są wyjaśnione poniżej wraz z ich pseudokodem.

1. Sudoku Solver: Ten problem zawiera podsiatkę 3×3 z powtarzającymi się liczbami. Technika backtrackingu pokaże, że rozwiązanie zwraca false, wskazując na potrzebę innego umieszczenia liczby.

function solveSudoku(board):
    if no empty cells:
        return true  # Sudoku is solved
    for each empty cell (row, col):
        for num from 1 to 9:
            if num is valid in (row, col):
                place num in (row, col)
                if solveSudoku(board):
                    return true
                remove num from (row, col)
    return false  # No valid solution

2. Problem N-królowejMetoda backtrackingu określa sposób rozmieszczenia hetmanów na szachownicy N × N w taki sposób, aby żadna z nich nie zagrażała innej.

function solveNQueens(board, col):
    if col >= N:
        return true  # All queens are placed
    for each row in the column col:
        if isSafe(board, row, col):
            place queen at (row, col)
            if solveNQueens(board, col + 1):
                return true
            remove queen from (row, col)
    return false  # No valid solution in this branch

3. Problem z sumą podzbiorów:Służy do znalezienia podzbioru liczb z danego zestawu, które sumują się do określonej sumy docelowej.

function subsetSum(nums, target, index, currentSubset):
    if target == 0:
        print(currentSubset)  # Subset with the target sum found
        return
    if index >= len(nums) or target < 0:
        return
   currentSubset.add(nums[index])
   subsetSum(nums, target - nums[index], index + 1, currentSubset)
   currentSubset.remove(nums[index])
   subsetSum(nums, target, index + 1, currentSubset)

4. Problem cyklu Hamiltona:Można zastosować technikę cofania, aby znaleźć w grafie trasę zamkniętą, która przechodzi przez każdy wierzchołek dokładnie raz.
5. Problem szczura w labiryncie:Technika cofania się jest wykorzystywana w celu odnalezienia ścieżki szczura od punktu początkowego labiryntu do wyjścia.

Zalety i wady algorytmu Backtracking

Zalety algorytmu Backtracking

Techniki backtrackingu są używane do rozwiązywania złożonych problemów. Mają wiele zalet, takich jak:

• Technika cofania się jest efektywna w radzeniu sobie z ograniczeniami.
• Metoda ta jest dobra do rozwiązywania problemów optymalizacyjnych.
• Technika ta sprawdza się w przypadku wielu typów problemów.
• Procedura ta może pomóc w przeglądzie wszystkich możliwych rozwiązań.
• Ponieważ metoda ta umożliwia cofanie się, oszczędza ona więcej pamięci niż technika Bruteforce.

Wady algorytmu Backtracking

Techniki backtrackingu mają również pewne ograniczenia, takie jak złożoność czasowa. Ta technika ma następujące wady:

• Nie ma pewnego rozwiązania.
• Jest wolniejszy ze względu na wiele kombinacji.
• Ma dużą złożoność czasową ze względu na wiele możliwości.
• Nie nadaje się do stosowania w przypadku ograniczeń czasu rzeczywistego, gdyż znalezienie najlepszego rozwiązania może zająć dużo czasu.
• Efektywność zależy od stopnia złożoności problemu.

Różnica między backtrackingiem a rekurencją

Podsumowanie

Backtracking to użyteczna strategia algorytmiczna służąca do rozwiązywania złożonych problemów poprzez systematyczne badanie wykonalnych rozwiązań i cofanie się, gdy jest to konieczne. Możemy oczekiwać, że techniki backtrackingu ulepszą się wraz z ulepszeniami mocy obliczeniowej i wydajności algorytmicznej. Te postępy pozwolą im skutecznie rozwiązywać większe i bardziej złożone problemy.

Ponadto modele uczenia maszynowego mogą wspomagać podejmowanie decyzji o cofaniu się w oparciu o wcześniej poznane wzorce.

Wszystkie te innowacje technologiczne zrewolucjonizują algorytmy backtrackingu, czyniąc z nich potężne i wszechstronne narzędzie do rozwiązywania skomplikowanych problemów w różnych dziedzinach.