• Author / Uploaded
• daniel gaviria collazos

Citation preview

Búsqueda No informada INTELIGENCIA ARTIFICIAL

Búsqueda en Amplitud La búsqueda en anchura o amplitud explora el espacio de búsqueda haciendo un recorrido por niveles, de manera que un nodo se visita solamente cuando todos sus predecesores y sus hermanos anteriores en orden de generación ya se han visitado.  Para obtener este algoritmo la estructura de datos que utiliza la lista de abiertos debe tener el comportamiento de una cola. Esta estructura permite que el algoritmo general visite los nodos en amplitud.

Algoritmo Busqueda General Est_abiertos . insertar (Estado inicial ) Actual= Est_abiertos . primero () mientras no es_final ?( Actual ) y no Est_abiertos . vacia ?() hacer Est_abiertos . borrar_primero () Est_cerrados . insertar ( Actual ) Hijos= generar_sucesores ( Actual )

Hijos= tratar_repetidos ( Hijos , Est_cerrados , Est_abiertos ) Est_abiertos . insertar ( Hijos ) Actual= Est_abiertos . primero ()

fmientras fAlgoritmo

Características COMPLEJIDAD Completitud

El algoritmo siempre encuentra la solución siempre y cuando exista.

Complejidad Temporal

El costo es exponencial respecto al factor de ramificación y la profundidad de la solución O(rp).

Complejidad Espacial

El coste es exponencial respecto al factor de ramificación y la profundidad de la solución O(rp).

Optimalidad

La solución que se encuentra es óptima en número de niveles desde la raíz

Búsqueda en profundidad La búsqueda en profundidad intenta seguir un camino hasta la mayor profundidad posible, retrocediendo cuando encuentra el ultimo nodo y retomando la última posibilidad de elección disponible. Para obtener este algoritmo la estructura de datos que utiliza para la lista de abiertos debe comportarse como una pila. Esta estructura permite que el algoritmo general visite los nodos en el orden de profundidad.

Algoritmo Busqueda General Est_abiertos . insertar (Estado inicial ) Actual= Est_abiertos . primero () mientras no es_final ?( Actual ) y no Est_abiertos . vacia ?() hacer Est_abiertos . borrar_primero () Est_cerrados . insertar ( Actual ) Hijos= generar_sucesores ( Actual )

Hijos= tratar_repetidos ( Hijos , Est_cerrados , Est_abiertos ) Est_abiertos . insertar ( Hijos ) Actual= Est_abiertos . primero ()

fmientras fAlgoritmo

Características COMPLEJIDAD Completitud

El algoritmo no siempre encuentra la solución

Complejidad Temporal

El costo es exponencial respecto al factor de ramificación y la profundidad de la solución O(rp).

Complejidad Espacial

El coste es exponencial respecto al factor de ramificación y la profundidad de la solución O(rp).

Optimalidad

La solución que se encuentra es óptima en número de niveles desde la raíz