Cofanie się - Backtracking

Cofanie się to ogólny algorytm służący do znajdowania rozwiązań niektórych problemów obliczeniowych , w szczególności problemów ze spełnieniem ograniczeń , który stopniowo buduje kandydatów do rozwiązań i porzuca kandydata („cofanie się”), gdy tylko ustali, że kandydata nie można ukończyć do prawidłowego rozwiązanie.

Klasycznym przykładem podręcznikowym przykładem wykorzystania backtracking jest logiczna osiem królowych , że prosi o wszystkich ustaleniach ośmiu szachista królowych na standardowej szachownicy tak, że nie ataki typu queen każdy inny. W powszechnym podejściu z nawracaniem, kandydatami częściowymi są układy k hetmanów w pierwszych k rzędach szachownicy, wszystkie w różnych rzędach i kolumnach. Każde częściowe rozwiązanie, które zawiera dwie wzajemnie atakujące matki, można porzucić.

Cofanie się może być stosowane tylko w przypadku problemów, które dopuszczają koncepcję „częściowego rozwiązania kandydującego” i stosunkowo szybkiego testu, czy można je ewentualnie przeprowadzić do ważnego rozwiązania. Jest bezużyteczny np. do lokalizowania danej wartości w nieuporządkowanej tabeli. Jednak gdy ma to zastosowanie, wycofywanie jest często znacznie szybsze niż wyliczenie metodą brute-force wszystkich kompletnych kandydatów, ponieważ może wyeliminować wielu kandydatów za pomocą jednego testu.

Cofanie się jest ważnym narzędziem do rozwiązywania problemów spełniania ograniczeń , takich jak krzyżówki , arytmetyka werbalna , Sudoku i wiele innych łamigłówek. Często jest to najwygodniejsza technika parsowania , dla problemu plecakowego i innych problemów optymalizacji kombinatorycznej . Jest również podstawą tzw. logicznych języków programowania takich jak Icon , Planner czy Prolog .

Cofanie się zależy od podanych przez użytkownika „ procedur czarnej skrzynki ”, które definiują problem do rozwiązania, charakter kandydatów częściowych oraz sposób ich rozszerzania na kandydatów kompletnych. Jest to zatem raczej metaheurystyka niż konkretny algorytm – chociaż, w przeciwieństwie do wielu innych metaheurystyk , gwarantuje znalezienie wszystkich rozwiązań skończonego problemu w ograniczonym czasie.

Termin „wstecz” został ukuty przez amerykańskiego matematyka DH Lehmera w latach 50. XX wieku. Pionierski język przetwarzania ciągów znaków SNOBOL (1962) mógł być pierwszym, który zapewnił wbudowaną funkcję ogólnego śledzenia wstecznego.

Opis metody

Algorytm wycofywania wylicza zbiór kandydatów cząstkowych, które w zasadzie można uzupełnić na różne sposoby, aby dać wszystkie możliwe rozwiązania danego problemu. Ukończenie odbywa się przyrostowo, przez sekwencję kroków rozszerzenia kandydującego.

Koncepcyjnie kandydaci częściowi są reprezentowani 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 jednym krokiem rozszerzenia; liście drzewa są kandydatami częściowymi, których nie można dalej rozszerzać.

Algorytm wycofywania przeszukuje to drzewo wyszukiwania rekursywnie , od korzenia w dół, w kolejności w głąb . W każdym węźle c algorytm sprawdza, czy c można uzupełnić do prawidłowego rozwiązania. Jeśli nie, całe poddrzewo zakorzenione w c jest pomijane ( przycinane ). W przeciwnym razie algorytm (1) sprawdza, czy samo c jest prawidłowym rozwiązaniem, a jeśli tak, zgłasza to użytkownikowi; i (2) rekurencyjnie wylicza wszystkie poddrzewa c . Dwa testy i dzieci każdego węzła są definiowane przez procedury podane przez użytkownika.

Dlatego rzeczywiste drzewo poszukiwań, które przemierza algorytm, jest tylko częścią drzewa potencjalnego. 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.

Pseudo kod

Aby zastosować śledzenie wsteczne 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 , remove , accept , first , next , i output . Procedury te powinny przyjmować dane instancji P jako parametr i wykonywać następujące czynności:

  1. root ( P ): zwróć częściowego kandydata w katalogu głównym drzewa wyszukiwania.
  2. odrzuć ( P , c ): zwróć true tylko wtedy, gdy częściowy kandydat c nie jest wart uzupełnienia.
  3. zaakceptuj ( P , c ): zwróć prawdę, jeśli c jest rozwiązaniem P , a fałsz w przeciwnym razie.
  4. first ( P , c ): wygeneruj pierwsze rozszerzenie kandydata c .
  5. next ( P , s ): wygeneruj następne alternatywne rozszerzenie kandydata, po rozszerzeniu s .
  6. wyjście ( P , c ): użyj rozwiązania c z P , odpowiednio do zastosowania.

Algorytm cofania redukuje problem do wywołania zwrotnego ( root ( P ) ), gdzie backtrack jest następującą rekurencyjną procedurą:

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)

Uwagi dotyczące użytkowania

Procedura odrzucenia powinna być funkcją o wartości logicznej, która zwraca prawdę tylko wtedy, gdy jest pewne, że żadne możliwe rozszerzenie c nie jest prawidłowym rozwiązaniem dla P . Jeśli procedura nie może doprowadzić do definitywnego zakończenia, powinna zwrócić false . Nieprawidłowy prawdziwy wynik może spowodować, że procedura bt pominie niektóre poprawne rozwiązania. Procedura może przyjąć, że odrzuci ( P , T ) zwrócone false dla każdego przodka t o C w drzewie wyszukiwania.

Z drugiej strony, wydajność algorytmu z wycofywaniem zależy od odrzucenia zwracającego prawdę dla kandydatów znajdujących się jak najbliżej korzenia. Jeśli odrzucenie zawsze zwraca false , algorytm nadal znajdzie wszystkie rozwiązania, ale będzie to równoważne przeszukaniu siłowemu.

Procedura akceptacji powinna zwrócić wartość true, jeśli c jest kompletnym i poprawnym rozwiązaniem dla wystąpienia problemu P , a false w przeciwnym razie. Można założyć, że częściowy kandydat c i wszyscy jego przodkowie w drzewie przeszli test odrzucenia .

Powyższy ogólny pseudokod nie zakłada, że ​​poprawnymi rozwiązaniami są zawsze liście potencjalnego drzewa wyszukiwania. Innymi słowy, dopuszcza możliwość, że ważne rozwiązanie dla P można dalej rozszerzyć, aby uzyskać inne ważne rozwiązania.

W pierwsze i następne procedury wykorzystywane w algorytmie wycofywania wyliczyć potomnych c drzewa, czyli kandydaci, które różnią się od C w pojedynczym etapie wydłużania. Połączenie pierwszym ( P , C ) powinno dostarczyć pierwszy dziecko C w pewnym porządku; a wywołanie next ( P , s ) powinno zwrócić następne rodzeństwo węzła s , w tej kolejności. Obie funkcje powinny zwrócić charakterystycznego kandydata "NULL", jeśli żądany element potomny nie istnieje.

Razem, korzeń , pierwszy , i kolejne funkcje określają zbiór częściowych kandydatów oraz potencjalnego drzewa wyszukiwania. Powinny być tak dobrane, aby każde rozwiązanie P występowało gdzieś w drzewie i żaden kandydat częściowy nie występował więcej niż raz. Ponadto powinni dopuścić wydajny i skuteczny predykat odrzucenia .

Warianty wczesnego zatrzymania

Powyższy pseudokod wywoła dane wyjściowe dla wszystkich kandydatów, którzy są rozwiązaniem dla danego wystąpienia P . Algorytm można zmodyfikować tak, aby zatrzymać się po znalezieniu pierwszego rozwiązania lub określonej liczby rozwiązań; lub po przetestowaniu określonej liczby kandydatów cząstkowych lub po spędzeniu określonej ilości czasu procesora .

Przykłady

Sudoku rozwiązany przez backtracking.

Przykłady, w których śledzenie wstecz może być wykorzystane do rozwiązywania zagadek lub problemów, obejmują:

Poniżej znajduje się przykład, w którym wycofywanie jest używane w przypadku problemu spełnienia ograniczeń :

Ograniczona satysfakcja

Ogólny problem spełnienia ograniczeń polega na znalezieniu listy liczb całkowitych x = ( x [1], x [2], …, x [ n ]) , każda w pewnym zakresie {1, 2, …, m }, która spełnia pewne ograniczenie arbitralne (funkcja logiczna) F .

Dla tej klasy problemów dane instancji P byłyby liczbami całkowitymi m i n oraz predykatem F . W typowym rozwiązaniu tego problemu z nawracaniem można zdefiniować częściowego kandydata jako listę liczb całkowitych c = ( c [1], c [2], …, c [k]) , dla dowolnego k pomiędzy 0 a n , który mają być przypisane do pierwszych k zmiennych x [1], x [2], …, x [ k ] . Kandydat root byłby wtedy pustą listą (). W pierwsze i następnych procedur będzie wtedy

function first(P, c) is
    k ← length(c)
    if k = n then
        return NULL
    else
        return (c[1], c[2], …, c[k], 1)
function next(P, s) is
    k ← length(s)
    if s[k] = m then
        return NULL
    else
        return (s[1], s[2], …, s[k − 1], 1 + s[k])

Tutaj długość ( c ) jest liczbą elementów na liście c .

Wywołanie odrzucenia ( P , c ) powinno zwrócić wartość true , jeśli ograniczenie F nie może być spełnione przez żadną listę n liczb całkowitych rozpoczynającą się od k elementów c . Aby śledzenie wsteczne było skuteczne, musi istnieć sposób na wykrycie tej sytuacji, przynajmniej dla niektórych kandydatów c , bez wyliczania wszystkich tych m nk n -krotek.

Na przykład, jeśli F jest koniunkcją kilku predykatów logicznych, F = F [1] ∧ F [2] ∧ … ∧ F [ p ] , a każde F [ i ] zależy tylko od małego podzbioru zmiennych x [1 ], …, x [ n ] , procedura odrzucenia może po prostu sprawdzić warunki F [ i ] , które zależą tylko od zmiennych x [1], …, x [ k ] , i zwrócić true , jeśli którykolwiek z tych warunków zwróci false . W rzeczywistości odrzucenie wymaga sprawdzenia tylko tych terminów, które zależą od x [ k ], ponieważ terminy zależne tylko od x [1], …, x [ k − 1] będą testowane dalej w drzewie wyszukiwania.

Zakładając, że odrzucenie jest zaimplementowane jak powyżej, to accept ( P , c ) wymaga jedynie sprawdzenia, czy c jest kompletne, czyli czy ma n elementów.

Generalnie lepiej jest uporządkować listę zmiennych tak, aby zaczynała się od tych najbardziej krytycznych (tzn. tych, które mają najmniej opcji wartości lub które mają większy wpływ na kolejne wybory).

Można by również pozwolić następnej funkcji na wybór, która zmienna ma być przypisana podczas rozszerzania kandydata częściowego, na podstawie wartości zmiennych już przez nią przypisanych. Dalsze ulepszenia można uzyskać dzięki technice propagacji ograniczeń .

Oprócz zachowywania minimalnych wartości odzyskiwania używanych podczas tworzenia kopii zapasowych, implementacje śledzenia wstecznego zwykle prowadzą zmienny ślad, aby rejestrować historię zmian wartości. Wydajna implementacja pozwoli uniknąć tworzenia zmiennego wpisu śladu między dwiema kolejnymi zmianami, gdy nie ma punktu wyboru, ponieważ cofanie usunie wszystkie zmiany jako jedną operację.

Alternatywą dla śladu zmiennej jest zachowanie znacznika czasu, kiedy dokonano ostatniej zmiany w zmiennej. Sygnatura czasowa jest porównywana ze sygnaturą czasową punktu wyboru. Jeśli punkt wyboru ma skojarzony czas późniejszy niż czas zmiennej, nie ma potrzeby przywracania zmiennej, gdy punkt wyboru jest cofany, ponieważ został zmieniony przed wystąpieniem punktu wyboru.

Zobacz też

Uwagi

Bibliografia

Dalsza lektura

Linki zewnętrzne