Algorytm Lee

Wstęp

Algorytm Lee pozwala na znalezienie najkrótszej ścieżki pomiędzy punktem początkowym, a końcowym. Wszelkie przeszkody o ile to możliwe potrafi pokonać, ale wymaga to bardzo dużej ilości pamięci i czasu. Z tego względu jego implementację ciężko znaleźć np. w grach komputerowych. Jest to jednak algorytm, który pozwala rozpocząć naukę dotyczącą szukania drogi pomiędzy dwoma punktami.

Algorytm

Zgodnie z algorytmem szukanie ścieżki odbywa się na planszy o kwadratowych polach. Dopuszczalne są kroki: góra, prawo, dół i lewo. W rezultacie można otrzymać ścieżkę, którą należy przejść oraz odległość jak daleko znajduje się punkt końcowy od początkowego.

Początkowo algorytm zaczyna działanie wychodząc z punktu startowego. Przyjmijmy, że na początku każdej iteracji program otrzymuje pewną listę punktów. Następnie dla każdego z tych punktów oznacza dopuszczalne kroki w każdym prawidłowym kierunku. Prawidłowy kierunek to taki, który nie prowadzi na pole z przeszkodą, albo na pole już odwiedzone. Każdy z oznaczonych punktów należy dodać na nową listę. Po zakończeniu oznaczania i przejściu do nowej iteracji za listę należy przyjąć liste punktów oznaczonych w poprzedniej iteracji. Algorytm kończy działanie, gdy pole końcowe zostanie oznaczone.

Warto jednak zauważyć, że taki algorytm sprawdza wszystkie możliwe przypadki. Jego warunkiem stopu będzie moment, gdy lista punktów oznaczonych w poprzedniej iteracji będzie pusta. Wtedy poszukiwanie drogi kończy się niepowodzeniem i należy zwrócić taką odpowiedź.

Przykład

Bez przeszkód

W poniższej tabeli znajdują się punkt początkowy S oraz punkt końcowy K. Przedstawione zostały kolejne etapy iteracji przechodzenia z punktu S do k. W każdej iteracji punkty od których były symulowane wszystkie możliwe kroki w danej iteracji zostały wyszczególnione niebieskim kolorem.

Z ostatniego schematu można odczytać, że podróż zajmuje dokładnie 4 kroki.

Z przeszkodami

Tym razem na drodze algorytmu ustawmy przeszkody oznaczone █.

Tym razem najkrótsza droga wynosi 7. Warto zwrócić uwagę na fakt, że w Iteracji 6 poszukiwania zostały rozdzielone w dwóch kierunkach. Gdyby plansza została jeszcze rozszerzona w prawo lub lewo to tam również zostałyby oznaczone pola o wartości 6, a może nawet 7 (zależy czy punkt końcowy zostałby znaleziony jako pierwszy w 7 iteracji).

Implementacja

Poniższy program jest realizacją algorytmu Lee w celu znalezienia pomiędzy punktami. Zakłada on poprawność danych wejściowych. Po działaniu programu mapa będzie przedstawiać taki sam schemat jak wyżej zamieszczone iteracje.

Założenia

Trzymanie współrzędnych w oddzielnych zmiennych może prowadzić do popełniania błędu, więc zostanie wykorzystana struktura pair, która z kolei będzie reprezentowana przez alias para.

1. typedef pair<int, int> para;

Informacje o mapie będą przechowywane w dwuwymiarowej tablicy liczb. Wszystkie pola na które można wykonać krok będą miały wartość 0, przeszkody -1, a punkt początkowy -2.

Szukanie połączenia

Do szukania połączenie służy funkcja szukajPolaczenia(), która przyjmuje kolejno: mapa - mapę obszaru, w i h tj. szerokość i wysokość mapy oraz punkty start i koniec. Funkcja przedstawia sie następująco:

1. int szukajPolaczenia(int** mapa, int w, int h, para start, para koniec) {
2.   vector<para> v;
3.   int i = 0;
4.   v.push_back(start);
5.   while (mapa[koniec.first][koniec.second] == 0) {
6.     i++;
7.     vector<para> vnowy;
8.     for each (para p in v) {
9.       zmien(mapa, w, h, p.first - 1, p.second, i, vnowy);
10.       zmien(mapa, w, h, p.first + 1, p.second, i, vnowy);
11.       zmien(mapa, w, h, p.first, p.second - 1, i, vnowy);
12.       zmien(mapa, w, h, p.first, p.second + 1, i, vnowy);
13.     }
14.     if (vnowy.size() == 0)
15.       return -1;
16.     v = vnowy;
17.   }
18.   return i;
19. }

(2.) Utworzenie listy pól oraz (3.) określenie aktualnego numeru kroku. (4.) Początkowo na liście oznaczonych pól znajduje się tylko pole startowe. (5.) Dopóki pole końcowe nie zostanie odwiedzone: (6.) wykonaj krok i (7. - 12.) dla każdego pola spróbuj wykonać krok w każdą stronę. (13. - 14.) Jeśli nowa lista pól oznaczonych jest pusta to zwróć, że nie ma rozwiązania (wartość -1). W przeciwnym razie kontynuuj działanie i (15.) przyjmij nową listę pól zamiast starej.

Zamiana pola

W tym przypadku funkcją pomocniczą jest funkcja zmien(), która przyjmuje bardzo dużo argumentów: mapa - mapę obszaru, w i h tj. szerokość i wysokość mapy, y i x - współrzędne wykonania kroku, i - aktualny numer kroku oraz vnowy - lista oznaczonych pól w tej iteracji.

1. void zmien(int** mapa, int w, int h, int y, int x, int i, vector<para>& vnowy) {
2.   if (x < 0 || x >= w || y < 0 || y >= h || mapa[y][x] != 0)
3.     return;
4.   mapa[y][x] = i;
5.   vnowy.push_back(make_pair(y, x));
6. }

(2.) Jej zadanie sprowadza się do sprawdzenia czy pole na który wykonany został krok jest prawidłowe oraz czy można tam wykonać krok. Jeśli krok jest prawidłowy to (4.) na mapie zapisana zostaje wartość i oraz (5.) oznaczony punkt trafia na listę vnowy, aby go rozpatrzeć w kolejnej iteracji.

Testowanie funkcji

W celu przetestowania działania funkcji można skorzystać z poniższej funkcji main():

1. int main() {
2.   int w, h;
3.   cout << "Podaj szerokosc mapy w = ";
4.   cin >> w;
5.   cout << "Podaj wysokosc mapy h = ";
6.   cin >> h;
7.   cout << "Podaj wzor mapy:";
8.   int** mapa = new int*[h];
9.   char t;
10.   para start, koniec;
11.   for (int i = 0; i < h; i++) {
12.     mapa[i] = new int[w];
13.     for (int j = 0; j < w; j++) {
14.       cin >> t;
15.       switch (t) {
16.       case 'x':
17.         mapa[i][j] = -1; break;
18.       case 's':
19.         mapa[i][j] = -2;
20.         start = make_pair(i, j); break;
21.       case 'k':
22.         mapa[i][j] = 0;
23.         koniec = make_pair(i, j); break;
24.       default:
25.         mapa[i][j] = 0; break;
26.       }
27.     }
28.   }
29.   cout << szukajPolaczenia(mapa, w, h, start, koniec) << endl;
30.   for (int i = 0; i < h; i++) {
31.     for (int j = 0; j < w; j++) {
32.       switch (mapa[i][j]) {
33.         case -2: cout << "S"; break;
34.         case -1: cout << "#"; break;
35.         default: cout << mapa[i][j]; break;
36.       }
37.       if (make_pair(i, j) == koniec)
38.         cout << "*";
39.       cout << "\t";
40.     }
41.     cout << endl;
42.   }
43.   for (int i = 0; i < h; i++)
44.     delete mapa[i];
45.   delete mapa;
46.   system("pause");
47.   return 0;
48. }

Wczytuje ona od użytkownika rozmiar mapy, a następnie jej schemat. Na podstawie danych wejściowych wylicza ona najkrótszą drogę pomiędzy punktami oraz pokazuje jak wygląda mapa wszystkich iteracji.

Dane wejściowe

Rozmiar i szerokość mapy to dowolne liczby całkowite. Obraz mapy może składać się z x - przeszkoda, s - punkt początkowy (maksymalnie jeden) oraz k - punkt końcowy (maksymalnie jeden). Każdy pozostały znak traktowany jest jako pole na które można stanąć. Przykładowo oznaczając wolne pole kropką prawidłową mapą będzie:

1. s..x..k
2. .xxx...
3. .x.....
4. .......

Gdzie jej wysokość to 4, a szerokość 7.

Wynik

W rezultacie program zwróci następującą mapę i określi odległość punktu startowego od końcowego.

1. Odleglosc wynosi: 12
2. S   1   2   #   10  11  12*
3. 1   #   #   #   9   10  11
4. 2   #   6   7   8   9   10
5. 3   4   5   6   7   8   9

• Kod źródłowy Implementacja

Zadania

Zadanie 1

Napisz program, który po otrzymaniu wyniku narysuje na ekranie jedynie ścieżkę jaką należy przejść z punktu początkowego do końcowego. Pola z przeszkodami oznacz "#", a pola wolne kropkami ".". Pola, którymi należy przejść oznacz gwiazdkami "*". Program powinien znajdować dowolną prawidłową ścieżkę:

1. Odleglosc wynosi: 12
2. S..#**K
3. *###*..
4. *#..*..
5. *****..

• Kod źródłowy Zadanie 1