Algoritmul lui Lee reprezintă una dintre cele mai cunoscute aplicații ale cozii (ca structură de date) și este folosit de obicei pentru determinarea drumului minim dintre două celule ale unei matrice. Algoritmul lui Lee există mai mult în folclorul românesc; străinii îl consideră doar un breadth first search pe un caz particular de graf (matricea). Ei prin Algoritmul lui Lee se referă mai degrabă la un algoritm de înfășurătoare convexă. În acest articol voi prezenta Algoritmul lui Lee, cum se folosește în problema labirintului, precum și câteva aplicații ale acestuia.

Problema labirintului

Se dă un labirint sub forma unei matrice cu m linii și n coloane, unde dacă o celulă este 0, aceasta se consideră accesibilă de către șoarece, iar dacă este -1 inaccesibilă. De asemenea, se dau coordonatele pozițiilor în care se află inițial șoarecele și bucata de brânză.

La fiecare pas, șoarecele se poate deplasa într-una dintre pozițiile imediat vecine la nord, sud, est sau vest, cu condiția ca aceasta să fie accesibilă și, desigur, să se afle în interiorul matricei.

Să se determine lungimea minimă a unui drum de la șoarece la brânză, precum și un astfel drum. Dacă nu se poate ajunge la brânză (este înconjurată de obstacole), se va afișa 0.

Exemplu

Iată matricea corespunzătoare exemplului de mai jos. Am reprezentat cu violet pozițiile accesibile, cu negru pozițiile inaccesibile, cu roșu poziția șoarecelui, iar cu albastru poziția brânzei.

Exemplu de labirint (Algoritmul lui Lee)

Date de intrare

Date de ieșire

Algoritmul lui Lee

Vom utiliza o matrice mat, cea pe care o citim, și pe care o vom folosi de asemenea pentru a calcula niște rezultate parțiale despre care voi vorbi imediat. Avem nevoie și de o coadă q, cu elemente de tip Pos. Tipul Pos este un struct pentru reținerea coordonatelor celulelor din matrice. Acesta conține câmpurile lin și col, pentru linia și coloana poziției stocate.

  • În coada q se adaugă poziția șoarecelui.
  • Se completează această poziție din mat cu valoarea 1.
  • Cât timp coada nu este vidă și nici nu am găsit lungimea minimă:
    • Extragem primul element din coadă. Să-i zicem pos.
    • Îi parcurgem vecinii din matrice:
      • Dacă vecinul curent este accesibil și nevizitat:
        • Îl marcăm drept vizitat, completând celula sa corespunzătoare din mat cu valoarea mat[pos.lin][pos.col] + 1.
        • Îl introducem în coadă.
  • Afișăm valoarea din mat de pe poziția unde se află bucata de brânză.

Complexitatea algoritmului este $O(m \cdot n)$, deoarece fiecare celulă a matricei este vizitată maxim o singură dată. Această complexitate este extrem de bună, având în vedere dimensiunile input-ului.

Exemplu

Iată cum funcționează completarea matricei mat de mai sus prin Algoritmul lui Lee:Exemplu de labirint (Algoritmul lui Lee)

Explicația algoritmului

În timpul execuției algoritmului, în matricea mat, o poziție are valoarea -1 dacă este inaccesibilă, 0 dacă încă nu a fost vizitată, sau distanța minimă de la șoarece la ea altfel. Algoritmul lui Lee se bazează pe următoarea idee: Dacă știm lungimea drumului optim de la șoarece până la poziția accesibilă de coordonate i și j (mat[i][j]), putem actualiza lungimile drumurilor minime pentru vecinii accesibili (și nevizitați încă) ai ei; aceste valori vor fi egale cu mat[i][j] + 1, pentru că de la poziția (i, j) până la un vecin de-ai ei se mai face un singur pas. Asta e practic o relație de recurență, așa că Algoritmul lui Lee poate fi considerat un algoritm de programare dinamică.

Totuși, recurența asta nu e suficientă. Mai trebuie să ținem cont de ordinea în care completăm matricea mat. După ce am completat toate celulele din mat cu valoarea x (cele până la care se poate ajunge în minim x pași), trebuie să completăm lungimile minime pentru vecinii lor (cu x + 1), apoi pentru vecinii vecinilor lor (cu x + 2), și tot așa. Doar în acest fel putem fi siguri că toate rezultatele din mat sunt corecte. Completarea matricei poate fi asemănată cu modul în care o picătură de cerneală se extinde pe o bucată de hârtie.

Pentru a menține această ordine a completării matricei, se folosește o coadă, căci această structură de date funcționează pe principiul primul venit, primul servit. La fiecare pas, din coadă extragem primul element pentru a-l prelucra (a completa lungimile corespunzătoare vecinilor accesibili și a-i pune la sfârșitul cozii). Întotdeauna, o parte dintre pozițiile din coadă (primele) vor avea o anumită valoare, iar restul (vecinii lor) vor avea valoarea cu o unitate mai mare.

Găsirea unui drum optim

Acum că avem matricea mat completată, putem folosi soluțiile subproblemelor pentru construirea unui drum de lungime minimă de la șoarece (a) la brânză (b). Asta nu mai ține de Algoritmul lui Lee, dar n-are sens să scriu un alt articol pentru această cerință.

Secretul este să pornim de la brânză și să ne îndreptăm spre șoarece, nu invers, cum ar fi fost natural. Știm că dacă un vecin ngh (de la neighbourvecin în engleză) al celulei pos are valoarea mat[pos.lin][pos.col] - 1, atunci din ngh sigur se poate ajunge în pos (într-un singur pas). Cu alte cuvinte, sigur există un drum optim de la șoarece la pos care trece prin ngh. Dacă porneam de la șoarece n-am fi avut niciodată cum să știm dacă suntem pe drumul bun sau nu.

Exemplu de construire a unui drum optim

Folosind această idee, putem deduce un algoritm foarte simplu ce rezolvă această cerință. Inițializăm o stivă st cu poziția unde se află brânza. Căutăm un vecin al acestei celule, care respectă proprietatea de mai sus, și îl adăugăm în stivă. Apoi, repetăm procedeul pentru el. Facem asta până când ajungem la poziția șoarecelui. La final, extragem și afișăm, pe rând, pozițiile din stivă.

Din modul în care m-am exprimat este clar că problema se poate rezolva și recursiv, mai simplu. Dacă dimensiunile matricei sunt suficient de mici pentru a nu se produce stack overflow, prefer să folosesc această variantă:

Implementare în C++

Până la prezentarea celor două surse C++ propuse, trebuie să mai discutăm despre niște detalii legate de implementare.

Bordarea matricei

Bordarea matricei este o tehnică des folosită în problemele cu matrice. Aceasta presupune să înconjurăm (să „bordăm”) matricea propriu-zisă cu un anumit număr. Pentru ca bordarea să fie efectuată corect, trebuie să avem grijă la declararea dimensiunilor maxime ale matricei. Aceasta trebuie să fie declarată cu măcar două linii și coloane în plus. De asemenea, este necesar să poziționăm colțul din stânga-sus al matricei în (1, 1), pentru a lăsa loc bordurii să treacă prin (0, 0).

Putem folosi ideea asta și în problema noastră. Ca să verificăm dacă poziția pos se află în interiorul matricei propriu-zise, ar trebui să efectuăm de fiecare dată acest test enervant:

Pe lângă faptul că face codul mai complicat, nici nu este eficient, pentru că s-ar executa de foarte multe ori. Însă, putem borda inițial matricea cu valoarea -1, ca și cum ar fi înconjurată de obstacole. Astfel, nu vom ieși niciodată din matrice, pentru că asta ar însemna să ne expandăm în celule inaccesibile.

Exemplu de bordare a matricei

Iată implementarea scurtă și simplă a bordării matricei mat:

Vectorii de deplasare

Ar fi aiurea să parcurgem vecinii unei poziții ca mai jos, pentru că am scrie de patru ori aceleași operații:

Ar fi frumos să putem parcurge vecinii cu un for. Ei bine, putem face asta dacă declarăm mai întâi vectorii de deplasare:

Acești vectori conțin pe poziția i niște valori, care adunate la coordonatele celulei curente, conduc la obținerea coordonatelor celui de-al i-lea vecin al ei:

Coordonatele vecinilor

Nu avem decât să ne folosim de acești vectori pentru a inițializa o variabilă ngh, ce reține coordonatele vecinului curent, pe care să o folosim în continuare.

Iată cum arată coordonatele vecinilor lui pos în cazul în care deplasarea se făcea cu o unitate pe 8 direcții, precum și în cazul în care deplasarea se făcea similar cu cea a calului de pe o tablă de șah:

Exemple vectori de deplasare

Sursa clasică

Prima sursă este cea clasică, ce folosește o coadă implementată sub forma unui vector static și găsește drumul optim iterativ:

Sursa cu STL

A doua sursă folosește STL pentru coadă și construiește drumul recursiv:

Aplicații ale algoritmului

În această problemă, ne-am putut opri din completarea matricei după ce am ajuns la brânză. Adesea însă, este util să lăsăm algoritmul să ruleze până se umple toată matricea. Iată ideile de rezolvare a trei probleme de pe .campion și InfoArena cu Algoritmul lui Lee:

  • rj. Facem două Lee-uri: unul din poziția lui Romeo și unul din poziția Julietei. Apoi, parcurgem simultan cele două matrice obținute. Când găsim o poziție pentru care valorile din ambele matrice sunt egale, înseamnă că cei doi pot ajunge acolo simultan. Mai rămâne să determinăm o astfel de poziție cu valoare minimă, pentru că numărul de pași trebuie să fie minim.
  • soricel3. Pentru calcularea gradelor de periculozitate din întreaga matrice, inițializăm punctele de pândă cu m + nLe introducem pe toate în coadă, și începem Lee-ul, expandându-ne simultan din toate punctele de pândă. Valorile vor scădea din 1 în 1, în loc să crească. Pentru determinarea drumului minim, vom înlocui coada din Lee-ul clasic cu o coadă de priorități. La fiecare pas, vom extrage cel mai mic element din coadă, pentru că dorim să ne extindem mai întâi în zone cât mai sigure. În plus, rezultatele subproblemelor vor fi gradele de periculozitate ale drumurilor, nu lungimile lor. Tehnica aceasta se numește Algoritmul lui Lee cu costuri. Este asemănător cu Algoritmul lui Dijkstra, doar că graful (matricea) are costuri pe noduri, nu pe muchii.
  • rover. Prima cerință este tot o variație a algoritmului lui Lee. De data aceasta, coada se înlocuiește cu un deque. Am explicat pe larg cum se rezolvă problema asta în acest articol.

Asta e tot ce am avut de spus despre Algoritmul lui Lee și problema labirintului. Dacă aveți vreo întrebare despre Algoritmul lui Lee, sau nu ați înțeles vreun detaliu din acest articol, nu ezitați să lăsați un comentariu mai jos 🙂

Îți place conținutul acestui site?

Dacă vrei să mă susții în întreținerea server-ului și în a scrie mai multe articole de calitate pe acest blog, mă poți ajuta printr-o mică donație. Află aici cum o poți face!