Lățimea prima căutare

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 26 aprilie 2021; verificările necesită 3 modificări .

Căutarea pe lățime ( BFS ) este una dintre metodele de traversare a graficului . Fie dat graficul și vârful inițial . Algoritmul de căutare pe lățimea întâi traversează sistematic toate muchiile pentru a „descoperi” toate vârfurile accesibile de la , în timp ce calculează distanța (numărul minim de muchii) de la fiecare vârf accesibil . Algoritmul funcționează atât pentru graficele direcționate , cât și pentru cele nedirecționate. [unu] $G=(V,E)$ $s$ $G$ $s$ $s$ $s$

Breadth-first search are acest nume deoarece în procesul de traversare mergem în lățime, adică înainte de a începe căutarea vârfurilor la distanță , vârfurile la distanță sunt parcurse . $k+1$ $k$

Breadth first search este unul dintre algoritmii de căutare neinformați [2] .

Operațiunea algoritmului

Breadth-First Search funcționează trecând prin nivelurile individuale ale graficului , începând de la nodul sursă . $u$

Luați în considerare toate muchiile care ies din nod . Dacă următorul nod este nodul țintă, atunci căutarea se termină; în caz contrar, nodul este adăugat la coadă . După ce toate muchiile care părăsesc nodul sunt verificate, următorul nod este luat din coadă și procesul se repetă. $(u,v)$ $u$ $v$ $v$ $u$ $u$

Descriere informală

Puneți nodul de la care începe căutarea în coada inițial goală.
Preluați un nod din capul cozii și marcați-l ca implementat. $u$
- Dacă nodul este nodul țintă, atunci încheiați căutarea cu un rezultat de „succes”. $u$
- În caz contrar, toți succesorii nodului care nu sunt încă implementați și nu sunt în coadă sunt adăugați la sfârșitul cozii. $u$
Dacă coada este goală, atunci toate nodurile grafului conectat au fost scanate, prin urmare, nodul țintă este inaccesibil față de cel inițial; terminați căutarea cu rezultatul „eșuat”.
Reveniți la punctul 2.

Notă: împărțirea vârfurilor în desfășurate și nu este necesară pentru un grafic arbitrar (deoarece poate avea cicluri). Pentru un arbore , această operație nu este necesară, deoarece fiecare vârf va fi selectat o singură dată.

Descriere formală

Mai jos este pseudocodul algoritmului pentru cazul în care este necesar doar să găsiți nodul țintă. În funcție de aplicația specifică a algoritmului, poate fi necesar un cod suplimentar pentru a stoca informațiile necesare (distanța de la nodul de pornire, nodul părinte etc.)

Formulare recursiva:

BFS( start_node , goal_node ) { return BFS'({ start_node }, ∅, goal_node ); } BFS'( margini , vizitat , goal_node ) { if ( margini == ∅) { // Nodul țintă nu a fost găsit returnează fals; } if ( goal_node ∈ franjuri ) { return true; } return BFS'({ copil | x ∈ franjuri , copil ∈ expand( x )} \ vizitat , vizitat ∪ franjuri , goal_node ); }

Formulare iterativă:

BFS( start_node , goal_node ) { for (toate nodurile i) vizitate [ i ] = false; // inițial lista nodurilor vizitate este coada goală .push( start_node ); // pornind de la nodul sursă vizitat [ start_node ] = true; while (! coada .empty() ) { // până când coada este goală nod = coada .pop(); // preia primul element din coada if ( node == goal_node ) { return true; // verifică dacă nodul curent este ținta } foreach ( copil în expand( nodul )) { // toți succesorii nodului curent, ... dacă (vizitat[ copil ] == fals) { // ... care nu au fost încă vizitați ... coadă .push ( copil ); // ... adaugă la sfârșitul cozii... vizitat [ copil ] = adevărat; // ... și marcați ca vizitat } } } returnează fals; // Nodul țintă este inaccesibil }

Implementarea Pascal :

funcţia BFS ( v : Nod ) : Boolean ; începe coada ( v ) ; în timp ce coada nu este goală , începe curr := scoate la coadă () ; if is_goal ( curr ) atunci începe BFS := true ; ieșire ; sfârşitul ; marca ( curr ) ; pentru next in succesors ( curr ) do if nu este marcat ( next ) apoi începe coda ( next ) ; sfârşitul ; sfârşitul ; BFS := false ; sfârşitul ;

Proprietăți

Notați numărul de vârfuri și muchii din grafic ca și respectiv. $\vert V\vert$ $\vert E\vert$

Complexitatea spațială

Deoarece toate nodurile extinse sunt stocate în memorie, complexitatea spațială a algoritmului este [2] . $O(\vert V\vert +\vert E\vert )$

Algoritmul de căutare de aprofundare iterativă este similar cu căutarea pe lățime, prin aceea că fiecare iterație examinează întregul nivel de noduri noi înainte de a trece la nivelul următor, dar necesită mult mai puțină memorie.

Complexitatea timpului

Deoarece în cel mai rău caz algoritmul vizitează toate nodurile graficului, atunci când stochează graficul sub formă de liste de adiacență , complexitatea de timp a algoritmului este [2] [3] . $O(\vert V\vert +\vert E\vert )$

Completitudine

Dacă fiecare nod are un număr finit de succesori, algoritmul este complet: dacă există o soluție, algoritmul de căutare pe lățimea întâi o găsește, indiferent dacă graficul este sau nu finit. Totuși, dacă nu există o soluție, căutarea nu se termină pe graficul infinit.

Optimitatea

Dacă lungimile marginilor graficului sunt egale, căutarea pe lățimea întâi este optimă, adică găsește întotdeauna calea cea mai scurtă. În cazul unui grafic ponderat , căutarea pe lățimea întâi găsește o cale care conține numărul minim de muchii, dar nu neapărat pe cea mai scurtă.

Căutarea pe primul cost este o generalizare a căutării pe lățimea întâi și este optimă pe un grafic ponderat cu ponderi de margine nenegative. Algoritmul vizitează nodurile graficului în ordinea creșterii costului căii de la nodul de pornire și, de obicei, utilizează o coadă de prioritate .

Istoric și aplicații

Căutarea pe lățimea întâi a fost propusă oficial de E. F. Moore în contextul găsirii unei căi într-un labirint [4] . Lee a descoperit în mod independent același algoritm în contextul cablajului PCB [5] [6] [7] .

Breadth-First Search poate fi aplicată problemelor legate de teoria grafurilor :

Algoritm ondulatoriu pentru găsirea unei căi într-un labirint [4]
Trasarea undelor de plăci cu circuite imprimate [5]
Găsirea componentelor de conectivitate într-un grafic
Găsirea celei mai scurte căi între două noduri ale unui grafic neponderat
Căutare în spațiul stărilor : găsirea unei soluții la problema cu cel mai mic număr de mișcări, dacă fiecare stare a sistemului poate fi reprezentată printr-un vârf de grafic, iar tranzițiile de la o stare la alta pot fi reprezentate prin muchii graficului [2]
Găsirea celui mai scurt ciclu într-un grafic neponderat direcționat [2]
Găsirea tuturor nodurilor și muchiilor situate pe orice cale cea mai scurtă între două vârfuri și [2] $A$ $b$
Creșterea căutării traseului în algoritmul Ford-Fulkerson ( algoritmul Edmonds-Karp )

Vezi și

Căutare limitată la profunzime

Note

↑ Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmi: construcție și analiză. - Ed. a 3-a. - Editura Williams, 2013. - S. 630. - 1328 p. - ISBN 978-5-8459-1794-2 (rusă). - ISBN 978-0-2620-3384-8 (engleză).
↑ 1 2 3 4 5 6 MAXimal :: algo :: Prima căutare amplă într-un grafic și aplicațiile acestuia Arhivat 16 septembrie 2013 la Wayback Machine
↑ 1 2 NSTU Structuri și algoritmi de procesare a datelor Parcursul graficului lățimii Copie de arhivă din 30 decembrie 2012 la Wayback Machine
↑ 1 2 Moore E. F. The shortest path through a maze // Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 aprilie 1957) - Harvard University Press , 1959. - Vol. 2. - P. 285-292. — 345 p. - ( Analele laboratorului de calcul al Universității Harvard ; Vol. 30) - ISSN 0073-0750
↑ 1 2 C. Y. Lee (1961), An algorithm for path connection and its applications . IRE Transactions on Electronic Computers , EC-10(3), pp. 346–365
↑ Cormen et al , Introduction to Algorithms, ediția a III-a, p. 623
↑ Mathematics Stack Exchange Originea algoritmului Breadth-First Search

Literatură

TH Cormen, CE Leiserson, RL Rivest, C. Stein. Introducere în algoritmi. — ediția a 3-a. - The MIT Press, 2009. - ISBN 978-0-262-03384-8 . . Traducere ediția a 2-a: Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmi: constructie si analiza = Introduction to Algorithms. - Ed. a II-a. - M .: „Williams” , 2006. - S. 1296. - ISBN 0-07-013151-1 .
Levitin A. V. Capitolul 5. Metoda de reducere a dimensiunii problemei: Breadth-First Search // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - 576 p. — ISBN 978-5-8459-0987-9

Link -uri

Algoritmi de căutare grafică
Metode neinformate	Căutare bidirecțională Căutare fascicul Prima căutare a lățimii lexicografice Lățimea prima căutare Căutare după criteriul de cost Profunzime prima căutare Căutare înapoi Caută prin urcare în vârf Căutare limitată la profunzime Căutare în profunzime cu aprofundare iterativă
Metode informate	Decuparea alfa beta Ramura și metoda legată Căutați după prima potrivire A* B* D* Găsirea unui punct de tranziție IDA* Căutare recurstivă pe primul cel mai bun meci SMA*
Comenzi rapide	Algoritmul undelor Algoritmul Bellman-Ford algoritmul lui Dijkstra Algoritmul Johnson algoritmul lui Levit Algoritmul Floyd-Warshall Căutare margine
Arborele de întindere minim	algoritmul lui Boruvka algoritmul lui Prim algoritmul lui Kruskal
Alte	Algoritmul British Museum Algoritmul Edmonds Traversarea copacilor Algoritmul celui mai apropiat vecin în problema vânzătorului ambulant