TEMA 2: ESTRATEGIAS DE BÚSQUEDA NO INFORMADA

5 DE JUNIO 2014

ESTRATEGIAS DE BÚSQUEDA NO INFORMADA

INTRODUCCIÓN

El término significa que ellas no tienen información adicional acerca de los estados más allá de la que proporciona la  definición del problema dado  que ellas pueden hacer es generar los sucesores y  distinguir entre un estado objetivo de uno que no lo es. Las estrategias que saben si un estado no objetivo es <es mas prometedor> que otro se llaman búsqueda informada o BÚSQUEDA heurística; Todas las estrategias se distinguen  por el orden de expansión de los nodos.

Búsqueda primero en anchura

˜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.

Evaluación de la Eficiencia

1. No es completo, pues si entra en una rama infinita, el algoritmo no termina nunca.

2. No es optimo, pues devuelve la primera solución que encuentra, que no tiene por que ser la optima.

3. Complejidad en tiempo: O(bm)

4. Complejidad en espacio: O(bm) si para cada nodo expandimos todos sus descendientes o O(m) si expandimos los nodos uno a uno.

Búsqueda primero en profundidad

˜La búsqueda primero en profundidad siempre expande el nodo mas profundo en la frontera actual del Árbol de búsqueda.

˜Esta estrategia puede implementarse por la BÚSQUEDA-ARBOLES por una cola ultimo en entrar primero  en salir (LIFO), también conocida como una pila.

Evaluación de la Eficiencia

1. No es completo, pues si entra en una rama infinita, el algoritmo no termina nunca.

2. No es optimo, pues devuelve la primera solución que encuentra, que no tiene por que ser la optima.

3. Complejidad en tiempo: O(b m)

4. Complejidad en espacio: O(bm) si para cada nodo expandimos todos sus descendientes o O(m) si expandimos los nodos uno a uno.

Búsqueda de Costo Uniforme

Para cada nodo j se tiene su costo asociado desde el nodo inicial hasta dicho nodo j, calculado como

g(j) = g(i) + C[i, j] donde C[i, j] es el costo de aplicar un operador para pasar del nodo i al j.

Ahora la frontera es una cola ordenada seg ́n el coste, de menor a mayor. Por lo tanto, antes de llegar a la solución se estudiaran todos los nodos con menor coste que los nodos del camino optimo.

Evaluación de la Eficiencia

1. Es completo siempre que los costes sean positivos (en caso contrario el algoritmo podría    quedar en un bucle infinito, pues el costo del camino sera cada vez menor).

     

2. Complejidad en tiempo y espacio.

  

  Sea c∗ el costo de la solución  optima y sean todos los costos ci ≥ ε > 0. As ́ la complejidad en tiempo y espacio ∈ O (b(c*/ε ))

CONCLUSIONES

Los métodos de búsqueda no informada son esenciales cuando no se tiene idea de una solución a determinados problemas, en los que solo se tiene una información básica de parámetros que se le da al agente como conocimiento inicial.

El escoger un método dependerá de las condiciones del problema ya que cada uno tiene sus beneficios como desventajas.

BIBLIOGRAFIA

˜Russell, S. Norvig, P. 2004. INTELIGENCIA A HTXFKCIAI, UN ENFOQIJE MUDERNO.2 ed. PEARSON EDUCACIONS,.S A. Formato PDF. Pag. 67-88.