5996833060

Metoda z nawrotami - zapis rekurencyjny:

Dane: Labirynt, czyli prostokąt z jednym wyjściem, wypełniony ścianami, które są równoległe do zewnętrznych ścian i nie tworzą zamkniętych obszarów. Dany jest punkt v wewnątrz labiryntu.

Wynik: Droga w labiryncie, która prowadzi z punktu v do wyjścia.

Krok 1. Dla każdego kolejnego kierunku (G,L,P,D) poruszania się z punktu v, jeśli istnieje w tym kierunku nieodwiedzone pole w i nie jest ono odgrodzone od pola v ścianą, to przejdź do kroku 2, a w przeciwnym razie zakończ to wywołanie algorytmu.

Krok2. Jeśli wyjście z labiryntu jest w jednej ze ścian pola w, to zakończ algorytm. W przeciwnym razie oznacz pole w jako odwiedzone i wywołaj ten algorytm dla tego pola w .

W zapisie tym pozornie nie ma ruchu do tylu B. W praktyce ruch ten jest wykonywany zawsze, gdy w wyniku wywołań rekurencyjnych docieramy do miejsca, w którym nie możemy przejść do nowego pola labiryntu i przechodzimy do drugiego etapu rekurencji - powrotu z kolejnych wywołań.

Znajdowanie najkrótszej drogi wyjścia z labiryntu - generowanie pól.

Metoda z nawrotami zawsze znajduje drogę wyjścia z labiryntu, ale nie można być zadowolonym z szybkości wykonania zadania - długo trzeba krążyć, aby trafić do wyjścia.

Należy pamiętać, że zarówno metoda po omacku, jak metoda z nawrotami może służyć do znajdowania wyjścia z labiryntu którego układ jest nieznany.

Metoda generacji pól będzie działać dla labiryntu, którego schemat znamy.