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. [1]
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 A * busque la función de evaluación (donde es 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 siguiente rompecabezas 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. [2]
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:
Garantía de optimalidad
Si se utiliza una heurística admisible en un algoritmo que, por iteración, progresa solo en la ruta que tiene el costo total esperado más bajo de varias rutas candidatas y termina en el momento en que cualquier ruta alcanza la meta aceptando esa ruta como la más corta (por ejemplo, en la búsqueda A * algoritmo ), este algoritmo terminará en la ruta más corta. Para ver por qué, simplemente considere que cualquier ruta en la que finalice el algoritmo solo avanzó porque su costo total esperado fue el más bajo de los candidatos. Para una heurística admisible, ninguno de los candidatos sobreestima sus costos, por lo que sus costos reales solo pueden ser mayores o iguales a los de la ruta aceptada. Finalmente, el costo total esperado es el costo real de una ruta que alcanza la meta porque la única heurística admisible para alcanzar la meta es cero.
Como ejemplo [3] de por qué la admisibilidad puede garantizar la optimización, 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 0100 0INICIO ---- O ----- OBJETIVO | |0 | | 100 | | O ------- O ------ O100 1100 1100
Así que claramente comenzaríamos visitando el nodo medio superior, 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 más bajo que el 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 forma, 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 coherentes son admisibles, no todas las heurísticas admisibles son coherentes.
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.
Referencias
- ^ Russell, SJ; Norvig, P. (2002). Inteligencia artificial: un enfoque moderno . Prentice Hall. ISBN 0-13-790395-2.
- ^ Korf, Richard E. (2000), "Progresos recientes en el diseño y análisis de funciones heurísticas admisibles" (PDF) , en Choueiry, Berthe Y .; Walsh, Toby (eds.), Abstraction, Reformulation, and Approximation: 4th International Symposium, SARA 2000 Horseshoe Bay, EE. UU., 26-29 de julio de 2000 Proceedings , 1864 , Springer, págs. 45–55, doi : 10.1007 / 3- 540-44914-0_3 , ISBN 978-3-540-67839-7, consultado el 26 de abril de 2010
- ^ "¿Por qué las heurísticas admisibles [ sic ] garantizan la optimización?" . algoritmo. Desbordamiento de pila . Consultado el 11 de diciembre de 2018 .