Căutare în lățime

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare
Exemplu animat de căutare în lățime

Căutarea (parcurgerea) în lățime (BFS) este un algoritm pentru parcurgerea sau căutarea într-o structură de date de tip arbore sau graf. Aceasta începe cu rădăcina arborelui (sau cu un nod arbitrar dintr-un graf, uneori denumit „cheie de căutare”[1]) și explorează nodurile mai întâi nodurile vecine acestuia, înainte de a trece la vecinii de pe nivelul următor (vecinii vecinilor).

BFS și aplicarea acestuia în găsirea de componente conexe⁠(d) ale grafurilor au fost inventate în 1945 de către Konrad Zuse, în teza sa de doctorat (respinsă) despre limbaj de programare Plankalkül⁠(d), dar aceasta a fost publicată abia în 1972.[2] A fost reinventat în 1959 de către E. F. Moore⁠(d), care l-a folosit pentru a găsi cea mai scurtă cale de ieșire dintr-un labirint,[3][4] și descoperită independent⁠(d) de C. Y. Lee ca algoritm de rutare a cablajelor⁠(d) (publicat în 1961).[5][6]

Pseudocod[modificare | modificare sursă]

Intrare: Un graf Graph și un nod inițial root al lui Graph

Ieșire: Starea finală. Legăturile părinte urmează calea cea mai scurtă înapoi la root

O implementare nerecursivă a căutării în lățime:

Breadth-First-Search(Graph, root):
    
    create empty set S
    create empty queue Q      

    add root to S
    Q.enqueue(root)                      

    while Q is not empty:
        current = Q.dequeue()
        if current is the goal:
            return current
        for each node n that is adjacent to current:
            if n is not in S:
                add n to S
                n.parent = current
                Q.enqueue(n)

Mai multe detalii[modificare | modificare sursă]

Această implementare nerecursivă este similară cu cea nerecursivă a căutării în adâncime, dar are două diferențe față de acesta:

  1. Utilizează o coadă (First In First Out), în loc de stivă; și
  2. Verifică dacă un nod a fost descoperit înainte de a-l pune în coadă, în loc să amâne această verificare până la scoaterea nodului din coadă.

Coada Q conține frontiera de-a lungul căreia algoritmul efectuează căutarea.

Mulțimea S este utilizată pentru a urmări care noduri au fost vizitate (necesar pentru o căutare generală prin graf, dar nu și pentru cea prin arbore). La începutul algoritmului, mulțimea este vidă. La sfârșitul algoritmului, acesta conține toate nodurile aflate la o distanță față de rădăcină mai mică decât a nodului căutat.


Părintele atribut fiecărui nod este util pentru accesarea nodurilor pe calea cea mai scurtă, de exemplu, făcând backtracking de la nodul destinație la nodul de pornire, după ce s-a aplicat BFS, și s-au stabilit nodurile predecesoare.

Căutarea în lățime produce așa-numitul arbore de căutare în lățime. Funcționarea unui arbore de căutare în lățime este ilustrată de următorul exemplu.

Exemplu[modificare | modificare sursă]

Acesta este un exemplu de arbore de căutare în lățime obținut prin rularea BFS pornind de la Frankfurt:

Graf pe baza unei hărți a Germaniei cu unele conexiuni între orașe
Arborele de căutare în lățime obținut atunci când se rulează BFS pe graful de mai sus, pornind de la Frankfurt

Analiza[modificare | modificare sursă]

Complexitatea în timp și spațiu[modificare | modificare sursă]

Complexitatea în timp poate fi exprimată ca deoarece în cel mai rău caz vor fi analizate fiecare nod și fiecare muchie. este numărul de noduri și este numărul de muchii din graf.   poate varia între și , în funcție de cât de rar este graful dat la intrare.[7]

Atunci când numărul de noduri din graf este cunoscut dinainte, și se utilizează structuri de date suplimentare pentru a determina care noduri au fost deja adăugate la coadă, complexitatea în spațiu poate fi exprimată ca , unde  este cardinalul⁠(d) mulțimii nodurilor. Aceasta în plus față de spațiul necesar pentru graful în sine, care poate varia în funcție de reprezentarea grafului⁠(d) utilizată de implementarea algoritmului.

Atunci când se lucrează cu grafuri care sunt prea mari pentru a fi stocate în mod explicit (sau infinite), este mai practic să se descrie complexitatea căutării în lățime în alți termeni: găsirea nodurilor aflate la distanța d față de nodul de start (măsurată în număr de muchii) solicită BFS un timp și un spațiu de O(bd + 1), unde b este „factorul de ramificare” al grafului (gradul exterior mediu).[8]:81

Completitudine și optimalitate[modificare | modificare sursă]

În analiza algoritmilor, datele de intrare ale căutării în lățime sunt presupuse a fi un graf finit, reprezentat în mod explicit ca listă de adiacență sau ceva similar. Cu toate acestea, la aplicarea metodelor de parcurgere a grafurilor folosite în inteligența artificială, datele de intrare pot fi o reprezentare implicită⁠(d) a unui graf infinit. În acest context, o metodă de căutare este descrisă ca fiind completă atunci când este garantat că va găsi o stare căutată, dacă există una. Căutarea în lățime este completă, dar cea în adâncime nu este. Atunci când este aplicată grafurilor infinite reprezentate implicit, căutarea în lățime va găsi în cele din urmă starea căutată, dar cea în lățime poate să se piardă în unele părți din graf în care nu există starea căutată și să nu se mai întoarcă niciodată.[9]

Ordonarea BFS[modificare | modificare sursă]

O enumerare a nodurilor unui graf este declarată a fi o ordonare BFS dacă este o ieșire posibilă a aplicării BFS pe graful respectiv.

Fie  un graf cu  noduri și fie  mulțimea vecinilor lui . Pentru  o listă de elemente distincte din , și pentru , fie  cel mai mic  astfel încât  este vecin cu , dacă există , și  altfel.

Fie  o enumerare a nodurilor lui . Enumerarea  este o ordonare BFS (cu originea ) dacă, pentru orice , este nodul  astfel încât  este minimal. Echivalent, este o ordonare BFS dacă, oricare ar fi  cu , există un vecin  al lui  astfel încât .

Aplicații[modificare | modificare sursă]

Căutarea în lățime poate fi folosită pentru a rezolva multe probleme din teoria grafurilor, de exemplu:

Bibliografie[modificare | modificare sursă]

  1. ^ „Graph500 benchmark specification (supercomputer performance evaluation)”. Graph500.org, 2010. 
  2. ^ Zuse, Konrad (), Der Plankalkül (în German), Konrad Zuse Internet Archive  Mai multe valori specificate pentru |author-link= și |authorlink= (help) .
  3. ^ Moore, Edward F. (). Proceedings of the International Symposium on the Theory of Switching. Harvard University Press. pp. 285–292.  Mai multe valori specificate pentru |author-link= și |authorlink= (help)
  4. ^ Skiena, Steven (). The Algorithm Design Manual. p. 480. doi:10.1007/978-1-84800-070-4_4.  Parametru necunoscut |legătură-autor= ignorat (help)
  5. ^ Leiserson, Charles E.; Schardl, Tao B. (). A Work-Efficient Parallel Breadth-First Search Algorithm (or How to Cope with the Nondeterminism of Reducers) (PDF). ACM Symp. on Parallelism in Algorithms and Architectures.  Mai multe valori specificate pentru |last1= și |last= (help); Mai multe valori specificate pentru |first1= și |first= (help)
  6. ^ Lee, C. Y. (). „An Algorithm for Path Connections and Its Applications”. IRE Transactions on Electronic Computers.  Mai multe valori specificate pentru |work= și |journal= (help)
  7. ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford () [1990]. „22.2 Breadth-first search”. Introduction to Algorithms⁠(d) (ed. 2nd). MIT Press and McGraw-Hill. pp. 531–539. ISBN 0-262-03293-7. 
  8. ^ Russell, Stuart; Norvig, Peter () [1995]. Artificial Intelligence: A Modern Approach⁠(d) (ed. 2nd). Prentice Hall. ISBN 978-0137903955. 
  9. ^ Coppin, B. (2004). Artificial intelligence illuminated. Jones & Bartlett Learning. pp. 79–80.
  10. ^ Aziz, Adnan; Prakash, Amit (). „4. Algorithms on Graphs”. Algorithms for Interviews. p. 144. ISBN 1453792996. 

Legături externe[modificare | modificare sursă]

Commons
Wikimedia Commons conține materiale multimedia legate de căutare în lățime