labirynt

- zbiór krętych, przeważnie poplątanych korytarzy, z których znaczny procent stanowią ślepe uliczki, a inne prowadzą do punktu docelowego lub wyjścia. W psychologii eksperymentalnej l. to przyrząd w formie l. służący do badania procesu uczenia się oraz rozwiązywania zadań przez zwierzęta i ludzi; w cybernetyce - model fizyczny lub tylko matematyczny takich procesów. Pierwsze badania labiryntowe podjęli w psychologii pod koniec ubiegłego stulecia W.S. Small i E.L. Thorndike, w cybernetyce w latach pięćdziesiątych naszego wieku C. Shannon. Najprostsza postać l. tzw. l. zwyrodniały, jest korytarzem bez rozgałęzień, biegnącym po linii prostej bądź łamanej; we właściwym tego słowa znaczeniu l. jest jednak dopiero system korytarzy z rozgałęzieniami. Zadanie rozwiązania l. polega na zapisaniu w pamięci informacji o strukturze l. jako grafu i znalezieniu możliwie jak najkrótszej drogi do celu, bez błądzenia. W modelowaniu cybernetycznym w procesie gromadzenia informacji o strukturze l., zależności między pojemnością pamięci i wyborem strategii oraz problem algorytmizacji znajdowania najkrótszej drogi. Utrwalenie informacji o strukturze l. następuje w zasadzie w wyniku jednorazowego przejścia, możliwe jest jednak imitowanie procesu uczenia się poprzez szereg przejść, z coraz lepszym zapamiętywaniem struktury i zmniejszaniem sie liczby błędów (m. in. osiąga się to przy ograniczonej pojemności pamięci).



Cybernetyczne modele rozwiązywania zadań labityntowych mogą mieć charakter teoretyczny i fizyczny lub tylko teoretyczny. Teoretyczne badanie l. może być traktowane jako proces uczenia się drogą prób i błędów lub gra z naturą. Modele fizyczne są niekiedy urządzeniami imitującymi, nawet w formie zewnętrznej, ruch zwierzęcia w l. (badacz labiryntu). Rozwiązywanie zadań modeluje się także za pomocą maszyn liczących. Makieta l. z poruszającym się w nim zwierzęciem



jest tylko poglądową postacią procesu rozwiązywania zadania przez maszynę liczącą. Dla ułatwienia algorytmizacji rozwiązywania zadań labiryntowych korytarze dzieli się na komórki, najczęściej prostokątne pola. Kiektóre typy l. komórkowych mogą przedstawione w uproszczonej, lecz równoważnej postaci tzw. dendrytu. Podstawowymi elementami struktury takiego l. są połączone odpowiednio punkty (komórki) l., z których drogi rozchodzą się co najmniej w trzech kierunkach. Zapamiętanie tych punktów ma ważne znaczenie w procesie uczenia się l.



W modelowaniu badania l. stosuje się zarówno ściśle ustalone, jak też losowe metody przechodzenia l. Do pierwszych, a zarazem najprostszych, należy znana zasada jednej ręki; polega ona na tym, że bada się labirynt trzymając się stale jednej ze ścian (prawej lub lewej). Metoda ta umożliwia przebycie l. i opuszczenie go po ściśle określonej liczbie kroków, wyklucza jednak zbadanie wszystkich korytarzy, a więc, w pewnych rodzajach l., również dotarcie do celu. Przypadkowe ominięcie jakiegoś bocznego odgałęzienia korytarza po stronie "prowadzącej" grozić może w pewnych typach l. znalezieniem się w zamkniętej pętli wewnętrznych korytarzy. W modelowaniu badania l. metodą prób i błędów najczęściej stosuje się ściśle określony program. Jeśli ogranicza się on do ruchu prostoliniowego i zmiany kierunku z chwilą napotkania przeszkody (np. zwrot w prawo o 90 stopni i dalszy ruch prostoliniowy), może nie wystarczyć do przebycia bardziej złożonego l., powodując bądź cofnięcie się do wejścia tą samą drogą, bądź wpadnięcia w zamkniętą pętlę. Można wyeliminować to niebezpieczeństwo przez rozbudowę programu, np. jego modyfikację po kilkakrotnym przebyciu tej samej drogi. Wprowadzenie czynnika losowości najlepiej usuwa te trudności, może jednak przedłuzyć czas badania l. i komplikuje konstrukcję modelu. Do takich programów należy losowy wybór kierunku z tym, że jeśli wybór był niewłaściwy i napotyka się przeszkodę, kierunek ten zostaje wyeliminowany spośród dalszych wyborów losowych, każdy zaś prawidłowy krok zwiększa prawdopodobieństwo utrzymania przyjętego kierunku ruchu. Skrócenie drogi przy ponownym przechodzeniu l. polega na eliminacji ślepych uliczek i pętli. Podstawową rolę odgrywa tu pamięć modyfikująca program ruchu "badacza".



Sposób rozwiązania zadania zależy w znacznym stopniu od względnej pojemności pamięci. Gdy pojemność ta jest dostatecznie duża, zapisana w niej może być pełna informacja o l. Kiedy brak jeszcze informacji o l. kierunek przejścia z dowolnego pola na jedno z czterech sąsiednich wyznacza ustalony program. Każdy ruch zapisany zostaje w pamięci ze wskazaniem, czy przejście było możliwe. Jesli nie - operator ponawia próbę w innym kierunku. Każdy ruch zwiększa więc informację o zakazanych i dozwolonych kierunkach ruchu. Jeśli przy pierwszym przechodzeniu l. "badacz" przebywa granicę dwóch pól dwukrotnie: tam i z powrotem, fakt ten może być zapisany w pamięci w sposób identyczny jak cofnięcie się przy natrafieniu na przeszkodę. Mamy więc trzy rodzaje informacji o każdym dowolnym kierunku ruchu "badacza" z danego pola: ao - nie przechodził granicy między polami, a1 - przeszedł granicę między polami, a2 - przeszedł granicę w dwóch kierunkach lub granica była zamknięta przeszkodą, np. ścianą labiryntu. Algorytm przyśpieszenia powtórnego przejścia można w tym wypadku sprowadzić do wykluczenia kierunków zapisanych liczbą parzystą (0 liczba parzysta). "Badacz" omija wówczas ślepe uliczki. Gdy ograniczona pojemność pamięci uniemożliwia zapisanie pełnej informacji o l., problem staje się trudniejszy i dla wielu przypadków nie został jeszcze w pełni rozwiązany. Należy on do zagadnień szczególnie interesujących z uwagi na uderzające podobieństwo z wieloma życiowymi przypadkami rozwiązywania zadań tego typu, np. orientacją w terenie według charakterystycznych punktów topograficznych, odnajdywaniem określonej książki w bibliotece, rozwiązywaniem zagadki kryminalnej, gdy nie dysponujemy pełną informacją (heurystyka). Jedną z dróg rozwiązania problemu l. jest wówczas gromadzenie informacji tylko o tych punktach, w których droga się rozgałęzia. Informacja dotyczy wtedy związku między odległymi punktami rozgałęzień (wierzchołek grafu) i l. sprowadza się do sieci złożonej z połączonych węzłów. W l. kwadratowym liczba elementów do zapamiętania jest w takim przypadku mniejsza od liczby wszystkich przejść z pola na pole. Inna droga rozwiązywania problemu przypomina badanie z gromadzeniem pełnej informacji, lecz kolejnymi fragmentami. Po zbadaniu określonego fragmentu, pełna informacja zostaje starta z pozostaje starta z pozostawieniem tylko informacji o drodze skróconej. Metod takich może być zresztą wiele. W szczególności użyteczne okazują się kombinacje między nimi, dostosowywanie do konkretnych sytuacji, przy czym wybór metody może być dokonany losowo bądź w oparciu o określone kryterium. [K.Bo.]