Heurística admisible

En informática , específicamente en algoritmos relacionados con la búsqueda de rutas , se dice que una función heurística es admisible si nunca sobreestima el costo de alcanzar el objetivo, es decir, el costo que estima para alcanzar el objetivo no es mayor que el costo mínimo posible desde el punto actual en la ruta. ^{[ 1 ]} En otras palabras, debe actuar como una cota inferior.

Está relacionado con el concepto de heurísticas consistentes . 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 informada . Para que una heurística sea admisible al problema de búsqueda, el costo estimado siempre debe ser menor o igual que el costo real de alcanzar el estado objetivo. El algoritmo de búsqueda utiliza la heurística admisible para encontrar una ruta óptima estimada hacia el estado objetivo desde el nodo actual. Por ejemplo, en la búsqueda A* la función de evaluación (donde ${\displaystyle n}$es el nodo actual) es:

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

dónde

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

${\displaystyle g(n)}$= el costo desde el nodo de inicio hasta el nodo actual

${\displaystyle h(n)}$= costo estimado desde el nodo actual hasta el objetivo.

${\displaystyle h(n)}$se calcula utilizando la función heurística. 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 una sobreestimación en${\displaystyle f(n)}$.

${\displaystyle n}$es un nodo

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

${\displaystyle h(n)}$es el costo indicado por${\displaystyle h}$alcanzar una meta desde${\displaystyle n}$

${\displaystyle h^{*}(n)}$es el costo óptimo para alcanzar un objetivo 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 mediante información de bases de datos de patrones que almacenan soluciones exactas a subproblemas del problema, o mediante el uso de métodos de aprendizaje inductivo .

Dos ejemplos diferentes de heurísticas admisibles se aplican al problema de los quince rompecabezas :

• distancia de Hamming
• 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 igual al 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 igual a la distancia de Hamming del rompecabezas.

La distancia de Manhattan de un rompecabezas se define como:

${\displaystyle h(n)=\sum _{\text{todas las fichas}}{\mathit {distancia}}({\text{ficha, posición correcta}})}$

Consideremos el siguiente rompecabezas en el que el jugador desea mover cada ficha de manera que los números queden ordenados. La distancia de Manhattan es una heurística admisible en este caso porque cada ficha deberá moverse al menos el número de casillas que la separan de su posición correcta. ^{[ 2 ]}

Los subíndices muestran la distancia de Manhattan para cada ficha. La distancia total de Manhattan para el rompecabezas mostrado es:

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

Si se utiliza una heurística admisible en un algoritmo que, por iteración, avanza únicamente por el camino de menor evaluación (coste actual + heurística) entre varios caminos candidatos, finaliza en el momento en que su exploración alcanza el objetivo y, fundamentalmente, cierra todos los caminos óptimos antes de finalizar (algo que es posible con el algoritmo de búsqueda A* si no se toman precauciones especiales ^{[ 3 ]} ), entonces este algoritmo solo puede finalizar en un camino óptimo. Para ver por qué, considérese la siguiente demostración por contradicción :

Supongamos que dicho algoritmo logró terminar en una ruta T con un costo real T _true mayor que la ruta óptima S con un costo real 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 < T _verdadero

_Evaluación de prueba ≤ _Evaluación de seguridad

Si nuestra heurística es admisible, se deduce que en este penúltimo paso T _eval = T _true porque cualquier aumento en el costo real debido a 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 una ruta más costosa que la óptima.

Como ejemplo, ^{[ 4 ]} digamos que tenemos los siguientes costos: (el costo por encima/por debajo de un nodo es la heurística, el costo en una arista es el costo real)

0 10 0 100 0 INICIO ---- O ----- META | | 0| |100 | | O ------- O ------ O 100 1 100 1 100

Así que claramente comenzaríamos visitando 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)}$igual a${\displaystyle 10+100+0=110}$. Entonces claramente elegiríamos los nodos inferiores uno tras otro, seguidos del objetivo actualizado, ya que todos tienen${\displaystyle f(n)}$inferior a la${\displaystyle f(n)}$del objetivo actual, es decir su${\displaystyle f(n)}$es${\displaystyle 100,101,102,102}$Así pues, aunque el objetivo era un candidato, no pudimos elegirlo porque aún existían mejores alternativas. De esta forma, una heurística admisible puede garantizar la optimalidad.

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

• Heurística consistente
• Función heurística
• Algoritmo de búsqueda