Revizia anterioară Revizia următoare
Algoritmul lui Lee
(Categoria Algoritmi, Autor Simoiu Robert)
- Conţinut
- Sectiunea 1
- Sectiunea 2
- Sectiunea 3
Introducere
În continuare vom prezenta algoritmul lui Lee, pentru cei care nu ştiu este parcurgerea în lăţime. Acest algoritm este de fapt o particularizare a algoritmului menţionat mai sus, şi anume parcurgere în lăţime. Este eficient, având o complexitate de O(M*N), şi frecvent utilizat. Acesta determină drumul minim de ieşire dintr-un labirint, sau în probleme asemănătoare.
Prezentare
Algoritmul lui Lee presupune doi paşi importanţi:
- Primul şi poate cel mai important pas este folosirea unei Cozi, sub forma unui vector de structuri (de preferabil), care va menţine toţi paşii pe care o să-i facem de acum în colo.
- Se marchează cu numere consecutive toate locurile posibile prin care putem trece, mergând din coadă în coadă, până când nu mai putem marca, sau am ajuns la final. În coadă vom băga toate locurile pe care le marcăm, verificând pentru fiecare în parte, la rândul lor, locurile pe care le putem marca.
Aplicaţie -> Problema Labirintului
Se dă o matrice cu M linii şi N coloane. Ştiind locul de plecare, se cere să se determine drumul de lungime minimă până la o ieşire, iar in caz că nu există, se va afişa -1
Rezolvare
După cum observaţi, este o aplicaţie a algoritmului lui Lee. Această problemă se poate rezolva şi cu metoda backtracking, dar această metodă nu este una eficientă, complexitatea fiind O(4(M*N)), sau O(3(M*N)) după caz, ceea ce este foarte mult.
