DOCUMENTACIÓ PROFUNDITAT


Descripció

Característiques: Per a trobar la solució l'algorisme agafa un dels fills de cada node que visita i avança a partir d'aquest fill. Les altres alternatives del mateix nivell les ignora mentre hi hagi possibilitats d'avançar des de la selecció original. Quan es troba en un node sense fills, diem que està en un carreró sense sortida i aleshores ha d'escollir un germà del node actual. Si no n'hi hagués cap, ha de pujar al nivell anterior. D'aquesta manera aconsegueix un ordre d'exploració de l'arbre de dalt a baix.

La cerca en profunditat és una bona opció quan es té la confiança de que totes les solucions parcials arriben a carrerons sense sortida o es tornen completes després d'un nombre raonable de passos. D'altra banda, és una mala idea triar-la quan hi ha trajectòries molt llargues (o infinitament llargues), quan no s'arriba a carrerons sense sortida o els principis de solució no es tornen complets.

Exemple d'ordre d'exploració i evolució de la pila de nodes:

Pseudocodi

Algorisme profunditat (node node_inicial) FiAlgorisme


/* L'ultim que entra es el primer que surt */
TAD pila ()
/* Crea una nova pila buida */
Funcio pila_buida (): pila
FiFuncio

/* Retorna CERT si la pila està buida */
Funcio buida (pila p): boolean FiFuncio

/* Retorna el node del cim de la pila */
Funcio cim (pila p): node
FiFuncio

/* Apila un node a la pila */
Funcio apilar_elem (pila p, node n): pila
FiFuncio

/* Treu el node del cim de la pila */
Funcio desapilar (pila p): pila
FiFuncio

/* Apila els nodes de la pila p2 a la pila p1 */
Funcio apilar_pila (pila p1, pila p2): pila
FiFuncio

FiTAD

Inici Anterior