Heurística Consistente y Admisible

Como Russel y Norvig señalan en Artificial Intelligence: A Modern Approach (el libro de texto de IA más comúnmente utilizado), es difícil llegar a una heurística que sea admisible pero no consistente.

Obviamente, puede seleccionar valores para nodos en un gráfico de tal manera que la heurística que representan sea admisible pero no consistente. Este artículo de Felner et al tiene un buen ejemplo de las dos formas en que esto es posible, pero es un poco denso, así que voy a resumen:

• Esta heurística es inconsistente en c1 porque está dando un límite inferior (es decir, menos informativo) en el costo para llegar a la meta que su nodo padre. La estimación del costo de llegar a la meta a través del nodo padre es 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 del padre (5), más el costo de la ruta del padre (1), más estimación heurística en c1 (2)).
• Dado que este gráfico no está dirigido, esta heurística también es inconsistente en c2, porque 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 los 8 rompecabezas:

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

Sin embargo, usted podría llegar a una heurística diferente. Tal vez solo desee mirar la distancia de Manhattan (es decir, el número de cuadrados de distancia) del 1, el 2 y el 3 a las ubicaciones en las que se supone que están en el estado de meta. La heurística, aunque 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, quizás 5, 6 y 7. Y entonces digamos que la forma de calcular la heurística en cada nodo es seleccionando al azar uno de esos conjuntos (1,2 y 3) o (5, 6 y 7) y computando su distancia de Manhattan a sus ubicaciones de objetivo. Esta heurística es todavía admisible - solo puede subestimar o igualar el número de movimientos necesarios para llegar al estado de meta. Sin embargo, ya no es consistente - no hay una relación clara entre las estimaciones heurísticas en cada nodo.