Heurística admisible

En informática, en concreto en algoritmos relacionados con la búsqueda de rutas, se dice que una función heurística es admisible si nunca sobreestima el coste de alcanzar la meta, es decir, el coste que estima para alcanzar la meta no es superior al coste más bajo posible desde el punto actual de la ruta. En otras palabras, debería actuar como un límite inferior.

Está relacionado con el concepto de heurística consistente. Si bien todas las heurísticas consistentes son admisibles, no todas las heurísticas admisibles son consistentes.

Una heurística admisible se utiliza para estimar el costo de alcanzar el estado objetivo en un algoritmo de búsqueda informado. Para una heurística para ser admisible al problema de búsqueda, el costo estimado siempre debe ser inferior o igual al costo real de alcanzar el estado de meta. El algoritmo de búsqueda utiliza la heurística admisible para encontrar una estimación camino óptimo al estado de gol desde el nodo actual. Por ejemplo, en A* busque la función de evaluación (donde ${\displaystyle n}$ es el nodo actual) es:

${\displaystyle f(n)=g(n)+h(n)}$

donde

${\displaystyle f(n)}$ = la función de evaluación.

${\displaystyle g(n)}$ = el costo del nodo inicial al nodo actual

${\displaystyle h(n)}$ = costo estimado del nodo actual a la meta.

${\displaystyle h(n)}$ se calcula utilizando la heurística función. Con una heurística no admisible, el algoritmo A* podría pasar por alto la solución óptima a un problema de búsqueda debido a un sobreestimación ${\displaystyle f(n)}$.

${\displaystyle n}$ es un nodo

${\displaystyle h}$ es una heurística

${\displaystyle h(n)}$ costo indicado por ${\displaystyle h}$ alcanzar un objetivo desde ${\displaystyle n}$

${\displaystyle h^{*}(n)}$ es el coste óptimo para alcanzar una meta desde ${\displaystyle n}$

${\displaystyle h(n)}$ es admisible si, ${\displaystyle \forall n}$

${\displaystyle h(n)\leq h^{*}(n)}$

Se puede derivar una heurística admisible a partir de una versión relajada del problema, o de información de bases de datos de patrones que almacenan soluciones exactas a subproblemas del problema, o utilizando métodos de aprendizaje inductivo.

Se aplican dos ejemplos diferentes de heurísticas admisibles al problema de los quince acertijos:

• Hamming distance
• Distancia a Manhattan

La distancia de Hamming es el número total de fichas mal colocadas. Es evidente que esta heurística es admisible, ya que el número total de movimientos necesarios para ordenar las fichas correctamente es al menos el número de fichas mal colocadas (cada ficha que no está en su lugar debe moverse al menos una vez). El coste (número de movimientos) para alcanzar el objetivo (un rompecabezas ordenado) es al menos la distancia de Hamming del rompecabezas.

La distancia de Manhattan de un rompecabezas se define como:

${\displaystyle h(n)=\sum _{\text{all tiles}{\mathit {distance}({\text{tile, correct position}})}$

Considere el siguiente rompecabezas en el que el jugador desea mover cada ficha de modo que los números estén ordenados. La distancia de Manhattan es una heurística admisible en este caso porque cada ficha deberá moverse al menos la cantidad de puntos que hay entre ella y su posición correcta.

Los subíndices muestran la distancia de Manhattan para cada pieza. La distancia total de Manhattan para el rompecabezas que se muestra es:

${\displaystyle h(n)=3+1+0+1+2+3+3+3+4+4+4+1+1=36}$

Si se utiliza una heurística admisible en un algoritmo que, por iteración, avanza sólo por el camino de menor evaluación (costo actual + heurística) de varios caminos candidatos, termina en el momento en que su exploración alcanza el objetivo y, fundamentalmente, nunca cierra todos los caminos óptimos antes de terminar (algo que es posible con el algoritmo de búsqueda A* si no se tiene especial cuidado), entonces este algoritmo sólo puede terminar en un camino óptimo. Para ver por qué, considere la siguiente prueba por contradicción:

Supongamos que dicho algoritmo logró terminar en una ruta T con un costo verdadero T_true mayor que la ruta óptima S con un costo verdadero S_true. Esto significa que antes de terminar, el costo evaluado de T era menor o igual que el costo evaluado de S (de lo contrario, se habría elegido S). Denotemos estos costos evaluados como T_eval y S_eval respectivamente. Lo anterior se puede resumir de la siguiente manera:

S_verdadero c) T_verdadero

T_eval ≤ S_eval

Si nuestra heurística es admisible, se deduce que en este penúltimo paso T_eval = T_true porque cualquier aumento del costo verdadero por la heurística en T sería inadmisible y la heurística no puede ser negativa. Por otro lado, una heurística admisible requeriría que S_eval ≤ S_true lo que combinado con las desigualdades anteriores nos da T_eval < T_true y más específicamente T_eval ≠ T_true. Como T_eval y T_true no pueden ser iguales y desiguales a la vez, nuestra suposición debe haber sido falsa y, por lo tanto, debe ser imposible terminar en un camino más costoso que el óptimo.

A modo de ejemplo, supongamos que tenemos los siguientes costos: (el costo por encima o por debajo de un nodo es la heurística, el costo en un borde es el costo real)

 0 10 0 100 0
START...
Silencio
0 sometidas a la práctica
Silencio
O... O... O
100 1 100

Así que claramente empezaríamos a visitar el nodo medio superior, ya que el costo total esperado, es decir. ${\displaystyle f(n)}$, es ${\displaystyle 10+0=10}$. Entonces el objetivo sería un candidato, con ${\displaystyle f(n)}$ iguales ${\displaystyle 10+100+0=110}$. Entonces claramente escogeríamos los nodos inferiores uno tras otro, seguido por el objetivo actualizado, ya que todos han ${\displaystyle f(n)}$ inferior a la ${\displaystyle f(n)}$ de la meta actual, es decir, su ${\displaystyle f(n)}$ es ${\displaystyle 100,101,102,102}$. Así que a pesar de que el objetivo era un candidato, no podíamos elegir porque todavía había mejores caminos por ahí. De esta manera, una heurística admisible puede garantizar la optimización.

Sin embargo, cabe señalar que, si bien una heurística admisible puede garantizar la optimalidad final, no es necesariamente eficiente.

• Heurística persistente
• Función heurística
• algoritmo de búsqueda