Heurística admisible - Admissible heuristic
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 la meta, es decir, el costo que estima para alcanzar la meta no es mayor que el costo más bajo posible de la actual. punto en el camino.
Algoritmos de búsqueda
Se utiliza una heurística admisible para estimar el costo de alcanzar el estado objetivo en un algoritmo de búsqueda informado . Para que una heurística sea admisible para el problema de búsqueda, el costo estimado siempre debe ser menor o igual al costo real de alcanzar el estado objetivo. El algoritmo de búsqueda utiliza la heurística admisible para encontrar una ruta óptima estimada al estado objetivo desde el nodo actual. Por ejemplo, en la búsqueda A *, la función de evaluación (donde está el nodo actual) es:
dónde
- = la función de evaluación.
- = el costo desde el nodo inicial hasta el nodo actual
- = costo estimado desde el nodo actual hasta la meta.
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 .
Formulación
- es un nodo
- es una heurística
- es el costo indicado por para alcanzar una meta desde
- es el costo óptimo para alcanzar una meta desde
- es admisible si,
Construcción
Una heurística admisible puede derivarse 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 .
Ejemplos de
Dos ejemplos diferentes de heurísticas admisibles se aplican al problema de los quince acertijos :
La distancia de Hamming es el número total de fichas extraviadas. Está claro que esta heurística es admisible ya que el número total de movimientos 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 costo (número de movimientos) para la meta (un rompecabezas ordenado) es al menos la distancia de Hamming del rompecabezas.
La distancia de Manhattan de un rompecabezas se define como:
Considere el rompecabezas a continuación en el que el jugador desea mover cada ficha de manera que los números estén ordenados. La distancia de Manhattan es una heurística admisible en este caso porque cada mosaico tendrá que moverse al menos el número de puntos entre él y su posición correcta.
| 4 3 | 6 1 | 3 0 | 8 1 |
| 7 2 | 12 3 | 9 3 | 14 4 |
| 15 3 | 13 2 | 1 4 | 5 4 |
| 2 4 | 10 1 | 11 1 |
Los subíndices muestran la distancia de Manhattan para cada mosaico. La distancia total de Manhattan para el rompecabezas que se muestra es:
Prueba de optimalidad
Si se utiliza una heurística admisible en un algoritmo que, por iteración, progresa solo en la ruta de evaluación más baja (costo actual + heurística) de varias rutas candidatas, termina en el momento en que su exploración alcanza la meta y, lo que es más importante, nunca cierra todas las rutas óptimas antes. terminando (algo que es posible con el algoritmo de búsqueda A * si no se tiene especial cuidado), entonces este algoritmo solo puede terminar en una ruta óptima. Para ver por qué, considere la siguiente prueba por contradicción :
Suponga que tal algoritmo logró terminar en una ruta T con un costo real T verdadero mayor que la ruta óptima S con un costo real S verdadero . Esto significa que antes de terminar, el costo evaluado de T era menor o igual al costo evaluado de S (o de lo contrario se habría elegido S). Denote estos costos evaluados T eval y S eval respectivamente. Lo anterior se puede resumir de la siguiente manera,
- S verdadero < T verdadero
- T eval ≤ S eval
Si nuestra heurística es admisible, se deduce que en este penúltimo paso T eval = T verdadero porque cualquier aumento en el 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 verdadero, lo que combinado con las desigualdades anteriores nos da T eval < T verdadero y más específicamente T eval ≠ T verdadero . Como T eval y T true no pueden ser iguales y desiguales, 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, digamos que tenemos los siguientes costos: (el costo por encima / por debajo de un nodo es la heurística, el costo en un borde es el costo real)
0 10 0 100 0 START ---- O ----- GOAL | | 0| |100 | | O ------- O ------ O 100 1 100 1 100
Entonces, claramente, comenzaríamos visitando el nodo superior medio, ya que el costo total esperado, es decir , es . Entonces el objetivo sería un candidato, con igual a . Luego, elegiríamos claramente los nodos inferiores uno tras otro, seguidos del objetivo actualizado, ya que todos tienen un valor inferior al del objetivo actual, es decir, su es . Entonces, aunque el objetivo era un candidato, no pudimos elegirlo porque todavía había mejores caminos por ahí. De esta manera, una heurística admisible puede garantizar la optimización.
Sin embargo, tenga en cuenta que aunque una heurística admisible puede garantizar la optimización final, no es necesariamente eficiente.
Notas
Si bien todas las heurísticas consistentes son admisibles, no todas las heurísticas admisibles son consistentes.
Para problemas de búsqueda de árbol, si se utiliza una heurística admisible, el algoritmo de búsqueda A * nunca devolverá un nodo objetivo subóptimo.