5996833056

Wychodzenie z labiryntu i pakowanie plecaka.

Zadania te nazywane są problemami optymalizacji, które dotyczą znajdowania najlepszego rozwiązania wśród wielu możliwych rozwiązań spełniających pewne warunki.

Rozwiązania powyższych zadań są jednocześnie przykładem metod heurystycznych, wykorzystujących intuicyjne sposoby otrzymania możliwie najlepszych rozwiązań - metody te są szybkie i mają duże znaczenie praktyczne.

Znajdowanie wyjścia z labiryntu.

Labirynt jest zamknięty w prostokącie, ma tylko jedno wyjście/wejście i wszystkie ściany wewnętrzne są równolegle do zewnętrznych. W labiryncie nie ma zamkniętych obszarów, tzn. z każdego pola istnieje droga prowadząca do wyjścia.

Pola labiryntu można ponumerować/nazwać jak na szachownicy.

Naszym celem jest podanie algorytmu, który z każdego punktu labiryntu zaprowadzi nas do wyjścia, bez zbędnego kluczenia.

W algorytmie takim zawsze można wyróżnić dwa elementy:

-    regułę gwarantującą, że żadnego odcinka drogi w labiryncie nie przechodzimy więcej niż jeden raz

-    strategię jak najszybszego wyjścia z labiryntu

Metoda po omacku (z ręka na ścianie ).

Po wybraniu kierunku poruszamy się, trzymając cały czas jedną (ale tę samą) rękę na ścianie - idziemy wzdłuż ścian.

Poruszając się w ten sposób albo trafimy do wyjścia, albo wrócimy do punktu, w którym już byliśmy.