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 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

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

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

Utilizează o coadă (First In First Out), în loc de stivă; și
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

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

Complexitatea în timp și spațiu

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 (b d + 1)$ , unde $b$ este „factorul de ramificare” al grafului (gradul exterior mediu).^[8]^:81

Completitudine și optimalitate

Î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

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 $G=(V,E)$ un graf cu $n$ noduri și fie $N(v)$ mulțimea vecinilor lui $v$ . Pentru $\sigma =(v_{1},\dots ,v_{m})$ o listă de elemente distincte din $V$ , și pentru $v\in V\setminus \{v_{1},\dots ,v_{m}\}$ , fie $\nu _{\sigma }(v)$ cel mai mic $i$ astfel încât $v_{i}$ este vecin cu $v$ , dacă există $i$ , și $\infty$ altfel.

Fie $\sigma =(v_{1},\dots ,v_{n})$ o enumerare a nodurilor lui $V$ . Enumerarea $\sigma$ este o ordonare BFS (cu originea $v_{1}$ ) dacă, pentru orice $1<i\leq n$ , $v_{i}$ este nodul $w\in V\setminus \{v_{1},\dots ,v_{i}-1\}$ astfel încât $\nu _{(v_{1},\dots ,v_{i-1})}(w)$ este minimal. Echivalent, $\sigma$ este o ordonare BFS dacă, oricare ar fi $1\leq i<j<k\leq n$ cu $v_{i}\in N(v_{j})\setminus N(v_{k})$ , există un vecin $v_{m}$ al lui $v_{j}$ astfel încât $m<i$ .

Aplicații

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

Garbage collection^⁠(d), algoritmul lui Cheney^⁠(d)
Găsirea celui mai scurt drum între două noduri u și v, cu lungimea măsurată prin numărul de muchii (avantaj față de căutarea în adâncime)^[10]
Reducerea benzii reverse Cuthill–McKee^⁠(d)
Metoda Ford–Fulkerson de calcul a debitului maxim^⁠(d) printr-o rețea de debit^⁠(d)
Serializarea/deserializarea unui arbore binar vs serializarea în ordine sortată, permite reconstruirea arborelui într-o manieră eficientă.
Construcția funcției de eșec a identificatorului de șabloane Aho–Corasick algorithm^⁠(d).
Testarea bipartitudinii unui graf.

Bibliografie

^ „Graph500 benchmark specification (supercomputer performance evaluation)”. Graph500.org, 2010. Arhivat din original la 26 martie 2015. Accesat în 31 iulie 2017.
^ Zuse, Konrad (1972), Der Plankalkül (în German), Konrad Zuse Internet Archive Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor).
^ Moore, Edward F. (1959). 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= (ajutor)
^ Skiena, Steven (2008). The Algorithm Design Manual. Springer. p. 480. doi:10.1007/978-1-84800-070-4_4.
^ Leiserson, Charles E.; Schardl, Tao B. (2010). 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= (ajutor); Mai multe valori specificate pentru |first1= și |first= (ajutor)
^ Lee, C. Y. (1961). „An Algorithm for Path Connections and Its Applications”. IRE Transactions on Electronic Computers. Mai multe valori specificate pentru |work= și |journal= (ajutor)
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [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.
^ Russell, Stuart; Norvig, Peter (2003) [1995]. Artificial Intelligence: A Modern Approach^⁠(d) (ed. 2nd). Prentice Hall. ISBN 978-0137903955.
^ Coppin, B. (2004). Artificial intelligence illuminated. Jones & Bartlett Learning. pp. 79–80.
^ Aziz, Adnan; Prakash, Amit (2010). „4. Algorithms on Graphs”. Algorithms for Interviews. p. 144. ISBN 1453792996.

Knuth, Donald E. (1997), The Art of Computer Programming Vol 1. 3rd ed., Boston: Addison-Wesley, ISBN 0-201-89683-4, arhivat din original la 4 septembrie 2008, accesat în 31 iulie 2017

Legături externe

Commons

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

Open Data Structures - Secțiunea 12.3.1 - Căutarea în lățime

[1] „Graph500 benchmark specification (supercomputer performance evaluation)”. Graph500.org, 2010. Arhivat din original la 26 martie 2015. Accesat în 31 iulie 2017.

[2] Zuse, Konrad (1972), Der Plankalkül (în German), Konrad Zuse Internet Archive Mai multe valori specificate pentru |author-link= și |authorlink= (ajutor).

[3] Moore, Edward F. (1959). 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= (ajutor)

[skiena-4] Skiena, Steven (2008). The Algorithm Design Manual. Springer. p. 480. doi:10.1007/978-1-84800-070-4_4.

[5] Leiserson, Charles E.; Schardl, Tao B. (2010). 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= (ajutor); Mai multe valori specificate pentru |first1= și |first= (ajutor)

[6] Lee, C. Y. (1961). „An Algorithm for Path Connections and Its Applications”. IRE Transactions on Electronic Computers. Mai multe valori specificate pentru |work= și |journal= (ajutor)

[clrs-7] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [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 (2003) [1995]. Artificial Intelligence: A Modern Approach^⁠(d) (ed. 2nd). Prentice Hall. ISBN 978-0137903955.

[coppin-9] Coppin, B. (2004). Artificial intelligence illuminated. Jones & Bartlett Learning. pp. 79–80.

[10] Aziz, Adnan; Prakash, Amit (2010). „4. Algorithms on Graphs”. Algorithms for Interviews. p. 144. ISBN 1453792996.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]