1531834462

<15>

> Techniki algorytmiczne - przybliżone i dokładne

mi są: G-4a, G-5a, G-6a, L-6b, L-5b, G-4b. Z pola 4b nie możemy jednak przejść na pole 4a, aby się nie zapę-tlić, gdyż przechodziliśmy już przez nie w tym poszukiwaniu wyjścia, zatem wracamy: B-5b, B-6b, B-6a, B-5a, B-4a, B-3a, a dalej już do wyjścia: L-3b, L-2b, P-2c, L-lc.

a b c d e f g h j

Rysunek 4.

Poszukiwanie wyjścia z labiryntu przedstawionego na rys. 3, zaczynając w polu 4a. Kolejno wykonywane ruchy i odwiedzane pola: G-3a, G-2a, G-la, P-lb, B-la, B-2a, B-3a, P-3b, L-2b, P-2c, L-lc

Ćwiczenie 20. Posługując się algorytmem Zgłębianie labiryntu wypisz kolejno odwiedzane pola na drodze do wyjścia z pola 4g w labiryncie pokazanym na rys. 3. jest to jednak dość długa droga - aby ją znaleźć, musisz przejść przez 26 pól, przez niektóre po kilka razy.

Przedstawiony algorytm jest realizacją metody przeszukiwania przestrzeni możliwych rozwiązań, która nazywa się przeszukiwaniem w głąb, gdyż w kolejnych krokach przeszukiwanie zagłębia się coraz bardziej, tak daleko, jak to możliwe. Ten algorytm należy również do rodziny metod nazywanych przeszukiwaniem z nawrotami, gdyż są w nim wykonywane nawroty do poprzednich punktów, gdy poszukiwanie zabrnie w ślepy zaułek i nie można kontynuować go do przodu.

Zauważmy, jak proste jest sformułowanie algorytmu Zgłębianie labiryntu. Tę prostotę zawdzięczamy przede wszystkim użyciu w jego opisie rekurencji - w obu krokach 1 i 2 następuje rekurencyjne odwołanie do kroku 1 z nowego pola w labiryncie, w którym znalazł się proces poszukiwania.

Zgodnie z naszym założeniem, w labiryncie nie ma obszarów zamkniętych, a więc z każdego pola istnieje droga do wyjścia. Na tej podstawie nie powinieneś mieć kłopotu z wykonaniem następnego ćwiczenia.

Ćwiczenie 21. Uzasadnij, że z każdego pola labiryntu algorytm z nawrotami Zgłębianie labiryntu znajdzie drogę z tego pola do wyjścia z labiryntu.

Algorytm przeszukiwania z nawrotami ma bardzo intuicyjny opis w poszukiwania wyjścia z labiryntu, konstruujemy dla labiryntu od po w a krawędziami możliwe przejścia między nimi - i przeszukujemy go gorytmu Zgłębiania labiryntu zostanie przedstawiona na innych zaji rytmom.

3.2 ROZMIESZCZANIE HETMANÓW NA SZACHOWNICY

Zakładamy, że wiesz jak wygląda szachownica. Jeśli natomiast nie umiesz grać w szachy, to przyjmij, że hetman jest figurą, która atakuje figury stojące na wszystkich liniach przechodzących przez pole, na którym stoi - poziomej, pionowej i obu przekątnych, tak jak na tym rys. 5 - hetman stoi na polu b3:

Problem hetmanów polega na rozmif żadne dwa nie atakują się. Zastosuje

iu na szachownicy jak największej liczby hetmanów, z których todę przeglądania możliwych ustawień hetmanów, ale oczywi-

%

KAPITAŁ LUDZKĄ