Cerca en amplada
 |
Aquest article o secció necessita l'atenció d'un expert en la matèria. |
La cerca en amplada (de l'anglès BFS - Breadth First Search) és un algorisme informàtic per recórrer o buscar elements en un graf (usat sovint en arbres). Intuïtivament, es comença a l'arrel (escollint algun node com a element arrel en el cas d'un graf) i s'exploren tots els veïns d'aquest node. A continuació per a cada un dels veïns s'exploren els seus respectius veïns adjacents, i així fins que es recorri tot l'arbre.
Formalment, BFS és un algorisme de cerca sense informació, que expandeix i examina tots els nodes d'un arbre sistemàticament per buscar una solució. Utilitza l'estratègia oposada de la cerca en profunditat, que en el seu lloc explora la branca del node tant com sigui possible abans de retrocedir i ampliar altres nodes.[1] L'algorisme no fa servir cap estratègia heurística.
BFS i la seva aplicació per trobar components connectats de grafs van ser inventats el 1945 per Konrad Zuse, en la seva tesi doctoral (rebutjada) sobre el llenguatge de programació Plankalkül, però no es va publicar fins al 1972.[2] Va ser reinventat el 1959 per Edward F. Moore, que el va utilitzar per trobar el camí més curt d'un laberint,[3][4] i va ser desenvolupat més tard per C. Y. Lee convertint-lo en un algorisme d'encaminament amb aplicacions en l'automatització de dissenys electrònics.[5] Si les arestes tenen pesos negatius, s'aplica l'algorisme de Bellman-Ford en alguna de les dues versions.
Procediment
[modifica]Donat un vèrtex font, Breadth-first search sistemàticament explora els vèrtexs de G per "descobrir" tots els vèrtexs assolibles des s.
Calcula la distància (menor nombre de vèrtexs) des de s a tots els vèrtexs assolibles.
Després produeix un arbre BF amb arrel en s i que contindrà tots els vèrtexs assolibles.
El camí desde s a cada vèrtex en aquest recorregut conté el mínim nombre de vèrtexs. És el camí més curt mesurat en nombre de vèrtexs.
El seu nom es deu al fet que expandeix uniformement la frontera entre el descobert i el no descobert. Arriba als nodes de distància k, només després d'haver arribat a tots els nodes a distància k-1.
Pseudocodi
[modifica]Es defineix un graf G i un vector inicial v. La nomenclatura addicional utilitzada és: Q = Cua de dades.
1 procedure BFS(G,v): 2 create a queue Q 3 enqueue v onto Q 4 mark v 5 while Q is not empty: 6 t ← Q.dequeue() 7 if t is what we are looking for: 8 return t 9 for all edges e in G.adjacentEdges(t) do 12 u ← G.adjacentVertex(t,e) 13 if u is not marked: 14 mark u 15 enqueue u onto Q
* Manca recórrer vèrtexs no adjacents directament o indirectament al vèrtex origen "s", ja que la cua queda buida sense els adjacents restants.
El temps d'execució és O(|V|+|E|), on |V| és el nombre de vèrtexs i |E| el nombre d'arestes, ja que en el pitjor cas l'algorisme haurà de comprovar cada vèrtex i cada aresta. Cada node és posat a la cua un cop, i la seva llista d'adjacència també és recorreguda una vegada.[1]
Aplicacions
[modifica]La cerca per amplada es pot utilitzar per resoldre molts problemes de la teoria de grafs, per exemple:
- Trobar el camí més curt entre dos nodes, amb la longitud del camí mesurada pel nombre d'arestes (un avantatge respecte a la cerca en profunditat).
- Recollida de memòria brossa (Garbage Collection) mitjançant l'algorisme de Cheney.
- Reduir l'amplada de banda d'una matriu simètrica dispersa mitjançant l'algorisme de Cuthill-McKee.
- Calcular el flux màxim en una xarxa de flux amb l'algorisme de Ford-Fulkerson.
- Reconstrucció d'arbres binaris de forma eficient.
- Comprovar si un graf és bipartit.
Variants
[modifica]La cerca en amplada lexicogràfica o en ordre lexicogràfic (Lex-BFS) és un algorisme de temps lineal per ordenar els vèrtexs d'un graf. L'algorisme és diferent, però produeix una ordenació que és coherent amb la cerca en amplada. La diferència és que en lloc de definir el vèrtex a triar en cada pas de manera imperativa, es pot definir la mateixa seqüència de vèrtexs declarativament per les propietats d'aquests vèrtexs.[6] L'algorisme rep el nom del fet que permet indexar les files i columnes d'una matriu d'adjacència d'un graf en ordre lexicogràfic.
Una altra variant és la cerca en amplada paral·lela, una modificació de l'algorisme original emprant computació paral·lela per tal d'accelerar el procés.[7]
Vegeu també
[modifica]Referències
[modifica]- ↑ 1,0 1,1 Thomas H.; T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms (PDF) (en anglès). 3rd. The MIT Press, 2009. ISBN 978-0-262-53305-8. OCLC 1006880283. El capítol 22.2 està dedicat a la cerca en amplada, i el 22.3 a la cerca en profunditat.
- ↑ Zuse, Konrad «Der Plankalkül» (PDF) (en alemany). Konrad Zuse Internet Archive, 1972, pàg. 96-105. (numeració interna: 2.47-2.56).
- ↑ Moore, Edward F. «The shortest path through a maze». Proceedings of the International Symposium on the Theory of Switching. Harvard University Press, 1959, pàg. 285-292.
- ↑ Skiena, Steven. «Sorting and Searching». A: The Algorithm Design Manual. Springer, 2008, p. 480. DOI 10.1007/978-1-84800-070-4_4. ISBN 978-1-84800-069-8.
- ↑ Lee, C. Y. «An Algorithm for Path Connections and Its Applications». IRE Transactions on Electronic Computers, 1961. DOI: 10.1109/TEC.1961.5219222.
- ↑ Corneil, Derek G. «Lexicographic Breadth First Search - A Survey». Springer-Verlag. Graph-Theoretic Methods in Computer Science: 30th International Workshop [Bad Honnef, Germany], Revisted Papters, Lecture Notes in Computer Science, 3353, 2004, pàg. 1-19. DOI: 10.1007/978-3-540-30559-0_1.
- ↑ Leiserson Schardl, Charles E. Tao B. «A work-efficient parallel breath-first search algorithm (or how to cope with the nondeterminism of reducers)». ACM, Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures, 2010.