Cerca en profunditat

Una cerca en profunditat (en anglès Depth First Search, DFS) és un algorisme que permet recórrer tots els nodes d'un arbre o graf de manera ordenada, però no uniforme. El seu funcionament es basa a anar expandint cada node que troba, de manera recursiva, recorrent tots els nodes d'un camí concret. Quan ja no queden més nodes per visitar d'aquest camí, es realitza un pas enrere (Backtracking), que permet que pugui tornar a començar el mateix procés amb cadascun dels germans d'un node ja processat.

De la mateixa manera, existeix l'algorisme de cerca en amplada (BFS - breadth first search).

El segle xix, el matemàtic francès Charles Pierre Trémaux investigà una versió de l'algorisme de cerca en profunditat com a estratègia per a la resolució de laberints.^[1]^[2]

Propietats

L'anàlisi del temps i l'espai necessaris per a l'algorisme DFS difereix en funció de l'àrea d'aplicació. En informàtica teòrica, l'algorisme DFS s'utilitza per recórrer un graf sencer, i necessita un temps Θ(|V| + |E|),^[3] lineal en la grandària del graf. En aquestes aplicacions, també necessita espai O(|V|) en el cas pitjor per emmagatzemar la pila de vèrtexs del camí de cerca en curs, així com el conjunt de vèrtexs ja visitats. Per tant, les fites de temps i espai són les mateixes que per l'algorisme de cerca en amplada, i l'elecció de quin d'aquests dos algorismes cal utilitzar no depèn tant de la seva complexitat com de les diferents propietats de les ordenacions de vèrtexs que produeixen.

Quant a les aplicacions de l'algorisme DFS en àrees específiques, com la cerca de solucions en intel·ligència artificial o el recorregut de pàgines web per part d'aranyes web, el graf que cal recórrer és o bé molt gran o bé infinit (DFS pot patir parades). En aquests casos, una solució pot ser limitar la cerca només fins a una certa profunditat; a causa de la limitació de recursos, com la memòria o l'espai en disc, no s'acostumen a utilitzar estructures de dades per guardar l'historial de quins vèrtexs s'han visitat. Quan es realitza la cerca fins a una profunditat limitada, el temps encara és lineal en termes del nombre de vèrtexs expandits i arestes (encara que aquest nombre no és el mateix que la grandària de tot el graf, ja que pot ser que alguns vèrtexs es recorrin més d'un cop i d'altres no es visitin), però la complexitat en espai d'aquesta variant de DFS només és proporcional a la profunditat límit, i com a resultat, molt menor que l'espai necessari per explorar fins a la mateixa profunditat mitjançant la cerca en amplada. Per a aquestes aplicacions, DFS resulta millor en la implementació de mètodes heurístics per escollir una branca apropiada. Quan no es coneix a priori una profunditat límit adequada, la cerca en profunditat iterativa aplica l'algorisme DFS repetidament amb una successió de límits creixent per a la profunditat. En el mode d'anàlisi de la intel·ligència artificial, amb un factor de ramificació superior a 1, la cerca en profunditat iterativa incrementa el temps de procés només en un factor constant sobre el cas en què es conegui prèviament la profunditat correcta, a causa del creixement geomètric del nombre de nodes per nivell.

L'algorisme de cerca en profunditat també es pot fer servir per recollir una mostra dels nodes del graf. Tanmateix, l'algorisme DFS incomplet, de manera semblant a BFS incomplet, és esbiaixat cap als nodes de grau elevat.

Exemples

Un exemple d'arbre és:

El resultat d'aplicar l'algorisme de cerca en profunditat sobre ell, començant per F, seria el recorregut següent: F, B, A, D, C, E, G, I, H.

Per al graf següent:

una cerca en profunditat que comenci en A, suposant que les arestes esquerres es recorren abans que les dretes, i suposant que la cerca recorda els vèrtexs visitats i no els repeteix (posat que aquest és un graf petit), recorre els nodes en aquest ordre: A, B, D, F, E, C, G. Les arestes recorregudes formen un arbre de Trémaux, una estructura amb aplicacions importants en teoria de grafs.

Si es realitza la mateixa cerca sense recordar els vèrtexs prèviament visitats, l'ordre seria A, B, D, F, E, A, B, D, F, E, etc. infinitament, atrapada en el cicle A, B, D, F, E i mai no arribaria a C o G.

La cerca en profunditat iterativa és una tècnica per evitar aquest bucle infinit i s'arribaria a tots els nodes.

Resultat d'una cerca en profunditat

Una descripció convenient d'una cerca en profunditat d'un graf és en termes d'un arbre d'expansió dels vèrtexs visitats durant la cerca. Basant-se en aquest arbre d'expansió, es poden classificar les arestes del graf original en tres tipus: arestes cap endavant, que apunten d'un node de l'arbre cap a un dels seus descendents, arestes cap enrere, que apunten d'un node a un dels seus superiors, i arestes creuades, que són aquelles que no pertanyen a cap dels dos tipus anteriors. De vegades, hom afegeix un quart tipus separat de les arestes cap endavant, les arestes de l'arbre, que són les arestes que pertanyen a l'arbre d'expansió. Si el graf original és no dirigit, llavors totes les seves arestes són arestes de l'arbre o arestes cap enrere.

Ordenacions dels vèrtexs

També és possible emprar la cerca en profunditat per ordenar linealment els vèrtexs del graf (o arbre) original. Hi ha tres maneres habituals de fer-ho:

Un preordre és una llista dels vèrtexs segons l'ordre en què l'algorisme DFS els visita per primer cop. Aquesta és una manera natural i compacta de descriure l'evolució de la cerca. Un preordre d'un arbre d'expressió és l'expressió en notació polonesa.

Un postordre és una llista dels vèrtexs segons l'ordre en què l'algorisme DFS els visita per últim cop. Un postordre d'un arbre d'expressió és l'expressió en notació polonesa inversa.

Un postordre invers és l'invers d'un postordre, és a dir, una llista dels vèrtexs en l'ordre invers de la seva última visita. El postordre invers no és el mateix que el preordre. Per exemple, quan se cerca en preordre el graf dirigit

començant en el node A, es visiten els nodes en seqüència, i el resultat és A, B, D, B, A, C, A o bé A, C, D, C, A, B, A (depenent de si l'algorisme opta per visitar primer B o C). Notem que s'hi inclouen les visites repetides a un node per verificar si encara té veïns sense visitar. Així, els preordres possibles són A, B, D, C i A, C, D, B (segons la primera aparició de cada node en la llista anterior), mentre que els postordres possibles són A, C, B, D i A, B, C, D (segons la darrera aparició de cada node en la llista anterior). El postordre invers proporciona una ordenació topològica per a qualsevol graf acíclic dirigit. Aquesta ordenació també és útil en anàlisi de flux de control, ja que sovint representa una linearització natural dels fluxos de control. El graf anterior podria representar el flux de control d'un fragment de codi com

si (A) llavors {
B
} sinó {
C
} D

i sembla natural considerar aquest codi en l'ordre A, B, C, D o en l'ordre A, C, B, D, però no en els ordres A, B, D, C ni A, C, D, B.

Pseudocodi

Entrada: Un graf G i un vèrtex v de G.

Sortida: Tots els vèrtexs que es poden visitar des de v, marcats com a visitats.

Una implementació recursiva de DFS:^[4]^[5]

1 procediment DFS(G,v):
2 etiquetar v com a visitat
3 per a tota aresta de v cap a w en G.arestesAdjacents(v) fer
4 si el vèrtex w no està etiquetat com a visitat llavors
5 cridar recursivament DFS(G,w)

Una implementació no recursiva de DFS:^[6]

1 procediment DFS-iteratiu(G,v):
2 sigui S una pila
3 S.empila(v)
4 mentre S no és buida
5 v = S.desempila()
6 si v no està etiquetat com a visitat:
7 etiquetar v com a visitat
8 per a tota aresta de v cap a w en G.arestesAdjacents(v) fer
9 S.empila(w)

Aquestes dues variants de l'algorisme DFS visiten els veïns de cada vèrtex en ordre invers l'una de l'altra: el primer veí de v que visita la variant recursiva és el primer en la llista d'arestes adjacents, mentre que en la variant iterativa el primer vèrtex visitat és l'últim de la llista d'arestes adjacents. La implementació recursiva visita els nods del graf d'exemple en l'ordre A, B, D, F, E, C, G. La implementació iterativa visita els nodes en l'ordre A, E, F, B, D, C, G. La variant iterativa és semblant a la cerca en amplada, però difereixen en dos aspectes: utilitza una pila en comptes d'una cua, i no es comprova si un vèrtex s'ha visitat fins que aquest vèrtex s'ha desempilat, en comptes de verificar-ho abans d'empilar-lo. Notem que aquesta implementació iterativa de DFS pot arribar a utilitzar un espai O(|E|) en el cas pitjor, per exemple en un graf complet.

Aplicacions

Algorisme aleatoritzat similar a la cerca en profunditat, emprat per generar un laberint

Alguns problemes que admeten solucions mitjançant l'aplicació de la cerca en profunditat són:

Trobar components connexes
Ordenació topològica
Trobar components 2-(aresta o vèrtex)-connexes
Trobar components 3-(aresta o vèrtex)-connexes
Trobar les arestes de tall d'un graf
Trobar els components fortament connexos
Comprovar si un graf és planar^[7]^[8]
Resoldre trencaclosques amb una sola solució, com laberints
La generació de laberints pot utilitzar una cerca en profunditat aleatoritzada.
Trobar biconnectivitat en grafs

Complexitat

La complexitat computacional de l'algorisme DFS fou investigada per Reif, que va demostrar que una versió de decisió (determinar si un vèrtex $u$ apareix abans d'un vèrtex $v$ en una ordenació DFS d'un graf amb arrel) és P-complet,^[9] la qual cosa significava que és "un malson per al processament paral·lel".^[10]

La complexitat en temps és $O(|E|)$ per a grafs explícits recorreguts sense repetició, i $O(b^{d})$ per a grafs implícits amb un factor de ramificació b explorats fins a la profunditat d. La complexitat en espai és $O(|V|)$ si s'explora el graf sencer sense repetició, i O(longitud del camí més llarg recorregut) per a grafs implícits sense eliminació dels nodes duplicats.

Referències

↑ Even, Shimon. Graph Algorithms. 2a edició. Cambridge University Press, 2011, p. 46–48. ISBN 978-0-521-73653-4.
↑ Sedgewick, Robert. Algorithms in C++: Graph Algorithms. 3a edició. Pearson Education, 2002. ISBN 978-0-201-36118-6.
↑ Cormen et al., 2001, p. 606.
↑ Goodrich i Tamassia, 2001.
↑ Cormen et al., 2001.
↑ Kleinberg i Tardos, 2006.
↑ Hopcroft, John; Tarjan, Robert E. «Efficient planarity testing». Journal of the Association for Computing Machinery, 21, 4, 1974, pàg. 549–568. DOI: 10.1145/321850.321852.
↑ de Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. «Trémaux Trees and Planarity». International Journal of Foundations of Computer Science, 17, 5, 2006, pàg. 1017–1030. DOI: 10.1142/S0129054106004248.
↑ Reif, John H. «Depth-first search is inherently sequential». Information Processing Letters, 20, 5, 1985. DOI: 10.1016/0020-0190(85)90024-9.
↑ Mehlhorn, Kurt; Sanders, Peter. Algorithms and Data Structures: The Basic Toolbox. Springer, 2008, p. 189. ISBN 978-3-642-09682-2.

Bibliografia

Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. «Section 22.3: Depth-first search». A: Introduction to Algorithms. 2a edició. MIT Press and McGraw-Hill, 2001, p. 540–549. ISBN 0-262-03293-7.
Goodrich, Michael T.; Tamassia, Roberto. Algorithm Design: Foundations, Analysis, and Internet Examples. Wiley, 2001. ISBN 0-471-38365-1.
Kleinberg, Jon; Tardos, Éva. Algorithm Design. Addison Wesley, 2006, p. 92–94. ISBN 0-321-29535-8.
Knuth, Donald E. The Art of Computer Programming Vol.1. 3a edició. Boston: Addison-Wesley, 1997. ISBN 0-201-89683-4. OCLC 155842391. Arxivat 2008-09-04 a Wayback Machine.

Enllaços externs

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Cerca en profunditat

[1] Even, Shimon. Graph Algorithms. 2a edició. Cambridge University Press, 2011, p. 46–48. ISBN 978-0-521-73653-4.

[2] Sedgewick, Robert. Algorithms in C++: Graph Algorithms. 3a edició. Pearson Education, 2002. ISBN 978-0-201-36118-6.

[FOOTNOTECormenLeisersonRivestStein2001606-3] Cormen et al., 2001, p. 606.

[FOOTNOTEGoodrichTamassia2001-4] Goodrich i Tamassia, 2001.

[FOOTNOTECormenLeisersonRivestStein2001-5] Cormen et al., 2001.

[FOOTNOTEKleinbergTardos2006-6] Kleinberg i Tardos, 2006.

[7] Hopcroft, John; Tarjan, Robert E. «Efficient planarity testing». Journal of the Association for Computing Machinery, 21, 4, 1974, pàg. 549–568. DOI: 10.1145/321850.321852.

[8] Fraysseix, H.; Ossona de Mendez, P.; Rosenstiehl, P. «Trémaux Trees and Planarity». International Journal of Foundations of Computer Science, 17, 5, 2006, pàg. 1017–1030. DOI: 10.1142/S0129054106004248.

[9] Reif, John H. «Depth-first search is inherently sequential». Information Processing Letters, 20, 5, 1985. DOI: 10.1016/0020-0190(85)90024-9.

[mehlhorn-10] Mehlhorn, Kurt; Sanders, Peter. Algorithms and Data Structures: The Basic Toolbox. Springer, 2008, p. 189. ISBN 978-3-642-09682-2.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]