algorytm backtracking wylicza zbiór częściowych kandydatów, które w zasadzie można uzupełnić na różne sposoby, aby dać wszystkie możliwe rozwiązania danego problemu. Zakończenie odbywa się stopniowo, przez sekwencję etapów rozszerzenia kandydata.
koncepcyjnie, częściowe kandydatury są reprezentowane jako węzły struktury drzewa, potencjalnego drzewa wyszukiwania. Każdy kandydat częściowy jest rodzicem kandydatów, którzy różnią się od niego pojedynczym krokiem rozszerzenia; liście drzewa są częściowymi kandydatami, których nie można dalej przedłużać.
algorytm śledzenia wstecznego przemierza to drzewo wyszukiwania rekurencyjnie, od korzenia w dół, w głębi-pierwszego rzędu. Na każdym węźle c algorytm sprawdza, czy c można uzupełnić do poprawnego rozwiązania. Jeśli nie, to całe sub-drzewo zakorzenione w c jest pomijane (przycinane). W przeciwnym razie algorytm (1) sprawdza, czy c samo w sobie jest poprawnym rozwiązaniem, a jeśli tak, zgłasza je użytkownikowi; oraz (2) rekurencyjnie wylicza wszystkie sub-drzewa c. dwa testy i dzieci każdego węzła są zdefiniowane przez procedury podane przez użytkownika.
zatem rzeczywiste drzewo wyszukiwania, które jest przemierzane przez algorytm, jest tylko częścią drzewa potencjału. Całkowity koszt algorytmu to liczba węzłów rzeczywistego drzewa razy koszt uzyskania i przetworzenia każdego węzła. Fakt ten należy wziąć pod uwagę przy wyborze potencjalnego drzewa wyszukiwania i wdrażaniu testu przycinania.
PseudocodeEdit
aby zastosować backtracking do określonej klasy problemów, należy podać dane P dla konkretnego wystąpienia problemu, który ma zostać rozwiązany, oraz sześć parametrów proceduralnych: root, reject, accept, first, next i output. Procedury te powinny przyjmować jako parametr instance data P i powinny wykonać następujące czynności:
- root (P): zwraca częściowego kandydata w korzeniu drzewa wyszukiwania.
- Odrzuć (P, c): zwraca true tylko wtedy, gdy częściowy kandydat c nie jest wart uzupełnienia.
- Akceptuj (P, c): zwraca true, Jeśli C jest rozwiązaniem P, A false w przeciwnym razie.
- first(P,c): Wygeneruj pierwsze rozszerzenie kandydata c.
- next(P,s): Wygeneruj kolejne alternatywne rozszerzenie kandydata, PO rozszerzeniu s.
- output (P,c): użyj rozwiązania C Z P, odpowiednio do aplikacji.
algorytm BackTrack redukuje problem do wywołania backtrack (root (P)), gdzie backtrack jest następującą procedurą rekurencyjną:
procedure backtrack(c) is if reject(P, c) then return if accept(P, c) then output(P, c) s ← first(P, c) while s ≠ NULL do backtrack(s) s ← next(P, s)
rozważania Zastosowaniaedit
procedura odrzucenia powinna być funkcją o wartości logicznej, która zwraca true tylko wtedy, gdy jest pewne, że żadne możliwe rozszerzenie c nie jest poprawnym rozwiązaniem dla P. jeśli procedura nie może dojść do pewnego wniosku, powinna zwrócić false. Nieprawidłowy wynik może spowodować, że procedura bt pominie pewne poprawne rozwiązania. Procedura może zakładać,że reject(P, t) zwracało false dla każdego przodka T z C w drzewie wyszukiwania.
z drugiej strony, skuteczność algorytmu backtracking zależy od odrzucenia zwracającego true dla kandydatów, które są jak najbliżej korzenia. Jeśli odrzucenie zawsze zwróci false, algorytm nadal znajdzie wszystkie rozwiązania, ale będzie to równoważne wyszukiwaniu brute-force.
procedura accept powinna zwracać true, Jeśli C jest kompletnym i poprawnym rozwiązaniem dla wystąpienia problemu P, A false w przeciwnym razie. Może zakładać, że częściowy kandydat c i wszyscy jego przodkowie w drzewie przeszli test odrzucenia.
powyższy ogólny pseudo-kod nie zakłada, że poprawnymi rozwiązaniami są zawsze liście potencjalnego drzewa wyszukiwania. Innymi słowy, przyznaje możliwość, że poprawne rozwiązanie dla P może być dalej rozszerzone, aby uzyskać inne poprawne rozwiązania.
pierwsze i następne procedury są używane przez algorytm backtrackingu do wyliczania Potomków węzła C drzewa, czyli kandydatów, które różnią się od c jednym krokiem rozszerzenia. Wywołanie first (P, c)powinno dać pierwsze potomstwo c, w pewnej kolejności; a wywołanie next (P, s) powinno zwrócić następne rodzeństwo węzła s, w tej kolejności. Obie funkcje powinny zwracać charakterystyczny” NULL ” kandydata, jeśli żądane dziecko nie istnieje.
razem funkcje root, first I next definiują zbiór częściowych kandydatów i potencjalne drzewo wyszukiwania. Należy je tak dobrać, aby każde rozwiązanie P występowało gdzieś w drzewie, a żaden częściowy kandydat nie wystąpił więcej niż raz. Co więcej, powinni przyznać skuteczny i skuteczny predykat odrzucenia.
wczesne zatrzymywanie wariantówedit
powyższy pseudo-kod wywoła wyjście dla wszystkich kandydatów, które są rozwiązaniem danej instancji P. algorytm może zostać zmodyfikowany tak, aby zatrzymać się po znalezieniu pierwszego rozwiązania lub określonej liczby rozwiązań; lub po przetestowaniu określonej liczby częściowych kandydatów lub po spędzeniu określonej ilości czasu procesora.