Vés al contingut

Cerca en amplada: diferència entre les revisions

De la Viquipèdia, l'enciclopèdia lliure
Exploració interactiva de l'historial
← Edició anteriorEdició següent →
Contingut suprimit Contingut afegit
VisualWikitext
Expansió del contingut
Aplicacions i variants
Línia 2: Línia 2:
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 (matemàtiques)|graf]] (usat sovint en [[arbre]]s). 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.
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 (matemàtiques)|graf]] (usat sovint en [[arbre]]s). 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.<ref>{{ref-llibre |cognom=Thomas H. |títol=Introduction to Algorithms |editorial=The MIT Press |any=2009 |isbn=978-0-262-53305-8 |url=http://sd.blackball.lv/library/Introduction_to_Algorithms_Third_Edition_(2009).pdf |coautors=T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein |llengua=en |edició=3rd |format=PDF |oclc=1006880283}} El capítol 22.2 està dedicat a la cerca en amplada, i el 22.3 a la cerca en profunditat.</ref> L'algorisme no fa servir cap estratègia [[heurística]].
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.<ref name="intro">{{ref-llibre |cognom=Thomas H. |títol=Introduction to Algorithms |editorial=The MIT Press |any=2009 |isbn=978-0-262-53305-8 |url=http://sd.blackball.lv/library/Introduction_to_Algorithms_Third_Edition_(2009).pdf |coautors=T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein |llengua=en |edició=3rd |format=PDF |oclc=1006880283}} El capítol 22.2 està dedicat a la cerca en amplada, i el 22.3 a la cerca en profunditat.</ref> L'algorisme no fa servir cap estratègia [[heurística]].


''BFS'' i la seva aplicació per trobar components connectats de [[Teoria de grafs|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.<ref>{{ref-publicació |cognom=Zuse |nom=Konrad |títol=Der Plankalkül |publicació=Konrad Zuse Internet Archive |data=1972 |pàgines=96-105 |url=http://zuse.zib.de/item/gHI1cNsUuQweHB6 |llengua=de |format=PDF}} (numeració interna: 2.47-2.56).</ref> Va ser reinventat el 1959 per [[Edward F. Moore]], que el va utilitzar per trobar el camí més curt d'un laberint,<ref>{{ref-publicació |cognom=Moore |nom=Edward F. |títol=The shortest path through a maze |publicació=Proceedings of the International Symposium on the Theory of Switching. Harvard University Press |data=1959 |pàgines=285-292}}</ref><ref>{{ref-llibre |cognom=Skiena |nom=Steven |títol=The Algorithm Design Manual |pàgines=480 |editorial=Springer |any=2008 |capítol=Sorting and Searching |bibcode=2008adm..book.....S |doi=10.1007/978-1-84800-070-4_4 |isbn=978-1-84800-069-8}}</ref>, 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.<ref>{{ref-publicació |cognom=Lee |nom=C. Y. |títol=An Algorithm for Path Connections and Its Applications |publicació=IRE Transactions on Electronic Computers |data=1961 |doi=10.1109/TEC.1961.5219222}}</ref> Si les arestes tenen pesos negatius, s'aplica l'[[algorisme de Bellman-Ford]] en alguna de les dues versions.
''BFS'' i la seva aplicació per trobar components connectats de [[Teoria de grafs|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.<ref>{{ref-publicació |cognom=Zuse |nom=Konrad |títol=Der Plankalkül |publicació=Konrad Zuse Internet Archive |data=1972 |pàgines=96-105 |url=http://zuse.zib.de/item/gHI1cNsUuQweHB6 |llengua=de |format=PDF}} (numeració interna: 2.47-2.56).</ref> Va ser reinventat el 1959 per [[Edward F. Moore]], que el va utilitzar per trobar el camí més curt d'un laberint,<ref>{{ref-publicació |cognom=Moore |nom=Edward F. |títol=The shortest path through a maze |publicació=Proceedings of the International Symposium on the Theory of Switching. Harvard University Press |data=1959 |pàgines=285-292}}</ref><ref>{{ref-llibre |cognom=Skiena |nom=Steven |títol=The Algorithm Design Manual |pàgines=480 |editorial=Springer |any=2008 |capítol=Sorting and Searching |bibcode=2008adm..book.....S |doi=10.1007/978-1-84800-070-4_4 |isbn=978-1-84800-069-8}}</ref>, 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.<ref>{{ref-publicació |cognom=Lee |nom=C. Y. |títol=An Algorithm for Path Connections and Its Applications |publicació=IRE Transactions on Electronic Computers |data=1961 |doi=10.1109/TEC.1961.5219222}}</ref> Si les arestes tenen pesos negatius, s'aplica l'[[algorisme de Bellman-Ford]] en alguna de les dues versions.
Línia 18: Línia 18:


== Pseudocodi ==
== Pseudocodi ==
Es defineix un graf ''G'' i un vector inicial ''v''.
La nomenclatura addicional utilitzada és: Q = Cua de dades
La nomenclatura addicional utilitzada és: ''Q'' = Cua de dades.


1 '''procedure''' BFS(''G'',''v''):
1 '''procedure''' BFS(''G'',''v''):
Línia 37: Línia 38:
ja que la cua queda buida sense els adjacents restants.
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.
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.<ref name="intro"/>

== Aplicacions ==
La cerca per amplada es pot utilitzar per resoldre molts problemes de la [[teoria de grafs]], per exemple:
* Trobar el [[Problema del camí més curt|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 [[Problema del flux màxim|flux màxim]] en una [[xarxa de flux]] amb l'[[algorisme de Ford-Fulkerson]].
* Reconstrucció d'[[Arbre binari|arbres binaris]] de forma eficient.
* Comprovar si un graf és [[Graf bipartit|bipartit]].

== Variants ==
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 [[Programació imperativa|imperativa]], es pot definir la mateixa seqüència de vèrtexs declarativament per les propietats d'aquests vèrtexs.<ref>{{ref-publicació |cognom=Corneil |nom=Derek G. |títol=Lexicographic Breadth First Search - A Survey |publicació=Springer-Verlag |data=2004 |pàgines=1-19 |volum=Revisted Papters, Lecture Notes in Computer Science, 3353 |doi=10.1007/978-3-540-30559-0_1 |lloc=Bad Honnef, Germany |editorial=Graph-Theoretic Methods in Computer Science: 30th International Workshop}}</ref> 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.<ref>{{ref-publicació |cognom=Leiserson Schardl |nom=Charles E. Tao B. |títol=A work-efficient parallel breath-first search algorithm (or how to cope with the nondeterminism of reducers) |publicació=ACM |data=2010 |volum=Proceedings of the twenty-second annual ACM symposium on Parallelism in algorithms and architectures |url=https://dl.acm.org/citation.cfm?id=1810534}}</ref>


== Vegeu també ==
== Vegeu també ==

Revisió del 18:43, 31 març 2021

Aquest article o secció necessita l'atenció d'un expert en la matèria.
Si us plau, ajudeu a trobar-ne un o milloreu aquesta pàgina vosaltres mateixos si podeu. (Vegeu la discussió).

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

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

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

La cerca per amplada es pot utilitzar per resoldre molts problemes de la teoria de grafs, per exemple:

Variants

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é

Referències

  1. ↑ 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.
  2. ↑ Zuse, Konrad «Der Plankalkül» (PDF) (en alemany). Konrad Zuse Internet Archive, 1972, pàg. 96-105. (numeració interna: 2.47-2.56).
  3. ↑ 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.
  4. ↑ 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. 
  5. ↑ Lee, C. Y. «An Algorithm for Path Connections and Its Applications». IRE Transactions on Electronic Computers, 1961. DOI: 10.1109/TEC.1961.5219222.
  6. ↑ 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.
  7. ↑ 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.


Obtingut de «https://ca.wikipedia.org/w/index.php?title=Cerca_en_amplada&oldid=26840228»