search - mejor - Heurística consistente y admisible

heuristica manhattan 8 puzzle (2)

Cualquier heurística consistente también es admisible. ¿Pero cuándo es admisible una heurística pero no constante (monótona)?

Proporcione un ejemplo en el que este es el caso.

Como señalan Russel y Norvig en Inteligencia Artificial: Un Enfoque Moderno (el libro de texto de Inteligencia Artificial más utilizado), es un desafío encontrar una heurística que sea admisible pero no consistente.

Obviamente, puede seleccionar valores para nodos en un gráfico de modo que la heurística que representan sea admisible pero no consistente. Este documento de Felner et al. Tiene un buen ejemplo de las dos formas en que esto es posible, pero es un poco denso, así que resumiré:

Esta heurística es inconsistente en c1 porque está dando un límite inferior (es decir, menos informativo) más bajo en el costo para llegar a la meta que su nodo padre. El costo estimado de llegar a la meta a través del nodo padre es de al menos 10 (porque el costo de la ruta a p es 5 y la estimación heurística en p también es 5). El costo estimado para llegar a la meta a través de c1 , sin embargo, es solo 8 (costo de padre (5), más costo de camino de padre (1), más estimación heurística en c1 (2)).
Como este gráfico no está dirigido, esta heurística también es inconsistente en c2 , ya que pasar de c2 a p tiene el mismo problema que el anterior.

Felner et al también proporcionan algunos ejemplos concretos de una heurística admisible pero inconsistente. Considere el problema de 8 acertijos:

En este rompecabezas hay 8 fichas deslizantes numeradas 1-8, y un espacio vacío. Las fichas comienzan fuera de servicio (como en la imagen de la izquierda). El objetivo es llevar el rompecabezas al estado que se muestra arriba a la derecha exclusivamente deslizando las fichas en el espacio vacío. La heurística clásica para este problema (la distancia de Manhattan de cada azulejo a la ubicación donde se supone que debe estar) es admisible y consistente.

Sin embargo, podría llegar a una heurística diferente. Tal vez solo quiera ver la distancia de Manhattan (es decir, el número de casillas de distancia) de 1, 2 y 3 en las ubicaciones en las que se supone que están en el estado objetivo. La heurística, aunque es menos informativa que la distancia de Manhattan de todas las fichas, sigue siendo admisible y consistente.

Pero digamos que eliges un grupo adicional de cuadrados, tal vez 5, 6 y 7. Y entonces digamos que la forma en que calculas la heurística en cada nodo es seleccionando aleatoriamente uno de esos conjuntos (1,2, y 3) o (5, 6 y 7) y calculando su distancia de Manhattan a sus ubicaciones de objetivo. Esta heurística sigue siendo admisible : solo puede subestimar o igualar la cantidad de movimientos necesarios para llegar al estado objetivo. Sin embargo, ya no es consistente , no hay una relación clara entre las estimaciones heurísticas en cada nodo.

Hace tiempo que murió, pero daré mi granito de todos modos. Creo que, de lejos, la forma más fácil de pensar esto es que una heurística admisible dice que no se puede sobrepasar cuando se llega a un nodo de objetivo definido en particular, mientras que una heurística consistente dice que no se puede rebasar cuando se llega a CUALQUIER nodo. Esto hace que las relaciones sean claras: dado que el nodo objetivo es un nodo, es admisible una heurística consistente. Pero como admisible solo garantiza esta propiedad para un nodo, admisible no implica consistencia.