En ciencias de la computación, específicamente en algoritmos relacionados con búsqueda de caminos, se dice que una heurística es admisible cuando nunca sobreestima el coste de alcanzar el objetivo, o sea, que en el punto actual la estimación del coste de alcanzar el objetivo nunca es mayor que el menor coste posible.
Una heurística admisible es usada para estimar el coste 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 coste estimado sea siempre menor o igual que el coste 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.
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
definida por una heurística admisible, el algoritmo de búsqueda A* devolverá una solución óptima.
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 al menos la cantidad de pasos entre ella misma y su posición original.
Considere el siguiente rompecabezas: la distribución de las distancias Manhattan para cada ficha quedaría así: La distancia total de Manhattan para el puzle quedaría:
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 está vacía".
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.
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.
generado por cualquier acción A, el costo estimado de alcanzar el objetivo desde
no es mayor que el costo de obtener
más el costo estimado de obtener el objetivo desde
Para problemas de busca en árbol, si una heurística admisible es usada, el algoritmo A* nunca devolverá un nodo objetivo subóptimo.
Artificial Intelligence: A Modern Approach.