DOCUMENTACIÓ AMPLADA


Descripció

Característiques:

L'algorisme en amplada busca primer en els principis de solució d'una longitud donada abans d'avançar cap a unes de més llargues. L'ordre d'exploració de l'arbre és d'esquerra a dreta. Per cada node visitat, genera els seus fills i els escull un darrera l'altre. Si un node no té fills, agafa un germà.

Aquesta cerca és una bona opció si la profunditat de l'arbre és infinita o pràcticament infinita. Si busquem la "millor solució" i considerem que la millor és la que tingui menor nombre de passos, la cerca en amplada és força adient ja que busca per nivells.

D'altra banda, usar aquest algorisme és una pèrdua de temps quan les trajectòries condueixen a la solució en aproximadament la mateixa profunditat. I a més, no resulta una bona idea quan el factor de ramificació és gran.

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

Pseudocodi

Algorisme amplada (node node_inicial)

FiAlgorisme

/* El primer que entra és el primer que surt */

TAD cua ()

/* Crea una nova cua buida */

Funcio cua_buida (): cua

FiFuncio

/* Retorna CERT si la cua està buida */

Funcio buida (cua c): boolean

FiFuncio

/* Retorna el primer node de la cua */

Funcio primer (cua c): node

FiFuncio

/* Afegeix un node a la cua */

Funcio encuar_elem (cua p, node n): cua

FiFuncio

/* Treu el primer node de la cua */

Funcio desencuar (cua c): cua

FiFuncio

/* Afegeix els nodes de la cua c2 a la cua c1 */

Funcio encuar_cua (cua c1, cua c2): cua

FiFuncio

FiTAD

Inici Anterior