headerphoto

Algorytmy z powrotami - Zasada działania

Podstawowe pojęcia

Zanim przejdę do zasadniczego omówienia techniki algorytmów z powrotami, chciałbym pokrótce przedstawić najważniejsze pojęcia z teorii grafów. Jest to wiedza niezbędna do zrozumienia idei programowania algorytmów z powrotami. Na szczęście pojęcia związane z grafami nie są zbyt skomplikowane, a ponadto w bardzo łatwy sposób można je przełożyć ze świata matematycznej abstrakcji do sytuacji łatwo wyobrażalnych w świecie rzeczywistym.

Graf, jest to zbiór wierzchołków (węzłów) oraz łączących je krawędzi. Szczególnym rodzajem grafu jest drzewo. Jest to graf, w którym istnieje dokładnie jedna ścieżka (sekwencja krawędzi) łącząca dowolne dwa wierzchołki. Tak jak w prawdziwym drzewie, panuje tutaj pewna logiczna hierarchia ułożenia wierzchołków oraz krawędzi. Wyróżniamy w nim korzeń, z którym połączone są wszystkie wierzchołki (i z którego bezpośrednio lub pośrednio "wyrastają"). Korzeń w drzewie można porównać do pary najstarszych przodków w rodzinnym drzewie genealogicznym. Istnieje dokładnie jedna ścieżka między danym węzłem a korzeniem (potomkiem a praprzodkami). Przyjmujemy, że ścieżka to ciąg krawędzi (na Rys.1 przykładowa ścieżka do węzła "6" zaznaczona jest linią przerywaną). Liczba krawędzi w ścieżce jest nazywana długością, zaś liczba o jeden większa określa poziom węzła (czyli pokolenie w przykładowym drzewie genealogicznym). Jak nie trudno się domyślić, z jednego węzła może "wyrastać" wiele innych węzłów (tak jak para przodków może posiadać wiele dzieci). Są to tzw. węzły potomne. Wierzchołek nie musi oczywiście posiadać żadnych potomków, wtedy nazywany jest liściem.

Rys 1. Budowa drzewa


Zasada działania algorytmów z powrotami

Algorytmy z powrotami zalicza się do rodziny algorytmów kombinatorycznych. Ich zadaniem jest odnalezienie w strukturze danych, pewnego szczególnego elementu, który spełnia ściśle określone kryteria. Dla przykładu strukturą danych może być labirynt składający się ze skrzyżowań, dróg i ślepych zaułków. Szukanie wyjścia to właśnie sprawdzanie kolejnych skrzyżowań pod kątem tego czy doprowadzą nas do wyjścia z labiryntu czy też nie. Co jednak zrobić, jeśli w czasie poruszania się po labiryncie dotrzemy do ślepego zaułka? Naturalnie należy wrócić się do poprzedniego rozgałęzienia i pójść inną drogą. Tak właśnie działają algorytmy z powrotami. Przekładając ten przykład na teorię grafów, można powiedzieć, że ze zbioru potencjalnych rozwiązań (struktury danych) tworzony jest graf, lub inaczej drzewo przestrzeni stanów (przykładowy labirynt), składający się z wierzchołków (skrzyżowań) i krawędzi (dróg). Algorytm porusza się w głąb drzewa po kolejnych wierzchołkach w poszukiwaniu optymalnego rozwiązania. Po dojściu do wierzchołka, który rokuje znalezienie "wyjścia z labiryntu" (nazywamy go wtedy węzłem obiecującym), algorytm rozwija i sprawdza jego węzły potomne. Jeśli zaś wierzchołek nie rokuje znalezienia rozwiązania (węzeł jest nieobiecujący), to algorytm cofa się w drzewie o jeden poziom i sprawdza kolejny nie rozwinięty jeszcze węzeł.

Realizacja w praktyce tego interesującego mechanizmu przeszukiwania drzewa przestrzeni stanów możliwa była poprzez zastosowanie klasycznego i uniwersalnego algorytmu przeszukiwania w głąb (DFS, ang. depth-first search). Jest to sprytny i silny algorytm rekurencyjny znajdujący często zastosowanie w problemach związanych z teorią grafów. Jego zasada działania polega na całościowym przeszukaniu drzewa przestrzeni stanów, czyli na odwiedzeniu wszystkich wierzchołków i zbadaniu każdej krawędzi w danym grafie. Algorytm przeszukuje drzewo zaczynając od korzenia, po czym kieruje się w dół do liścia, następnie wraca się o jeden poziom i testuje kolejne węzły, przechodząc w głąb tak daleko, jak jest to tylko możliwe.

Aby możliwe było zastosowanie metody przeszukiwania DFS, graf musi być spójny, czyli konieczne jest, aby istniała droga pomiędzy dwoma dowolnymi wierzchołkami w tym grafie (tzn. by z dowolnego wierzchołka możliwe było przejście do wszystkich pozostałych). Drzewo z definicji spełnia to założenie.

Rys 2. Kolejność odwiedzania węzłów przy zastosowaniu algorytmu
przeszukiwania w głąb (DFS)


Implementacja algorytmu przeszukiwania w głąb w dowolnym języku programowania polega na zastosowaniu prostej metody rekurencyjnej. W ten sposób mamy gwarancję, że funkcja przeszukująca zostanie wywołana dla każdego węzła w drzewie przestrzeni stanów. W pseudokodzie, algorytm ten wygląda następująco:


void przeszukiwanie_w_głąb (Węzeł v)
{
 Węzeł u;
 Odwiedź v;
    for (dla każdego węzła u, który jest potomkiem węzła v)
        przeszukiwanie_w_głąb (u)
}


Na potrzeby programowania algorytmów z powrotami zmodyfikowano nieco technikę przeszukiwania w głąb. Tak jak wspomniałem wcześniej, klasyczny algorytm przeszukiwania DFS, polega na przeszukaniu drzewa przestrzeni stanów w całości. Jednak sedno skuteczności algorytmów z powrotami kryje się w znacznym zredukowaniu liczby sprawdzanych węzłów. Co za tym idzie, aby dojść do interesującego nas rozwiązania, nie musimy sprawdzać wszystkich węzłów w drzewie przestrzeni stanów, lecz tylko niewielką ich część. Każdy napotkany węzeł klasyfikowany jest pod kątem ścisłych kryteriów (w zależności od konkretnego algorytmu z powrotami). Dzięki tym ograniczeniom, algorytm potrafi określić czy dany węzeł jest obiecujący czy też nie.