Tema
Heurísticas admisibles y consistentes
- IA clásica
- Nivel intermedio
Una heurística es admisible cuando nunca sobreestima el coste real restante, y es consistente cuando cumple la desigualdad triangular h(n) <= c(n, a, n') + h(n') para todo sucesor n'.
Nombre en inglés
Admissible and consistent heuristics
Intuición
La admisibilidad es una promesa de optimismo, mientras que la consistencia es una promesa de optimismo que además no se contradice a sí misma paso a paso. Toda heurística consistente es admisible, pero no al revés. La forma habitual de construir una heurística admisible consiste en relajar el problema quitando restricciones y resolver esa versión más fácil, porque el coste óptimo de un problema relajado nunca supera al del problema real.
Fórmula
admisible cuando h(n) <= h*(n). consistente cuando h(n) <= c(n, a, n') + h(n'). h2 domina a h1 cuando h2 >= h1 en todo n
Ejemplo resuelto
En el rompecabezas de 8 fichas, la heurística h1 cuenta fichas fuera de su sitio y la heurística h2 suma las distancias de Manhattan de cada ficha hasta su posición final. Con 5 fichas descolocadas y distancias 1, 2, 1, 3 y 1, se obtiene h1 = 5 y h2 = 8. Ambas son admisibles porque cada movimiento coloca como mucho una ficha y la mueve una casilla. Como h2 >= h1 en todo estado, h2 domina a h1 y A estrella expande con h2 un subconjunto de los nodos que expandiría con h1.
Errores frecuentes
- Sumar dos heurísticas admisibles para obtener una más informada, ya que la suma sobreestima salvo que las heurísticas midan recursos disjuntos y ahí deja de ser admisible.
- Tratar admisible y consistente como sinónimos, error que se paga al usar búsqueda en grafos con cierre de nodos, donde solo la consistencia garantiza que el primer camino hallado a un estado sea el más barato.
- Usar la distancia de Manhattan en una rejilla que permite movimientos diagonales de coste 1, porque entonces la estimación supera al coste real y la heurística deja de ser admisible.
Ejercicio
Un nodo n tiene un sucesor n' con coste de arco 2. Se sabe que h(n) = 7 y h(n') = 4. Determina si la heurística puede ser consistente en ese par.
Ver la solución
La consistencia exige h(n) <= c(n, a, n') + h(n'), o sea 7 <= 2 + 4 = 6, desigualdad que no se cumple. La heurística es inconsistente en ese par, aunque todavía podría ser admisible si h(n) = 7 no supera el coste real desde n hasta la meta. En una búsqueda en grafos con cierre de nodos, esa inconsistencia obliga a reabrir nodos ya cerrados para no perder la optimalidad.
Respuesta: No, porque 7 es mayor que 6.