Revizia anterioară Revizia următoare
Algoritmul lui Lee
(Categoria Algoritmi, Autor Simoiu Robert)
- Conţinut:
- Introducere
- Prezentare
- Aplicaţie
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 parcurgerii î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. În această coadă se pun, pentru fiecare pas, locurile care s-au marcat la punctul anterior.
- Se marchează cu numere consecutive toate locurile posibile prin care putem trece, parcurgând în ordine elementele cozii, până când nu mai putem marca, sau am ajuns la final.
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.
