Búsqueda primero en

AnchuraAna K. Paz A.

Luis E. Cuenca H.

Definición:

La Búsqueda Primero en Anchura es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expande todos los sucesores del nodo raíz, después sus sucesores, etc.

Se expanden todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel.

Implementación:

La búsqueda primero en anchura se puede implementar con la Búsqueda de Árboles con una frontera vacía que sea una cola (FIFO)

La cola FIFO pone todos los nuevos sucesores generados al final de la cola, lo que significa que los nodos más superficiales se expanden antes que los nodos más profundos.

Evaluación de la Búsqueda Primero en Anchura

Completa: Si el nodo objetivo más superficial está en una cierta profundidad finita d, se lo encontrará luego de expandir los nodos más superficiales, siempre que el factor de ramificación b sea finito.

Óptima: Es óptimo si el coste del camino es una función no decreciente de la profundidad del nodo.

Evaluación de la Búsqueda Primero en Anchura

Cantidad de Tiempo y Memoria:

b = estado con b sucesores d = profundidad

= nodos en el nivel d +1

Cada nodo debe permanecer en memoria, porque o es parte de la frontera o es un antepasado de un nodo de la frontera.

11...32 dbObdb

dbbbb

bdb 1

Evaluación de la Búsqueda Primero en Anchura

Complejidad en el Espacio: Igual a la complejidad en tiempo, más un nodo para la raíz.

Una tabla de ejemplo sería para:b = 10d = diferentes10.000 nodos/segundo1.000 = bytes/segundo

Profundidad Nodos Tiempo Memoria

2 1.100 11 seg. 1 megabyte

4 111.100 11 seg. 106 megabytes

6 107 19 minutos 10 gigabytes

8 109 31 horas 1 terabyte

10 1011 129 días 101 terbytes

12 1013 35 años 10 petbytes

14 1015 3 .523 años 1 exabyte

Consideraciones:

1. Debemos preocuparnos más por la memoria que por el tiempo de ejecución.

2. Los requisitos de tiempo son un factor importante.

Los problemas de búsqueda de complejidad exponencial no pueden resolverse por métodos sin información, salvo casos pequeños.

Algoritmo:

Bibliografía:

Preguntas ??????

GraciasAna K. Paz A.

Luis E. Cuenca H.