Wikipedysta:Lethern/Sztuczna inteligencja/Szukanie drogi - podstawa

Najkrótsza ścieżka

Najkrótsza ścieżka jest drogą łączącą dwa zadane punkty o najkrótszej możliwej długości. Rozważanym problemem będzie znalezienie owej najkrótszej ścieżki dla danych dwóch punktów na pewnym obszarze, zakładając, że składa się on z pól (pustych lub zajętych).

Z reguły najprostszym, znajdującym zawsze prawidłową odpowiedź, choć jednocześnie najwolniejszym algorytmem, jest symulowanie i analizowanie wszystkich możliwości. W tym przypadku, sprawdzenie wszystkich możliwych dróg.

Sposób ten jest jedynie punktem wyjścia, ponieważ szybkość działania takiego algorytmu jest nie do przyjęcia. Będziemy szukać metody na redukcję ilości dróg, jakie powinny nas interesować.

Przyspieszenie osiągniemy, jeśli postaramy się nie przeglądać dróg dłuższych niż nasza droga do celu, a jest to możliwe. Zacznijmy od przykładu: jeżeli cel jest oddalony od punktu startowego o np. 10 pól, wystarczy nam przejrzeć wszystkie drogi o długości 10. Nie mamy oczywiście danej długości najkrótszej drogi, ale skorzystamy z tego pomysłu. Zastosujemy pewną metodę: sprawdzimy wszystkie drogi o długości 1, następnie wszystkie drogi o długości 2, ciągle zwiększając długość. Wracając do przykładu, algorytm w pewnym momencie będzie analizował wszystkie drogi o długości 10, wówczas też trafi na poszukiwaną ścieżkę, która prowadzi do naszego końcowego pola, na czym zakończymy działanie algorytmu. Dzięki temu, pominiemy wszystkie drogi mające długości 11, 12 itd. Nie trzeba się zastanawiać, czy znajdujemy na pewno najkrótszą drogę, ponieważ sprawdzamy wszystkie odcinki zaczynając od najkrótszego, więc jedynie najkrótszy odcinek połączy nas z celem. Pomijamy więc jedynie te odcinki, które rozwiązaniem na pewno nie będą, co może nam przynieść spore przyspieszenie.

Sposób przeszukiwania ścieżek

Ponieważ przeszukujemy odcinki o coraz większych długościach, możemy generować nowy wynik posługując się poprzednimi obliczeniami. Tak więc, odcinki o długości 6 wygenerujemy wyłącznie z odcinków o długości 5. Powiększamy długość o 1, czyli dodajemy jedno pole - sąsiednie pole. Wystarczy nam więc tylko ostatnie pole, z którego będziemy mogli 'sięgać' do jego sąsiadów, a z nich do kolejnych itd.

Wykorzystamy ten fakt również w zapamiętywaniu przebiegu drogi. Ponieważ mając punkt końcowy pewnej drogi możemy wygenerować wszystkie jej rozszerzenia, tzn. ścieżki dłuższe o 1 pole, ograniczymy się właśnie do wykorzystania tych 'końcowych punktów'. Jeśli spróbujemy nakreślić je na planszy, w pierwszym kroku będą to pola wokół pola startowego (droga o długości 1), w następnym pola wokół nich, i tak dalej. Będzie to swego rodzaju 'pierścień' (uginający się na przeszkodach terenu) pól, które aktualnie są rozpatrywane przez algorytm. Figura ta będzie się po prostu 'rozszerzać', z czasem działania programu.

Możemy więc dla każdego takiego pola zapamiętać długość ścieżki, będzie to jedyna informacja opisująca drogę. Z punktu tego stworzymy wszystkie rozgałęzienia ścieżki, dłuższe o 1. Jeśli umieścimy te długości w tablicy, otrzymamy właśnie 'pierścienie' liczb, rosnących w miarę oddalania się od środka. Jesteśmy w stanie zapisać wszystkie drogi o danej długości, jednak jak wyznaczyć z tego drogę łączącą punkt środkowy i dowolny dany punkt? Nie jest to problem, wystarczy spostrzec, że choć z punktu początkowego rozchodzi się masa rozgałęzień, tak nasz konkretny końcowy punkt jest połączony jednym 'promieniem' z początkiem. Gdybyśmy stali na owym końcowym polu, widzielibyśmy, że wracając po malejących polach, doszlibyśmy do pola startowego, tak właśnie trzeba uczynić. Na drogę składają się więc pola z kolejnymi malejącymi liczbami.

Nie jest to poprawna kolejność - poruszanie się od końca do początku, dlatego musimy to odwrócić. Oczywiście, nie jest problemem uruchomić algorytm "na polu końcowym", aby rozszerzył swój pierścień poszukiwań do pola startowego, z którego wystarczy już tylko iść za kolejnymi zmniejszającymi się liczbami pól do celu.

Podsumowanie

Problemem jest znalezienie najkrótszej drogi między jednym a drugim polem. Ideą algorytmu jest przeszukiwanie rozszerzającego się obszaru, tzn. w coraz większym promieniu od pola pierwszego, aż w obszar ten 'wpadnie' pole drugie. Na owy obszar składa się grupa pól, które znajdują się w tej samej odległości od początkowego pola. Długości te są zapisywane w polach. Gdy osiągnie się drugie pole, będące w odległości np. 20, wystarczy znaleźć sąsiednie pole w odległości 19, po czym z niego pole w odległości 18, aż dojdzie się do pola pierwszego. Przejdziemy tym samym drogę długości 20, jest to najkrótsza droga, ponieważ wiemy, że żadna krótsza droga nie zdołała połączyć obu punktów.

Algorytm korzysta z tablicy wielkości przeszukiwanego terenu. W polu tablicy zapisywana jest długość ścieżki. (dana komórka tablicy = długość ścieżki danego pola, oczywiście pole o współrzędnych x y jest zapisane w tablicy też pod wsp. x y)

Algorytm

Na początku inicjujemy tablicę, zapisując pod każdym polem wartość nieskończoność (ma symbolizować, że droga jest nieskończenie długa = nie istnieje). W implementacji - musi to być oczywiście wartość większa niż długość najdłuższej możliwej drogi.

ustaw wszystkie komórki tablicy na nieskończoność

Program zaczynamy od analizy pola końcowego (tzn. szukamy drogi od niego do pola początkowego), ustawiamy w tablicy dla tego pola wartość 0 (ponieważ droga prowadzi do samego pola). Wykonujemy procedurę dla jego sąsiadów (rekurencyjnie lub iteracyjnie, przy użyciu stosu), przekazując współrzędne owego sąsiada i długość utworzonej z tym polem drogi (tzn. zwiększoną o 1), czyli 1. Procedura będzie się wykonywać póki nie trafi się na Pole Początkowe (co jest notowane w zmiennej Pole Znalezione). Podane zostaną obie możliwości implementacji - rekurencyjna i, jako dodatkowe linijki, iteracyjna.

zmienna Pole Znalezione - ustaw wartość Fałsz
komórka o współrzędnych pola końcowego - ustaw wartość 0
wykonaj procedurę (współrzędne Pola Końcowego, długość 1)
/iteracyjnie:/ dodaj na stos (współrzędne Pola Końcowego, długość 1)
/iteracyjnie:/ wykonuj procedurę dla elementów ze stosu

Procedura (przyjmuje współrzędne pola i długość drogi):

Jeżeli nie znaleziono szukanego Początkowego Pola, to:

Dla podanego pola zapisujemy długość drogi.

Następnie wykonujemy procedurę dla sąsiadów, przekazując długość drogi+1.

Uwaga - nie wykonujemy procedury dla sąsiadów, których długość drogi zapisana w tablicy jest krótsza, czyli dla pól odwiedzonych wcześniej (długość musi być dłuższa niż pobrana długość +1).

Uwaga2 - jeśli sąsiednie pole jest Początkowym Polem, którego szukamy, kończymy działanie i odnotowujemy ten fakt.

procedura (współrzędne Pola, Długość drogi)
jeżeli zmienna Pole Znalezione ma wartość Fałsz, kontynuuj
komórka o współrzędnych pobranego Pola - ustaw wartość Długość
dla każdego sąsiada Pola:
  jeżeli sąsiadem jest Pole Początkowe, Pole Znalezione = Prawda, skończ działanie.
  jeżeli komórka o współrzędnych sąsiada ma długość większą niż Długość+1, to
     wykonaj procedurę (współrzędne sąsiada, Długość+1)
     /iteracyjnie:/ dodaj na stos (współrzędne sąsiada, Długość+1)

Wykonywanie procedury skończy się w momencie, gdy trafi się na pewne pole, którego sąsiadem jest Pole Początkowe. W tym momencie bierzemy je 'na warsztat' i sporządzamy ścieżkę do Pola Końcowego. Szukamy wśród naszych sąsiadów pola o najmniejszej odległości, zapisujemy je w ścieżce. Kontynuując od niego już, powtarzamy: szukamy sąsiada o mniejszej odległości, zapisujemy w ścieżce i 'przechodzimy' do niego. Kończymy, gdy do ścieżki dodamy pole Końcowe.

ustaw Długość drogi =nieskończoność, ustaw Współrzędne =nieokreślone
stwórz pustą kolejkę Ścieżka, która będzie zbiorem pól szukanej drogi
dla każdego sąsiada Pola Początkowego:
   jeżeli komórka tablicy o wsp. sąsiada ma mniejszą wartość niż Długość, to
       zapamiętaj pod Współrzędnymi i Długością dane sąsiada
powtarzaj:
   dla każdego sąsiada pola W (określonego Współrzędnymi)
       jeżeli komórka tablicy dla sąsiada jest równa Długość-1, to 
           zapisz pod Współrzędne i Długość dane sąsiada
           oraz dodaj nowe pole (Współrzędne) do kolejki Ścieżka
       (uwaga, zmieniły się Współrzędne, przeszukiwani są sąsiedzi nowego pola)
powtarzaj dopóki Długość jest większa niż 0

kolejne pola w kolejce Ścieżka są kolejnymi polami najkrótszej drogi