Algorytm rozwiązywania labiryntów

Robot w drewnianym labiryncie

Algorytm rozwiązywania labiryntów to zautomatyzowana metoda rozwiązywania labiryntu . Algorytmy losowej myszy, podążania za ścianą, Pledge'a i Trémaux są przeznaczone do użytku wewnątrz labiryntu przez podróżnika bez wcześniejszej wiedzy o labiryncie, podczas gdy algorytmy wypełniania ślepej uliczki i najkrótszej ścieżki są przeznaczone do użytku przez osobę lub program komputerowy, który może zobaczyć cały labirynt na raz.

Labirynty niezawierające pętli są znane jako labirynty „po prostu połączone” lub „doskonałe” i są odpowiednikiem drzewa w teorii grafów. Algorytmy rozwiązywania labiryntów są ściśle związane z teorią grafów . Intuicyjnie, jeśli we właściwy sposób przeciągnąć i rozciągnąć ścieżki w labiryncie, wynik mógłby przypominać drzewo.

Losowy algorytm myszy

Jest to trywialna metoda, którą może zaimplementować bardzo nieinteligentny robot lub mysz. Polega to po prostu na podążaniu aktualnym przejściem aż do skrzyżowania, a następnie podjęciu przypadkowej decyzji co do dalszego kierunku. Chociaż taka metoda zawsze ostatecznie znalazłaby właściwe rozwiązanie , ten algorytm może być bardzo powolny.

Zwolennik ściany

Trawersowanie przy użyciu reguły prawej ręki

Najbardziej znaną regułą pokonywania labiryntów jest reguła podążania za ścianą , znana również jako reguła lewej ręki lub reguła prawej ręki . Jeśli labirynt jest po prostu połączony , to znaczy wszystkie jego ściany są połączone razem lub z zewnętrzną granicą labiryntu, to trzymając jedną rękę w kontakcie z jedną ścianą labiryntu, rozwiązujący ma gwarancję, że się nie zgubi i dotrze do innego wyjścia, jeśli takie istnieje; w przeciwnym razie algorytm powróci do wejścia po przejściu co najmniej raz każdego korytarza obok tego połączonego fragmentu ścian. Algorytm jest uporządkowany według głębokości przeprawa po drzewie .

Inne spojrzenie na to, dlaczego podążanie za ścianą działa, jest topologiczne. Jeśli ściany są połączone, mogą zostać zdeformowane w pętlę lub okrąg. Następnie podążanie za ścianą sprowadza się do chodzenia po okręgu od początku do końca. Aby rozwinąć ten pomysł, zauważ, że poprzez zgrupowanie połączonych elementów ścian labiryntu, granice między nimi są dokładnie rozwiązaniami, nawet jeśli istnieje więcej niż jedno rozwiązanie (patrz rysunki po prawej).

Jeśli labirynt nie jest po prostu połączony (tj. jeśli punkty początkowe lub końcowe znajdują się w środku struktury otoczone pętlami przejścia lub ścieżki krzyżują się i pod sobą, a takie części ścieżki rozwiązania są otoczone pętlami przejścia), ta metoda niekoniecznie doprowadzi do celu.

Innym problemem jest to, że należy uważać, aby rozpocząć podążanie za ścianą przy wejściu do labiryntu. Jeśli labirynt nie jest po prostu połączony i zaczyna się podążanie za ścianą w dowolnym punkcie wewnątrz labiryntu, można znaleźć się w pułapce wzdłuż oddzielnej ściany, która zapętla się wokół siebie i nie zawiera wejść ani wyjść. Jeśli okaże się, że podążanie za ścianą zaczyna się późno, spróbuj zaznaczyć miejsce, w którym zaczęło się podążanie za ścianą. Ponieważ podążanie za ścianą zawsze doprowadzi cię z powrotem do miejsca, w którym zacząłeś, jeśli po raz drugi natkniesz się na punkt początkowy, możesz dojść do wniosku, że labirynt nie jest po prostu połączony i powinieneś przełączyć się na alternatywną ścianę, której jeszcze nie pokonałeś. Zobacz Pledge Algorithm , poniżej, dla alternatywnej metodologii.

Podążanie za ścianą można wykonać w trójwymiarowych lub wielowymiarowych labiryntach, jeśli jego wielowymiarowe przejścia można rzutować na płaszczyznę 2D w deterministyczny sposób. Na przykład, jeśli w labiryncie 3D można założyć, że przejścia „w górę” prowadzą na północny zachód, a przejścia „w dół” na południowy wschód, wówczas mogą obowiązywać standardowe zasady podążania za ścianą. Jednak w przeciwieństwie do 2D wymaga to znajomości bieżącej orientacji, aby określić, który kierunek jest pierwszy po lewej, a który po prawej stronie.

Algorytm przysięgi


Po lewej: uwięziony solver skręcający w lewo Po prawej: rozwiązanie algorytmu Pledge

Rozłączne (gdzie ściany nie są połączone z zewnętrzną granicą / granica nie jest zamknięta) labirynty można rozwiązać metodą podążania za ścianą, o ile wejście i wyjście z labiryntu znajdują się na zewnętrznych ścianach labiryntu. Jeśli jednak rozwiązujący zaczyna w labiryncie, może znajdować się na odcinku rozłącznym z wyjściem, a wyznawcy ściany będą nieustannie krążyć wokół swojego pierścienia. Algorytm Pledge (nazwany na cześć Johna Pledge'a z Exeter) może rozwiązać ten problem.

Algorytm Pledge, przeznaczony do omijania przeszkód, wymaga arbitralnie wybranego kierunku, w którym będzie preferencyjny. Po napotkaniu przeszkody jedna ręka (np. prawa ręka) jest trzymana wzdłuż przeszkody, podczas gdy kąty obrócenia są liczone (obrót w prawo jest dodatni, obrót w lewo jest ujemny). Kiedy rozwiązujący ponownie zwraca się w pierwotnym preferowanym kierunku, a suma kątowa wykonanych skrętów wynosi 0, rozwiązujący opuszcza przeszkodę i kontynuuje poruszanie się w swoim pierwotnym kierunku.

Ręka jest usuwana ze ściany tylko wtedy, gdy zarówno „suma wykonanych obrotów”, jak i „aktualny kurs” są równe zeru. Pozwala to algorytmowi uniknąć pułapek w kształcie dużej litery „G”. przy ścianach zostaje obrócony o pełne 360 ​​stopni . Algorytm, który śledzi tylko „bieżący kurs”, prowadzi do nieskończonej pętli, gdy opuszcza dolną prawą ścianę kierując się w lewo i ponownie wpada do zakrzywionej sekcji po lewej stronie. Algorytm Pledge nie opuszcza skrajnej prawej ściany, ponieważ „suma wykonanych obrotów” nie wynosi zero w tym punkcie (uwaga 360 stopni nie jest równe 0 stopni ). Podąża wzdłuż ściany dookoła, w końcu pozostawiając ją skierowaną w lewo na zewnątrz i tuż pod kształtem litery.

Algorytm ten pozwala osobie z kompasem znaleźć drogę z dowolnego punktu wewnątrz do zewnętrznego wyjścia dowolnego skończonego dwuwymiarowego labiryntu, niezależnie od początkowej pozycji osoby rozwiązującej. Jednak ten algorytm nie zadziała w odwrotnej kolejności, a mianowicie w znalezieniu drogi od wejścia na zewnątrz labiryntu do jakiegoś końcowego celu w nim.

Algorytm Trémaux



Algorytm Trémaux. Duża zielona kropka pokazuje aktualną pozycję, małe niebieskie kropki pokazują pojedyncze znaki na wejściach, a czerwone krzyżyki pokazują podwójne znaki. Po znalezieniu wyjścia trasa jest śledzona przez pojedynczo oznaczone wejścia. Zauważ, że dwa znaki są umieszczane jednocześnie za każdym razem, gdy zielona kropka dociera do skrzyżowania. To dziwactwo ilustracji; każdy znak powinien być w rzeczywistości umieszczony zawsze, gdy zielona kropka przechodzi przez miejsce znaku.

Algorytm Trémaux, wymyślony przez Charlesa Pierre'a Trémaux , jest skuteczną metodą znajdowania wyjścia z labiryntu, która wymaga narysowania linii na podłodze w celu oznaczenia ścieżki i gwarantuje działanie dla wszystkich labiryntów, które mają dobrze zdefiniowane przejścia, ale nie gwarantuje znalezienia najkrótszej trasy.

Wejście do przejścia jest albo nieodwiedzane, oznaczone raz, albo oznaczone dwukrotnie. Należy pamiętać, że oznaczenie wejścia to nie to samo, co oznaczenie skrzyżowania lub przejścia, ponieważ skrzyżowanie może mieć wiele wejść, a przejście ma wejścia na obu końcach. Ślepe zaułki można traktować jako skrzyżowania z jednym wejściem (wyobraź sobie, że w każdym ślepym zaułku znajduje się pokój).

Algorytm działa według następujących zasad:

  • Za każdym razem, gdy przechodzisz przez wjazd na przejście, niezależnie od tego, czy chcesz wjechać, czy zjechać ze skrzyżowania, zostaw znak przy wjeździe.
  • Gdy jesteś na skrzyżowaniu, skorzystaj z pierwszej odpowiedniej zasady poniżej, aby wybrać wjazd do zjazdu:
    1. Jeśli zaznaczone jest tylko wejście, z którego właśnie przyszedłeś, wybierz dowolne nieoznakowane wejście, jeśli takie istnieje. Ta zasada obowiązuje również wtedy, gdy dopiero zaczynasz w środku labiryntu i nie ma żadnych oznaczonych wejść.
    2. Wybierz wejście, z którego właśnie przyszedłeś, chyba że jest zaznaczone dwukrotnie. Ta zasada będzie obowiązywać zawsze, gdy dotrzesz do ślepego zaułka.
    3. Wybierz dowolne wejście z najmniejszą liczbą znaków (zero, jeśli to możliwe, w przeciwnym razie jeden).

Zasada „odwróć się i wróć” skutecznie przekształca każdy labirynt z pętlami w po prostu połączony; ilekroć znajdziemy ścieżkę, która zamknie pętlę, traktujemy ją jako ślepy zaułek i wracamy. Bez tej zasady można odciąć sobie dostęp do niezbadanych jeszcze części labiryntu, jeśli zamiast zawrócić, dowolnie wybierzemy inne wejście.

Kiedy w końcu dotrzesz do rozwiązania, wejścia zaznaczone dokładnie raz wskażą drogę powrotną na start. Jeśli nie ma wyjścia, ta metoda zabierze Cię z powrotem na początek, gdzie wszystkie wejścia są oznaczone dwukrotnie. W tym przypadku każde przejście przechodzi się dokładnie dwa razy, po jednym w każdym kierunku. Wynikowy spacer nazywany jest dwukierunkowym podwójnym śledzeniem.

Zasadniczo ten algorytm, który został odkryty w XIX wieku, był używany około sto lat później jako przeszukiwanie w głąb .

Wypełnianie ślepej uliczki

Wideo zewnętrzne
video icon Strategia labiryntu: wypełnianie ślepej uliczki
video icon Algorytm rozwiązywania labiryntu

Wypełnianie ślepych zaułków to algorytm rozwiązywania labiryntów, który wypełnia wszystkie ślepe zaułki, pozostawiając niewypełnione tylko prawidłowe ścieżki. Można jej używać do rozwiązywania labiryntów na papierze lub za pomocą programu komputerowego, ale nie jest to przydatne dla osoby znajdującej się w nieznanym labiryncie, ponieważ ta metoda patrzy na cały labirynt naraz. Metoda polega na

  1. znajdź wszystkie ślepe zaułki w labiryncie, a potem
  2. „wypełnij” ścieżkę od każdego ślepego zaułka, aż do pierwszego skrzyżowania.

Pamiętaj, że niektóre przejścia nie staną się częścią ślepych zaułków, dopóki inne ślepe zaułki nie zostaną usunięte. Film przedstawiający ślepą uliczkę w akcji można zobaczyć po prawej stronie.

Wypełnianie ślepej uliczki nie może przypadkowo „odciąć” początku od końca, ponieważ każdy etap procesu zachowuje topologię labiryntu. Ponadto proces nie zatrzyma się „zbyt szybko”, ponieważ wynik nie może zawierać żadnych ślepych zaułków. Tak więc, jeśli wypełnianie ślepej uliczki zostanie wykonane w idealnym labiryncie (labiryncie bez pętli), pozostanie tylko rozwiązanie. Jeśli zostanie to zrobione na labiryncie częściowo oplecionym (labirynt z kilkoma pętlami), to pozostaną wszystkie możliwe rozwiązania, ale nic więcej. [1]

Algorytm rekurencyjny

Mając wszechwiedzący widok labiryntu, prosty algorytm rekurencyjny może powiedzieć, jak dotrzeć do końca. Algorytm otrzyma początkową wartość X i Y. Jeśli wartości X i Y nie znajdują się na ścianie, metoda wywoła się ze wszystkimi sąsiednimi wartościami X i Y, upewniając się, że nie używała już tych wartości X i Y wcześniej. Jeśli wartości X i Y są wartościami lokalizacji końcowej, wszystkie poprzednie wystąpienia metody zostaną zapisane jako poprawna ścieżka.

W efekcie jest to przeszukiwanie w głąb wyrażone w postaci punktów siatki. Widok wszechwiedzący zapobiega wchodzeniu w pętle przez zapamiętywanie. Oto przykładowy kod w Javie : 

     
    
     
   boolean  [][]  labirynt  =  nowy  boolean  [  szerokość  ][  wysokość  ]  ;  // Labirynt  boolean  [][]  wasHere  =  new  boolean  [  szerokość  ][  wysokość  ]  ;  boolean  [][]  correctPath  =  new  boolean  [  szerokość  ][  wysokość  ]  ;  // Rozwiązanie labiryntu  int  startX  ,  startY  
       

   
       

    
        0     ;  // Początkowe wartości X i Y labiryntu  int  endX  ,  endY  ;  // Końcowe wartości X i Y labiryntu  public  void  solveMaze  ()  {  labirynt  =  generuj Labirynt  ();  // Tworzenie labiryntu (false = ścieżka, prawda = ściana)  // Poniższe przypisanie wartości false jest zbędne, ponieważ Java domyślnie przypisuje elementom tablicy wartość false  for  (  int  row  =  ;  row  <  maze  .  length  ;  row  ++   
        
            0    
              
              
        
        )  // Ustawia tablice boolowskie na wartości domyślne  dla  (  int  col  =  ;  col  <  labirynt  [  wiersz  ]  .  length  ;  col  ++  ) {  wasHere  [  wiersz  ][  col  ]  =  false  ;  poprawna ścieżka  [  wiersz  ][  kolumna  ]  =  fałsz  ;  }  boolean  b  =  recursiveSolve  (  
    
    
    

      
              
      startX  ,  startY  );  // Zostawi cię z tablicą logiczną (correctPath)  // ze ścieżką wskazywaną przez prawdziwe wartości.  // Jeśli b jest fałszywe, labirynt nie ma rozwiązania  }  public  boolean  recursiveSolve  (  int  x  ,  int  y  )  {  if  (  x  ==  endX  &&  y  ==  endY  )  return  true  ;  // Jeśli dotarłeś do końca  if  (     
    
      
       0 
            labirynt  [  x  ][  y  ]  ||  wasHere  [  x  ][  y  ]  )  return  false  ;  // Jeśli jesteś na ścianie lub już tu byłeś  wasHere  [  x  ][  y  ]  =  true  ;  if  (  x  !=  )  // Sprawdza, czy nie na lewej krawędzi  if  (  recursiveSolve  (  x  -  1  ,  y  ))  {  
               
             
        
          
            
             // Przywołuje metodę numer jeden po lewej stronie  correctPath  [  x  ][  y  ]  =  true  ;  // Ustawia tę wartość ścieżki na true;  zwróć  prawdę  ;  }  if  (  x  !=  width  -  1  )  // Sprawdza, czy nie na prawej krawędzi  if  (  recursiveSolve  (  x  +  1  ,  y  ))  {  // Przywołuje metodę pierwszą po prawej stronie  correctPath  [  x  ][   
             
        
       0  
            
              
             
        
        y  ]  =  prawda  ;  zwróć  prawdę  ;  }  if  (  y  !=  )  // Sprawdza, czy nie na górnej krawędzi  if  (  recursiveSolve  (  x  ,  y  -  1  ))  {  // Przywołuje metodę jeden w górę  correctPath  [  x  ][  y  ]  =  true  ;  zwróć  prawdę  ;  }  jeśli  (  y  !=  wysokość    
            
              
             
        
     
 -  1  )  // Sprawdza, czy nie na dolnej krawędzi  if  (  recursiveSolve  (  x  ,  y  +  1  ))  {  // Przywołuje metodę o jeden w dół  correctPath  [  x  ][  y  ]  =  true  ;  zwróć  prawdę  ;  }  zwróć  fałsz  ;  }

Algorytm wyznaczania trasy labiryntu

Algorytm wyznaczania tras w labiryncie to niskonakładowa metoda znajdowania drogi między dowolnymi dwoma lokalizacjami labiryntu. Algorytm jest początkowo proponowany dla układów wieloprocesorowych (CMPs) i gwarantuje działanie dla dowolnego labiryntu opartego na siatce. Oprócz znajdowania ścieżek między dwoma lokalizacjami siatki (labiryntu), algorytm może wykrywać brak ścieżki między źródłem a celem. Ponadto algorytm ma być używany przez wewnętrznego podróżnika bez wcześniejszej wiedzy o labiryncie ze stałą złożonością pamięci, niezależnie od rozmiaru labiryntu; wymaga łącznie 4 zmiennych do znalezienia ścieżki i wykrycia nieosiągalnych lokalizacji. Niemniej jednak algorytm nie polega na znalezieniu najkrótszej ścieżki.

Algorytm wyznaczania trasy labiryntu wykorzystuje pojęcie odległości Manhattanu (MD) i opiera się na właściwości siatek, że MD zwiększa/zmniejsza się dokładnie o 1 podczas przemieszczania się z jednej lokalizacji do dowolnych 4 sąsiednich lokalizacji. Oto pseudokod bez możliwości wykrywania nieosiągalnych lokalizacji. 

  

    

    
           Źródło  punktu  ,  dst  ;  // Współrzędne źródłowe i docelowe  // cur wskazuje również współrzędne bieżącej lokalizacji  int  MD_best  =  MD  (  src  ,  dst  );  // Przechowuje najbliższą MD jaką kiedykolwiek mieliśmy dst  //  Ścieżka  produktywna to taka, która zmniejsza naszą MD do dst  while  (  cur  !=  dst  )  {  if  (  istnieje  ścieżka  produktywna  )  { 
           
      
           
              
                  
          Podążaj  produktywną  ścieżką  ;  _  }  else  {  MD_best  =  MD  (  kurs  ,  czas letni  );  Wyobraź  sobie  linię  między  cur  i  dst  ;  Wybierz  pierwszą  ścieżkę  po  lewej  /  prawej  stronie  linii  ;  _  _  _  // Wybór lewo/prawo wpływa na następującą regułę ręki,  podczas gdy  (  MD  (             
                
    
 cur  ,  dst  )  !=  MD_best  ||  nie  istnieje  produktywna  ścieżka  )  {  Kieruj  się  zasadą  prawej  /  lewej  ręki  ;  _  _  _  _  _  _  // Przeciwieństwo wybranej strony linii  }  }

Algorytm najkrótszej ścieżki

Dalsze informacje: Pathfinding § Algorytmy
Labirynt z wieloma rozwiązaniami i bez ślepych zaułków, w którym przydatne może być znalezienie najkrótszej ścieżki

Gdy labirynt ma wiele rozwiązań, osoba rozwiązująca może chcieć znaleźć najkrótszą ścieżkę od początku do końca. Istnieje kilka algorytmów znajdowania najkrótszych ścieżek, większość z nich pochodzi z teorii grafów . Jeden z takich algorytmów znajduje najkrótszą ścieżkę, wdrażając przeszukiwanie wszerz , podczas gdy inny, algorytm A* , wykorzystuje technikę heurystyczną . Algorytm przeszukiwania wszerz wykorzystuje kolejkę odwiedzać komórki w rosnącej kolejności odległości od startu do mety. Każda odwiedzana komórka musi śledzić swoją odległość od początku lub która sąsiednia komórka bliżej początku spowodowała dodanie jej do kolejki. Po znalezieniu lokalizacji końcowej podążaj ścieżką komórek wstecz do początku, która jest najkrótszą ścieżką. Przeszukiwanie wszerz w swojej najprostszej formie ma swoje ograniczenia, takie jak znajdowanie najkrótszej ścieżki na wykresach ważonych.

Zobacz też

Linki zewnętrzne

Pobrano z „ https://en.wikipedia.org/w/index.php?title=Maze-solve_algorithm&oldid=1139381524 ”