Proyectorup

U N I V E R S I D A D P R I V A D A C É S A R V A L L E J O
FACULTAD DE INGENIERÍA
ESCUELA DE INGENIERÍA DE SISTESMAS


BUSQUEDAS INFORMADAS (HEURÍSTICAS)

Curso :INTELIGENCIA ARTIFICIAL

Alumnos :

* W. FERDINAND VÁSQUEZ TANTALEÁN

VII
CICLO :

2009 II

BÚSQUEDA INFORMADA: HEURÍSTICA
Proviene del griego “heuriskein” que significa descubrir o encontrar,un heurístico es una ayuda para guiar el proceso de búsqueda, en general con la utilización de heurísticos no siempre se van a conseguir resultados óptimos (la mejor solución), pero si van aconseguir resultados de buena calidad en media en un tiempo razonable.

Se utiliza en problemas complejos donde aparece el problema de la explosión combinatoria. En este tipo de problemas, los algoritmos debúsqueda exhaustiva tienen unos costes inaceptablemente altos (sólo son validos para problemas sencillos).

BÚSQUEDA PRIMERO EL MEJOR
* Búsqueda Voraz (Avara).
* Búsqueda A*.

*Búsqueda Voraz (avara):
Se trata de reducir al mínimo el costo estimado para alcanzar la meta o sea el nodo cuyo estado se considere como el más cercano a la meta será el expandido. Ese cálculo, en lamayoría de los casos, sólo puede ser estimado ya que no es posible obtener el costo real. La función para estimar el costo se denomina función heurística (h).

h(n)=Costo estimado de la ruta más baratadesde n a un estado meta

La búsqueda avara utiliza h para escoger cuál será el próximo nodo a expandir, desde el punto de vista formal h puede ser cualquier función, el único requisito es que h(n) =0 cuando n es el estado meta.
Clarifiquemos las ideas con un ejemplo, en el caso de viajar desde una ciudad a otra una buena función será la distancia que hay en línea recta desde las ciudades hastala meta.
Esta medida, aunque no es precisa, nos da una aproximación ya que cuando se construye una carretera se trata de minimizar las distancias (si no hay otros intereses)
Para un mejor...