1.1.
INTRODUCCIÓN
MARCO
TEÓRICO
2.1. Estrategias De Búsquedas Informadas
Heurísticas
Como ya
he venido mencionando las búsquedas informadas son aquellas que poseen un
conocimiento previo para ¿que el agente pueda conocer el entorno en el que se
desenvolverá pero que hace especial a este tipo de búsquedas? A diferencia de
las búsquedas no informadas las informadas hacen uso de estrategias para poder
encontrar soluciones de manera más eficiente que las no informadas, una de
ellas es la utilización de la búsqueda primero el mejor la cual es un caso
particular de las búsquedas de árboles en donde se tenía que expandir un nodo
basado en una función de evaluación. Este tipo de búsqueda hace uso de una
función de evaluación en donde f(n) será el costo estimado del camino más
barato desde el nodo n hacia el nodo objetivo.
2.1. Búsqueda Voraz Primero El Mejor
Esta búsqueda es una derivación de la búsqueda primero
el mejor, la cual trata de expandir el nodo más cercano al objetivo para poder
encontrar una solución que lo conduzca hacia un estado objetivo, esta búsqueda
evalúa los nodos mediante una función heurística f(n)=h(n) la cual es un
componente clave de este tipo de algoritmos. La función de evaluación es la
encargada de devolver los valores de la expansión de los nodos en donde se
escoge el nodo que posea una mejor evaluación. Un defecto de este tipo de
búsqueda es que no tiene en cuenta el costo que tendrá n hasta llegar a su
objetivo.
Imagen 1: Búsqueda Voraz Primero el Mejor
2.1. Búsqueda A*
La búsqueda A* o búsqueda en estrella como se le
conoce es una de las estrategias de búsqueda más conocidas de la búsqueda
primero el mejor, esta trata de minimizar el costo total entre el nodo origen y
el nodo objetivo, a diferencia de la búsqueda voraz primero el mejor esta
búsqueda trata de buscar el costo del camino más barato de la solución mediante
la función de evaluación, la cual se representa de la siguiente manera f(n) =
g(n) + h(n) en donde g(n) será el costo del camino desde el nodo inicio hasta
el nodo n y h(n) será el costo estimado
del camino hacia el nodo objetivo. Esta estrategia de búsqueda en A* es óptima
si la función heurística cumple con las condiciones de admisibilidad y
consistencia.
Imagen 2: Búsqueda A*
2.1. Búsqueda Heurística Con Memoria Acotada
También conocida como búsqueda con memoria
simplificada, este tipo de búsqueda lo que busca es expandir los nodos de la
misma forma que lo hace la búsqueda en A* hasta el punto en que la memoria
disponible se llene, el objetivo de esto es hacer que no se puedan ingresar más
nodos al árbol, lo que hace este algoritmo es eliminar el peor nodo hoja, para
de esta manera volver hacia atrás el valor del nodo olvidado de forma que el
antepasado sepa cuál es la calidad del mejor camino en ese subárbol, si todos
los nodos descendientes de un nodo n son olvidados no sabremos porque camino ir
pero lo que si sabremos es el costo de ese camino. Este algoritmo es óptimo si
la solución es alcanzable si no devolverá la mejor solución.
CONCLUSIONES
Este tipo de búsquedas informadas nos han demostrado que son muy utiles encontrando una solución optimas en problemas de búsqueda, se pueden aplicar a agentes para que estos puedan desenvolverse en un ambiente conocido y como ya se conoce estas búsquedas usan una función de evaluación heurística que se encarga de devolver los valores de los nodos de expansión.
Este tipo de búsquedas informadas nos han demostrado que son muy utiles encontrando una solución optimas en problemas de búsqueda, se pueden aplicar a agentes para que estos puedan desenvolverse en un ambiente conocido y como ya se conoce estas búsquedas usan una función de evaluación heurística que se encarga de devolver los valores de los nodos de expansión.
BIBLIOGRAFIAS
Russell, S., Norvig, P. 2008. Inteligencia Artificial Un Enfoque Moderno. Segunda Edición. Pearson Education. España
No hay comentarios.:
Publicar un comentario