Heurística admisible

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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 costo de alcanzar el objetivo, o sea, que en el punto actual la estimación del costo de alcanzar el objetivo nunca es mayor que el menor costo posible.

Algoritmos de busqueda[editar]

Una heurística admisible es usada para estimar el costo 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 costo estimado sea siempre menor o igual que el costo 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 costo mínimo que va desde el inicio hasta el objetivo y pasa por n.
  • g(n) es el costo del camino desde el inicio hasta n.
  • h(n) es el costo 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 costo de solucionar el problema es menor que el que realmente es. Como g(n) es el costo exacto de alcanzar n, tenemos como consecuencia inmediata que f(n) nunca sobreestima el costo 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[editar]

Tomando que:

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

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

Ejemplos[editar]

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:

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[editar]

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 esta vacía".

Se pueden generar tres problemas quitando una o ambas condiciones:

  1. Una ficha se puede mover desde la casilla A hasta la casilla B si A es adyacente a B.
  2. Una ficha se puede mover desde la casilla A hasta la casilla B si B está en blanco.
  3. 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[editar]

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':

h(n) \le c(n, A, n') + h(n')

Para problemas de busca en árbol, si una heurística admisible es usada, el algoritmo A* nunca devolverá un nodo objetivo subóptimo.

Referencias[editar]

Russell, S.J.; Norvig, P. (2002). Artificial Intelligence: A Modern Approach. Prentice Hall. ISBN 0-13-790395-2.

Temas relacionados[editar]