Download - Busqueda Informada Funcion Heuristica
-
ESCUELA SUPERIOR POLITCNICA AGROPECUARIA DE
MANAB MANUEL FLIX LPEZ
CARRERA INFORMTICA
SEMESTRE SPTIMO PERODO ABRIL-SEPT/2015
TEMA:
BUSQUEDA INFORMADA Y FUNCIN HEURSTICA
MATERIA:
INTELIGENCIA ARTIFICIAL II
AUTORA:
LUISA KATERINE FARIAS CHICA
FACILITADORA:
ING. HIRAIDA SANTANA
MISIN
Formacin de profesionales ntegros que conjuguen ciencia, tecnologa y valores en
su accionar, comprometidos con la sociedad en el manejo adecuado de programas
y herramientas computacionales de ltima generacin.
VISIN
Ser referente en la formacin de profesionales de prestigio en el desarrollo de
aplicaciones informticas y soluciones de hardware.
CALCETA, JUNIO 2015
-
Luego de haber tratado en capitulo pasado sobre la
bsqueda no informada nos pudimos dar cuenta que
su principal metas es encontrar soluciones de
problemas por medio del objetivo en cambio ahora le
vamos hablar acerca de la bsqueda informada la
cual (la que utiliza el conocimiento especfico del
problema ms all de la definicin del problema en s
mismo, estos bsqueda son muy eficaces ya que se
resuelven problemas en los cuales el coste del
camino es irrelevante, A continuacin le explicaremos
acerca de la funcin heurstica.
Obtener Conocimientos acerca de la bsqueda
informada y saber qu papel cumple la funcin
heurstica en dicha bsqueda.
-
BSQUEDA INFORMADA
Esta bsqueda es la que utiliza el conocimiento especfico
del problema ms all de la definicin del problema en s
mismo.La informacin sobre el espacio de estados puede
impedir a los algoritmos cometer un error en la oscuridad
HEURSTICA
La heurstica aparece bajo la forma de una funcin
de evaluacin basada en la informacin especfica
para el dominio o contexto relacionada con el
problema.
-
FUNSION HEURISTICA
Las funciones heursticas son criterios, mtodos o
principios para decidir cul de entre varias acciones
promete ser la mejor para alcanzar una determinada
meta.
El uso de heursticas nos permite convertir nuestra
bsqueda de una solucin en un proceso guiado de
ensayo y error.
En esta seccin, veremos heursticas para el 8 -puzle,
para que nos den informacin sobre la naturaleza de
las heursticas en general.
Informacin especificada aparte de la descripcin
del conocimiento. p.ej. Uso de una funcin heurstica
que evala la bondad de un estado del sistema:
f(estado) R.
No expandir trayectos que ya se sabemos que son
caros Funcin de evaluacin:
f(n) = g(n) + h(n) g(n) = costo hasta llegar a n
h(n) = costo estimado hasta la meta desde n
f(n) = costo total de ruta pasando por n hasta la meta
-
El 8 -puzle fue uno de los primeros problemas de
bsqueda heurstica. El objeto del puzle es deslizar las
fichas horizontalmente o verticalmente al espacio
vaco hasta que la configuracin empareje con la
configuracin Objetivo.
PROBLEMAS CON LA HEURSTICA
la heurstica suele ser poco certera - problema
abierto
valor de la actividad a un meta-nivel - problema
abierto
Puede no encontrar la mejor respuesta -
superado por algoritmo A*
ESTRATEGIAS IRREVOCABLES
En cada momento, slo mantenemos en memoria un
nico nodo, que incluye la descripcin completa del
sistema en ese momento:
o Se selecciona un operador R.
o Se aplica sobre el estado del sistema E, para
obtener un nuevo estado E = R(E).
o Se borra de memoria E y se sustituye por E.
-
APRENDIZAJE DE HEURSTICAS DESDE LA
EXPERIENCIA
Cada ejemplo se compone de un estado del camino
solucin y el costo real de la solucin desde ese
punto. En la implementacin de cada ejercicio se
puede utilizar un algoritmo de aprendizaje inductivo
para construir una funcin h(n) que pueda (con
suerte) predecir los costos solucin para otros estados
que surjan durante la bsqueda.
-
BUSQUEDA VORAZ PRIMERO EL MEJOR
Se explora exhaustivamente el grafo utilizando una
funcin heurstica para determinar el orden en que se
exploran los nodos:
Seleccionar el nodo E del grafo que tenga mayor
valor para la funcin heurstica.
Seleccionar un operador R aplicable sobre E.
Aplicar R, para obtener un nuevo nodo R(E).
Aadir el arco E R(E) al grafo
Repetir el proceso.
En conclusin como nos pudimos dar cuenta la
funcin heurstica cumple un papel muy importante
en la bsqueda informada es muy significativo
obtener conocimientos de la misma mientras
obtengas informacin incluida en la descripcin del
propio conocimiento que tenemos del problema para
poder comenzar en su elaboracin y as llegar al
objetivo propuesto con mucho xito y calidad y por lo
tanto notamos que para resolver un problema
-
eficiente es mejor utilizar la tcnica de bsqueda
informada.
Berzal, F. 2012. Bsqueda Heurstica. (En lnea). Consultado 05
Jun. de 2015. Formato: PDF. Consultado
http://elvex.ugr.es/decsai/iaio/slides/A5%20Heuristic%20Searc
h.pdf
Russell, S ; Peter, N; Lores , J. 2009. Artificial Intelligence: A
Modern Approach Evaluacin Heurstica. (En lnea).
Consultado 05 Jun. de 2015. Disponible en:
http://www.gedlc.ulpgc.es/docencia/lp/documentacion/GB
_Prolog.pdf.
Rich, E. 2000. Artificial Intelligence. (En lnea). Consultado 05
Jun. de 2015. Formato: PDF. Consultado http://elvex.ugr.es/
Elaine Rich
/iaio/slides/A5%20ArtificialIntelligence%20Search.pdf.
Russell, S. y Norvig, P. 2004. INTELIGENCIA ARTIFICIAL. UN
ENFOQUE MODERNO. PEARSON EDUCACION. 2 ed. Madrid.