miércoles, 5 de septiembre de 2018

Ensayo Heuristicas


Heuristicas

- Heuristica Admisible 
Una heuristica admisible se utiliza para el costo que se necesita para llegar al estado de meta, se dice que la heuristica sera admisible solo en ciertos problemas en donde el costo que se encuentra siempre debe ser menor o igual que el costo minimo para llegar a la meta.

Como indicamos anteriormente es admisible si para cada nodo n, h(n) ≤ h *(n), donde h *(n) significa el costo verdadero para llegar al estado meta n.  Una heurística admisible nunca sobreestima el costo para llegar al estado objetivo y es óptima. El algoritmo de busqueda utilliza la uhueristica para enontrar una estimacion de una camino optimo hasta la meta desde el nodo actual.  


- Heuristica Monotona
Es una condicion que se aplica a la busqueda heuristica, se dice que una heuristica sera monotona si para n y sus sucesores n' el costo estimado para alcanzar el objetivo de n no sea mayor que el costo de obtener a n' sumado a costo para alcanzar el objetivo de n.
Esto se evidencia en la siguiente ecuacion
Monotonia

-Heuristica Consistente
 Las heuristicas consistentes son admisibles pero no todas las heuristicas adisbles son monotonas, para que una heuristica sea consistente se necesita que para todo los nodos n y sus sucesores n'  se cumple la siguiente ecuacion
Consistencia 
En donde  el costo estimado para alcanzar el objetivo desde n no sea mayor que el costo de obtener n' sumado al costo para alcanzar el objetivo desde n'.

Si h* es consistente, entonces también es optima, pero existen funciones heurísticas h* optimas que no son consistente.

-Heuristicas más informadas
 Esta permite hacer comparacion de heuristicas admisibles entre sí en cualquier estado n, evaliando cual es mas optima para encontrar la mejor solucion y cual es mas informada, es decir, si una búsqueda heurística es más informada que otra, al hacer uso en  A*, se expandirán menos nodos durante la búsqueda porque lo hará por profundidad, y habrá nodos sucesores del problema inicial que no tendrá en cuenta
 

Bibliografia

-http://andrclam.blogspot.com/2015/03/heursitica-monotona-y-admisible.html 
- https://ia301ud.wordpress.com/2017/03/10/heuristica/



 


No hay comentarios:

Publicar un comentario