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

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