Algoritmul lui Lee
- Ce este si ce face acest algoritm?
Ei bine, algoritmul lui Lee este un algoritm ce determina numarul minim de pasi, pentru a ajunge din punctul x in punctul y in anumite conditii (de exemplu: evitand obstacole). De-asemenea cu acest algoritm se face introducerea unei noi structuri in informatica: coada (sau queue). Acest algoritm nu se face la clasa deoarece este foarte greu de predat, iar explicarea modului de functionare este destul de dificila. Acest algoritm este foarte util pentru cei ce se afla in clasa 10 si doresc sa participe la olimpiada judeteana de informatica, deoarece este unul din algoritmii prioritari ce trebuie stiuti (un alt algoritm prioritar ar mai fi algoritmul de fill, dar despre el vom vorbii intr-un episod viitor). Inainte de a ne apuca sa implementam acest algoritm, vreau sa va spun ca trebuie sa aveti cateva cunostiinte de baza in limbajul C++.
- Prezentarea generala
Algoritmul lui Lee este defapt o parcurgere in latime (BFS) a unui graf, doar ca aplicat pentru o grila. Stati linistiti, o sa aflati in clasa 11 ce este aia BFS (sau intr-unul din videourile mele, mai tarziu). Este un algoritm destul de eficient, avand complexitatea de O(M*N), fiind foarte utilizat in problemele in care apare un labirint.
- Problema alee
Vom incepe sa prezentam acest algoritm, citind o problema “alee” (care defapt este prescurtarea de la a – algoritm si lee – Lee) de pe platforma infoarena.ro. Daca nu aveti un cont pe infoarena, va trebuii sa va creati unul. Problema poate fi accesata de pe link-ul http://www.infoarena.ro/problema/alee .
- Vectorii de deplasare
In primul si primul rand, inainte de a incepe sa scriem acest algoritm, va trebui sa ne dam seama cum realizam deplasarea, in cele 4 sau in cele 8 directii ale axei?.. Dar pentru ca in problema se mentioneaza la “Aleea este continua daca oricare doua placi consecutive au o latura comuna.”, putem deduce ca deplasarea are loc pe cele 4 directii. Asa ca vom declara doi vectori, primul vector fiind directia pe axa Ox, iar cel de-al doilea directia pe axa Oy.
Acum vine partea care necesita o atentie mai deosebita, vom codifica cele 4 puncte cardiale in 0 1 si -1. Astfel, dupa cum urmeaza, avem nordul (0,1), sudul (0,-1), vestul (1,0) si estul (-1,0). Astfel avem liniile
int di[4] = {1,0,-1,0};
int dj[4] = {0,1,0,-1};
- Citirea valorilor din problema
Acum vom trece la citirea valorilor si initializarea problemei. Astfel incat vom avea N, latimea si lungimea parcului, M – numarul de obstacole, iar mai apoi citim obstacolele si coordonatele de pornire si oprire.
- Variabila pair
Pair este o variabila ceva mai deosebita, iti permite sa retii doua valori simultan, ceea este perfect pentru problema noastra, deoarece putem retine coordonata x si coordonata y in aceeasi variabila. Pentru a va arata un exemplu concret, vom memora punctul P. Il vom declara
pair < int, int > P;
Iar pentru a introduce valori, scriem:
P = make_pair(1,5);
Iar pentru a afisa: unde .first reprezinta primul numar (adica 1) iar second al doilea numar (5).
cout << P.first << “ “ << P.second;
- Clasa queue
Mai departe, pentru rezolvarea acestei probleme ne vom folosii de un include foarte util in rezolvarea tuturor problemelor, un include care introduce un nou tip de variabila, o variabila cunoscuta la scoala sub numele de “coada”. Aceasta coada functioneaza pe principiul “primul venit – primul servit” – exact ca o coada de la farmacie. Incepem prin a scrie header-ul
#include <queue>
Si vom analiza urmatoare secventa de cod.
queue < int > Q; Q.push(1); Q.push(15); Q.push(25); Q.push(62); cout << Q.front(); Q.pop(); cout << Q.front();
- Functia OK
Iar ultimul detaliu inainte de a trece la implementarea efectiva a algoritmului. Vom scrie o functie de tip bool care va verifica daca se poate trece la un nou punct de pe harta sau nu.
bool OK(int i, int j)
{
if (i < 1 || j < 1 || i > N || j > N)
return false;
if (parc[i][j] == -1)
return false;
return true;
}
- Algoritmul lui Lee
Inainte de a trece la implementarea efectiva a algoritmului, va trebuii sa urmariti urmatoarea animatie. O prima observatie este faptul ca algoritmul nostru nu se opreste decat atunci cand a aflat cea mai mica distanta pornind din punctul nostru la toate celalalte puncte, de unde putem concluziona faptul ca acesta se executa pana nu mai are puncte, iar rezultatul final (adica numarul minim de pasi) se va afla in coordonata i si j a punctului de oprire din matrice.
- Vom incepe prin a marca punctul din matrice cu “1” si sa il introducem in queue.
- Iar acum, vine cea mai importanta parte a algoritmului, vine algoritmul in sine. Vom pune cei 4 vecini ai punctului curent in queue (coada), si ii vom marca cu +1 (deoarece distanta se mareste cu o unitate)
