Inteligencia Artificial

UNIVERSIDAD LAICA ELOY ALFARO DE MANABI

FACULTAD DE CIENCIAS INFORMATICAS

ASIGNATURA:

INTELIGENCIA ARTIFICIAL

TEMA/TITULO DEL TRABAJO:

“Búsqueda primero en anchura”

Integrantes:

Macias Intriago Fabian.

Reyes Mera Victor.

Rojas Urdánigo José.

Zambrano Zambrano Jorge.

Curso: 5 “A”

Profesor:

Ing. Fabricio Rivadeneira.

MANTA-MANABÍ-ECUADOR

2013-2014

BÚSQUEDA PRIMERO EN ANCHURA

La búsqueda primero en anchura es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expanden todos los sucesores del nodo raíz, después sus sucesores, etc. En general, se expanden todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel.

La búsqueda primero en anchura se puede implementar llamando a la BÚSQUEDA-ARBOLES con una frontera vacía que sea una cola primero en entrar primero en salir (FIFO). Asegurando que los nodos primeros visitados serán los primeros expandidos. En otras palabras, llamando a la BÚSQUEDA-ÁRBOLES (problema, COLA-FIFO ()) resulta una búsqueda primero en anchura. 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. El nodo objetivo más superficial no es necesariamente el óptimo.

Técnicamente, la búsqueda primero en anchura es óptima si el costo del camino es una función no decreciente de la profundidad del nodo (por ejemplo, cuando todas las acciones tienen el mismo coste).

En este caso, primero se expande el nodo raíz y luego todos los nodos generados por éste, luego sus sucesores y así sucesivamente.

Todos los nodos que están a profundidad se expanden antes que los nodos con profundidad d+1.

Para ver por qué no es siempre la estrategia a elegir tenemos que considerar la cantidad de tiempo y memoria que utiliza para completar una búsqueda.

Algoritmo:

 Si Abiertos = ( ), fin devolviendo fallo

 Abiertos←(n0); Cerrados←( )

 n←primer elemento de Abiertos; eliminar n de Abiertos y llevarlo a Cerrados; Suc←( )

 Si n es meta, fin con éxito, devolviendo el camino

 expandir n, colocando sus hijos en Suc, como hijos de n

 eliminar de Suc cualquier nodo cuyo estado ya esté asociado a algún nodo de Abiertos o Cerrados

 colocar los nodos de Suc al final de Abiertos

 Ir a 2

Si hay solución, es seguro que se encontrará mediante la búsqueda preferente por amplitud.

Si son varias soluciones, siempre encontrará primero el estado de meta más próximo (menos profundidad,

...