Algorytmy z powrotami

https://en.wikipedia.org/wiki/Backtracking

https://en.wikipedia.org/wiki/Stable_marriage_problem (Gale, Shapley, 1962)

WPROWADZENIE

Algorytmy z powrotami (ang. backtracking) są algorytmami rekurencyjnymi. Szukamy algorytmów poszukujących rozwiązań dla specyficznych problemów metodą prób i błędów. Zwykle stosowanym tu sposobem jest podział rozwiązywanego zadania na podzadania. Dla takich zadań często najbardziej naturalnym opisem jest opis rekurencyjny.

Cały proces rozwiązywania problemu można potraktować jako proces poszukiwań w drzewie podzadań. Zwykle drzewo podzadań rośnie bardzo szybko (wykładniczo) i równie szybko rośnie ilość pracy związana z przeglądaniem drzewa. Najczęściej drzewo można stopniowo obcinać stosując reguły heurystyczne, co pozwala zredukować obliczenia. Algorytmy z powrotami uzyskały znaczenie prawie wyłącznie dzięki maszynom cyfrowym, które mogą cierpliwie i dokładnie sprawdzać ogromną liczbę wariantów.

Wirth omawia ogólne zasady podziału zadań, związanych z rozwiązywaniem pewnej klasy problemów, na podzadania oraz możliwości stosowania rekurencji. Kod może być zorganizowany na kilka sposobów.

• Znajdowanie pojedynczego rozwiązania danego problemu. Przykładem jest określenie drogi skoczka szachowego i rozmieszczenie ośmiu hetmanów. Każde rozwiązanie jest jednakowo dobre, więc kończymy poszukiwania po znalezieniu pierwszego rozwiązania.
• Znajdowanie wszystkich rozwiązań danego problemu. Przykładem jest układanie pentomino, ale także problem skoczka szachowego i problem ośmiu hetmanów.
• Znajdowanie optymalnego rozwiązania. Należy wygenerować wszystkie możliwe rozwiązania i zachować jedno w pewnym sensie optymalne. Musimy mieć daną pewną funkcję f(), która będzie mierzyć wartość każdego rozwiązania. Przykładem jest poszukiwanie największego zbioru niezależnego w grafie, a funkcja f() będzie zwracać liczność znalezionego zbioru niezależnego. Podczas pracy algorytmu przechowujemy najlepsze z dotychczasowych rozwiązań, ponadto trzeba rozpocząć od poprawnej wartości początkowej, np. zbiór niezależny pusty lub jednoelementowy.

Cechy charakterystyczne algorytmów z powrotami:

• Kolejne kroki, które mogłyby doprowadzić do rozwiązania końcowego są zapisywane. Jeżeli dochodzimy do ślepej uliczki, to odpowiednie zapisy są usuwane.
• Liczba potencjalnych kandydatów w każdym kroku jest skończona, ale może się zmieniać w kolejnych krokach.
• Programy często używają parametru jawnie określającego głębokość rekurencji, co pozwala na proste sformułowanie warunku zakończenia.

Algorytm z powrotami jest właściwie metaheurystyką niż specyficznym algorytmem. Użytkownik musi określić problem do rozwiązania, naturę częściowego rozwiązania i jak należy częściowe rozwiązanie uzupełniać w celu otrzymania pełnego rozwiązania. W przeciwieństwie do wielu innych metaheurystyk, mamy tu gwarancję znalezienia wszystkich rozwiązań w ograniczonym zakresie czasu.

Wybrane problemy rozwiązywane za pomocą algorytmów z powrotami:

• Problem skoczka szachowego.
• Problem ośmiu hetmanów.
• Problem dokładnego pokrycia zbioru. Przykładami są układanie kwadratu łacińskiego n × n (ang. latin square) lub sudoku (różne warianty planszy: 4 × 4, 6 × 6, 9 × 9, itp.).
• Problem trwałego małżeństwa [Wirth]. Mamy dane n kobiet i n mężczyzn. Każda kobieta i każdy mężczyzna szereguje partnerów według preferencji. Jeżeli n par zostało dobranych tak, że istnieje mężczyzna i kobieta, którzy nie stanowią małżeństwa, ale mężczyzna przedkłada tę kobietę nad aktualną żonę, a kobieta przedkłada tego mężczyznę nad aktualnego męża, to taki dobór małżeństw jest nietrwały. Jeżeli żadna taka para nie istnieje, to dobór małżeństw jest trwały..
• Problem m-kolorowania grafu (ang. m coloring problem). Jest to problem kolorowania wierzchołków grafu nieskierowanego m kolorami. Przy rozwiązywaniu metodą siłową mamy m^n rozwiązań do sprawdzenia.
• Problem optymalnego wyboru [Wirth]. Przykładem jest problem znalezienia największego zbioru niezależnego w grafie nieskierowanym lub problem plecakowy.