Back البحث المتسع الاول Arabic Eninə axtarış alqoritmi Azerbaijani Обхождане в ширина Bulgarian Prohledávání do šířky Czech Breitensuche German Αναζήτηση κατά πλάτος Greek Breadth-first search English Búsqueda en anchura Spanish Laiuti otsing Estonian Zabalera bilaketa Basque
 |
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.
- ↑ 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.