2.2.1 Breadth-first search (búsqueda a lo ancho)

Explora progresivamente en capas del grafo de misma profundidad.

La forma de implementarlo es poner los sucesores de cada nodo al final de una cola o agenda, por lo que OPEN (lista de nodos por explorar) se implementa como un stack.

Tabla 2.2: Algoritmo Breadth-first

Breadth-first es completo (encuentra una solución si existe) y óptimo (encuentra la más corta) si el costo del camino es una función que no decrece con la profundidad del nodo.

Pero requiere de mucha memoria. Básicamente tiene que guardar la parte completa de la red que está explorando.

Si se tiene un factor de arborecencia de $b$ y la meta está a profundidad $d$, entonces el máximo número de nodos epandidos antes de encontrar una solución es: $1 + b + b^2 + b^3 + \ldots + b^d$

Tabla 2.3: Requerimientos de tiempo y memoria para breadth-first. Factor de arborecencia = 10; 1,000 nodos/sec; 100 bytes/nodo.

Profund.	Nodos	Tiempo	Memoria
0	1	1 miliseg.	100 bytes
2	111	.1 seg.	11 kilobytes
4	11,111	11 seg.	1 megabyte
6	10$^{6}$	18 min.	111 megabytes
8	10$^{8}$	31 hr.	11 gigabytes
10	10$^{10}$	128 días	1 terabyte
12	10$^{12}$	35 años	111 terabytes
14	10$^{14}$	3500 años	11,111 terabytes

Los requerimientos de memoria es un problema grande para breadth-first.

También el tiempo es un factor importante. Básicamente problemas de búsqueda de complejidad exponencial no se pueden resolver, salvo para sus instancias más pequeñas.