Heurística admisible

En ciencias de la computación, específicamente en algoritmos relacionados con búsqueda de caminos, se dice que una heurística (informática) es admisible si nunca sobreestima el coste de alcanzar el objetivo, o sea, que en el punto actual la estimación del coste de alcanzar el objetivo nunca es mayor que el menor coste posible.

Algoritmos de búsqueda

Una heurística admisible es usada para estimar el coste de alcanzar el estado objetivo en un algoritmo de búsqueda informada. Una heurística será admisible para cierto problema de búsqueda cuando el coste estimado sea siempre menor o igual que el coste mínimo de alcanzar el estado objetivo. El algoritmo de búsqueda usa la heurística para encontrar una estimación del camino óptimo hasta el objetivo desde el nodo actual. Por ejemplo, uno de los algoritmos de búsqueda más populares es el A* (en inglés A-Star Search). En este la función de evaluación para $n$ , donde $n$ es el nodo actual, es así:

$f(n)=g(n)+h(n)$

donde:

$f(n)$ es la función de evaluación, una estimación del camino de coste mínimo que va desde el inicio hasta el objetivo y pasa por $n$ .
$g(n)$ es el coste del camino desde el inicio hasta $n$ .
$h(n)$ es el coste estimado desde el nodo actual hasta el objetivo.

$h(n)$ es calculado usando una función heurística. Con una heurística no admisible, el algoritmo A* podría pasar por alto la solución óptima durante la búsqueda debido a una sobreestimación de $f(n)$ . Las heurísticas admisibles son por su naturaleza optimistas, porque ellas piensan que el coste de solucionar el problema es menor que el que realmente es. Como $g(n)$ es el coste exacto de alcanzar $n$ , tenemos como consecuencia inmediata que $f(n)$ nunca sobreestima el coste verdadero de la solución a través de $n$ . De estar $h(n)$ definida por una heurística admisible, el algoritmo de búsqueda A* devolverá una solución óptima.

Formulación

Tomando que:

$n$ es un nodo.
$h$ es una heurística.
$h(n)$ es el la estimación del coste mínimo para alcanzar el objetivo desde $n$ , aplicando $h$ .
$C(n)$ es el coste mínimo real para alcanzar el objetivo desde $n$ .

Decimos que $h$ es admisible si para todo $n$ , $h(n)\leq C(n)$ .

Ejemplos

Por ejemplo, si se quiere resolver el 15-puzle (o juego del 15) en la menor cantidad de pasos posible usando A*, es necesario emplear una heurística admisible. Hay una larga historia de tales heurísticas para el 15-puzle, aquí tenemos dos de las más comúnmente usadas:

Distancia de Hamming: el número de fichas que no están en su lugar.
Distancia Manhattan: la suma de las distancias desde la posición actual de cada ficha hasta su posición original.

Queda claro que la Distancia de Hamming es admisible, dado que el número total de movimientos para ordenar las fichas correctamente es al menos el número de fichas que no están en su lugar (si cada ficha no está en su posición original deberá ser movida al menos una vez). La Distancia Manhattan también será una heurística admisible porque cada ficha será movida el menos la cantidad de pasos entre ella misma y su posición original. Considere el siguiente rompecabezas:

4	6	3	8
7	12	9	14
15	13	1	5
2	10	11

la distribución de las distancias Manhattan para cada ficha quedaría así:

3	1	0	1
2	3	3	4
3	2	4	4
4	1	1

La distancia total de Manhattan para el puzle quedaría:

$h(n)=3+1+0+1+2+3+3+4+3+2+4+4+4+1+1=36$

Construcción

Una heurística admisible puede derivar de una versión simplificada del problema, o por información desde un patrón de base de datos que almacene la solución exacta de un problema, o usando aprendizaje inductivo. Por ejemplo, del 15-puzle visto anteriormente, podemos definir tres problemas más simples: La regla del juego original es "Una ficha se puede mover desde la casilla A hasta la casilla B si A es adyacente a B y B está vacía".

Se pueden generar tres problemas quitando una o ambas condiciones:

Una ficha se puede mover desde la casilla A hasta la casilla B si A es adyacente a B.
Una ficha se puede mover desde la casilla A hasta la casilla B si B está en blanco.
Una ficha se puede mover desde la casilla A hasta la casilla B.

De 1) podemos derivar la Distancia Manhattan, de 2) podemos derivar otra heurística conocida como La heurística de Gaschnig y de 3) podemos derivar la Distancia de Hamming.

La idea detrás del patrón de base de datos es almacenar los costos de las soluciones exactas de cada posible instancia de un sub-problema, en nuestro ejemplo las instancias de sub-problemas podrían ser 8 casillas y el espacio en blanco o 7 casilla y el espacio en blanco. Por ejemplo (1-2-3-4-5-6-7-8) y (9-10-11-12-13-14-15). Si las casillas seleccionadas no se repiten en dos sub-problemas (o dicho generalmente, no hay solapamiento en dos sub-problemas), podemos crear una heurística admisible que sea la suma de ambos costos almacenados en la base de datos. Usando esta heurística se resolvería el 15-puzzle en unos pocos milisegundos, el número de nodos generados se reduce en 10000 comparado con como cuando se usa la distancia Manhattan.

Notas

Si se tiene de una heurística admisible, la que mejor funcione va a ser la de mayor valor, o sea, la que mejor aproxime la solución óptima real sin sobrepasar su valor. De ahí si tenemos varias heurísticas admisibles y no sabemos cuál elegir, podemos crear una nueva que sea el máximo de todas las otras.

Mientras que todas las heurísticas consistentes son admisible, no todas las heurísticas admisibles son consistentes. Una heurística $h(n)$ es consistente si, para todo nodo $n$ y todo sucesor $n'$ de $n$ generado por cualquier acción A, el costo estimado de alcanzar el objetivo desde $n$ no es mayor que el costo de obtener $n'$ más el costo estimado de obtener el objetivo desde $n'$ :