Parcurgerea in latime – Lee

Parcurgerea in latime este cunoscuta si ca algoritmul lui Lee in lumea algoritmicii romanesti sau BFS (Breath First Search) in lumea grafurilor este la baza un algoritm de cautare ce sunt folositi in general pentru a afla drumul de lungime minima intre doua noduri.

Prezentarea algoritmului

Algoritmul are la baza o metoda iterativa. Fiecare vecin va fi bagat, iar la extragerea unuia din coada vom baga in coada toti vecinii nevizitati ai nodului curent (avand grija sa eliminam nodul curent). Algoritmul se repeta pana cand coada devine vida sau gasim solutia asteptata.

Implementare in pseudocod

intreg m[100][100];
coada c;
functie bfs(nod p)
{
   adaug_in_coada(p);
   m[k.x][k.y]=1; //vizitez nodul
   pentru(i=0;i< =n+1;i++) m[i][0]=m[i][m+1]=1; //bordam coloanele marginale
   pentru(i=0;i<=m+1;i++) m[0][i]=m[n+1][i]=1; //bordam liniile marginale
   cat_timp(c <> NULL)
   {
      k = scot_din_coada(c);
      pentru_fiecare_nod(vecin din k)
      {
          daca(m[vecin.x][vecin.y]==0) //daca vecinul e nevizitat
          { 
              m[vecin.x][vecin.y]=1; //il vizitez
              adaug_in_coada(vecin);
          }
      }
      sterg_din_coada(k);
   }
}

Aplicatii

1. Problema alee de pe .campion

Parcul orasului a fost neglijat mult timp, astfel ca acum toate aleile sunt distruse. Prin urmare, anul acesta Primaria si-a propus sa faca reamenajari.
Parcul are forma unui patrat cu latura de n metri si este inconjurat de un gard care are exact doua porti. Proiectantii de la Primarie au realizat o harta a parcului si au trasat pe harta un caroiaj care imparte parcul in nxn zone patrate cu latura de 1 metru. Astfel harta parcului are aspectul unei matrice patratice cu n linii si n coloane. Liniile si respectiv coloanele sunt numerotate de la 1 la n. Elementele matricei corespund zonelor patrate de latura 1 metru. O astfel de zona poate sa contina un copac sau este libera.
Edilii orasului doresc sa paveze cu un numar minim de dale patrate cu latura de 1 metru zonele libere (fara copaci) ale parcului, astfel incat sa se obtina o alee continua de la o poarta la alta.
Solutie
Rezolvarea acestei probleme este o aplicatie clara a algoritmului BFS pe matrici.

2. Problema RJ de pe .campion

In ultima ecranizare a celebrei piese shakespeariene Romeo si Julieta traiesc intr-un oras modern, comunica prin e-mail si chiar invata sa programeze. Intr-o secventa tulburatoare sunt prezentate framantarile interioare ale celor doi eroi incercand fara succes sa scrie un program care sa determine un punct optim de intalnire.
Ei au analizat harta orasului si au reprezentat-o sub forma unei matrice cu n linii si m coloane, in matrice fiind marcate cu spatiu zonele prin care se poate trece (strazi lipsite de pericole) si cu X zonele prin care nu se poate trece. De asemenea, in matrice au marcat cu R locul in care se afla locuinta lui Romeo, iar cu J locul in care se afla locuinta Julietei.
Ei se pot deplasa numai prin zonele care sunt marcate cu spatiu, din pozitia curenta in oricare dintre cele 8 pozitii invecinate (pe orizontala, verticala sau diagonale).
Cum lui Romeo nu ii place sa astepte si nici sa se lase asteptat n-ar fi tocmai bine, ei au hotarat ca trebuie sa aleaga un punct de intalnire in care atat Romeo, cat si Julieta sa poata ajunge in acelasi timp, plecand de acasa. Fiindca la intalniri amandoi vin intr-un suflet, ei estimeaza timpul necesar pentru a ajunge la intalnire prin numarul de elemente din matrice care constituie drumul cel mai scurt de acasa pana la punctul de. intalnire. Åži cum probabil exista mai multe puncte de intalnire posibile, ei vor sa il aleaga pe cel in care timpul necesar pentru a ajunge la punctul de intalnire este minim.
Solutie
O aplicatie foarte interesanta, ideea cea mai buna este de a face BF pornind atat din directia lui Romeo cat si din cea a Julietei. Pentru a obtine solutia minima, vom cauta solutia cea mai buna ce coincide celor doua matrici „vizitate” create de BFS.

3. Problema sotron1 de pe .campion

Ana si Bogdan au inventat un nou model de sotron. Ei deseneaza cu creta pe asfalt un caroiaj format din NxM patrate organizate in N linii si M coloane. O parte dintre aceste patrate le coloreaza in rosu, celelalte in verde. In plus, un patrat este selectat ca patrat de start si un alt patrat ca patrat de final (acestea sunt verzi).
Scopul jocului este ca jucatorul sa ajunga de la patratul de start la patratul final in cel mai scurt timp. Regulile jocului sunt:

1. este interzis ca jucatorul sa paseasca intr-un patrat rosu; este permis sa se deplaseze doar in cele verzi;
2. atunci cand jucatorul ajunge intr-un patrat el se poate deplasa in patratul din fata sa, in cel din stanga sa sau in cel din dreapta sa (fata, stanga, dreapta sunt stabilite evident in functie de sensul de mers); prin urmare este interzis ca un jucator sa se deplaseze inapoi sau in diagonala; de asemenea este interzis ca jucatorul sa paraseasca caroiajul;
3. de-a lungul intregului drum de la start la final sunt permise in total cel mult K deplasari la dreapta;
4. initial, cand jucatorul este plasat in patratul de start, el poate alege ce sens de deplasare doreste;
5. deplasarea de la un patrat la altul dureaza o secunda.
Solutie
Vom aplica algoritmul lui Lee, adaptat restrictiilor din enunt. Vom utiliza o coada in care vom introduce pozitiile de joc:
Cat timp coada nu este vida:
– extrag o pozitie din coada
– verific vecinii pozitiei extrase si daca este posibil (repsecta conditiile) ii introduc in coada.
Cum se realizeaza verificarea vecinilor? In primul rand trebuie sa verificam ca pozitia urmatoare este pe tabla de joc.

Apoi ca acea pozitie nu mai fost vizitata. In acest scop vom utiliza un tablou uz cu 4 dimensiuni : uz[i][j][d][r]= 1 daca am ajuns pe linia i, coloana j deplasandu-ne in directia d, avand r deplasari dreapta disponibile.

Alte aplicatii

http://campion.edu.ro/arhiva/index.php?page=keyword&action=view&id=26