Vamos a presentar dos conceptos importantes para las funciones heurísticas. El primero se denomina "admisibilidad". Vamos a decir que una función heurística es admisible cuando ésta no sobreestima. Esto quiere decir que el valor de la función heurística es menor o igual que el costo real a la meta. En este ejemplo tenemos cuatro estados, "A", "B", "C" y "D". En las aristas están anotados los costos y tenemos también ahí, para los nodos "C" y "D", la función heurística. La función heurística de "C" es igual a tres y la de "D" es igual a uno. Podemos ver que en ambos casos la función heurística está por debajo del valor real a la meta, en este caso, la meta es "B". Entonces, esta heurística es admisible. Si utilizamos esa heurística y calculamos la función "f" que utiliza A estrella, podemos ver que la "f" de "C" nos da "1+3=4" y la "f" de "D" nos da "2+1=3". Entonces, A estrella va a preferir expandir primero el nodo "D" y ésta es una buena decisión. Ahora vamos a ilustrar qué pasa si la heurística no es admisible. Hemos cambiado aquí la heurística de "D", ahora es tres. Si ahora es tres, vemos que sobreestima el valor del costo real, que era dos. Si utilizamos esa heurística para calcular "f", vemos que "f" de "C" va a ser la misma, es igual a cuatro, pero "f" de "D" ahora va a ser "3+2", que nos da cinco. Esto significa que al sacar de la agenda va a salir primero el nodo "C". Esto nos puede llevar a que no encontremos la solución óptima, esta va a ser una ruta más larga. El siguiente concepto que vamos a presentar es el de "monotonicidad o "consistencia". Decimos que una heurística es consistente si para cada sucesor de todo vértice en el grafo, la heurística del vértice es menor o igual que la suma del costo de la transición del vértice al sucesor, más la heurística del sucesor. En este ejemplo, la heurística cumple con la definición de monotonicidad. Primero, vamos a analizar la ruta que va a través de "C", desde "A" hasta "B", y vemos que el vértice "A" tiene una heurística de tres. Esto debe ser menor que el costo de la transición al sucesor. En este caso, el sucesor es "C", y costo de la transición es uno, sumada con el costo de la heurística de "C", en este caso, dos. Entonces, la suma de esas dos cantidades es tres y eso es igual a la heurística del nodo "A". Si analizamos la ruta a través de "D", algo similar sucede. El costo ahí es dos, de la transición, y el costo de la heurística es uno. También da tres, entonces, en ambos casos es igual. Por lo tanto, es monotónica. Hemos modificado el ejemplo para ilustrar una heurística no monotónica. En esta, "h" de "A", la heurística de A, es igual a cuatro, y ahora vemos que ya no se cumple que esta sea menor que la suma de las cantidades de la costa de la transición más la heurística del sucesor. En este caso, esa suma nos daba tres. Lo que pasa, entonces, es que si calculamos la función "f", la función "f" para "A" va a ser mayor que la función "f" para "C", lo cual es no monotónico porque, en lugar de crecer, conforme avanzamos en la profundidad y nos acercamos a la meta, la función "f" decreció para el sucesor. Adicionalmente, vamos a señalar que la admisibilidad de una heurística está implicada si la heurística es consistente. Vamos a comenzar analizando la memoria. Los requerimientos de memoria del algoritmo son exponenciales en la profundidad del nodo meta. Esto es el algoritmo es "O", "b" elevado a la "d". El segundo de los criterios que vamos a analizar es el tiempo. En este caso, también se requiere "O", "b" elevado a la "d", pero hay que agregar la complejidad de extraer el mínimo de la estructura de datos, que es logarítmica en el tamaño de la estructura. El tercer aspecto a evaluar es la calidad de la solución. El algoritmo A estrella nos va a entregar la solución óptima siempre que la heurística sea admisible y monotónica. El cuarto aspecto es la completez y siempre que la meta sea alcanzable desde el estado inicial, el algoritmo es completo.
