Solución:
Está sobreestimando cuando la estimación de la heurística es más alta que el costo de la ruta final real. Estás subestimando cuando es más bajo (no tienes que subestimar, solo tienes que no sobreestimar; correcto las estimaciones están bien). Si los costos de los bordes de su gráfico son todos 1, entonces los ejemplos que proporcione proporcionarán sobreestimaciones y subestimaciones, aunque la distancia de coordenadas simples también funciona bien en un espacio cartesiano.
Sobreestimar no hace exactamente que el algoritmo sea “incorrecto”; lo que significa es que ya no tienes un heurística admisible, que es una condición para garantizar que A * produzca un comportamiento óptimo. Con una heurística inadmisible, el algoritmo puede terminar haciendo toneladas de trabajo superfluo examinando caminos que debería estar ignorando y posiblemente encontrando caminos subóptimos debido a explorarlos. Si eso realmente ocurre depende de su espacio problemático. Ocurre porque el costo de la ruta está ‘fuera de conjunto’ con el costo estimado, lo que esencialmente le da al algoritmo ideas erróneas sobre qué rutas son mejores que otras.
No estoy seguro de si lo habrá encontrado, pero es posible que desee consultar el artículo A * de Wikipedia. Menciono (y enlace) principalmente porque es casi imposible buscarlo en Google.
Del artículo de Wikipedia A *, la parte relevante de la descripción del algoritmo es:
El algoritmo continúa hasta que un nodo objetivo tiene una menor F valor que cualquier nodo en la cola (o hasta que la cola esté vacía).
La idea clave es que, con subestimación, A * solo dejará de explorar un camino potencial hacia la meta una vez que sepa que el costo total de la ruta excederá el costo de una ruta conocida hacia la meta. Dado que la estimación del costo de una ruta es siempre menor o igual que el costo real de la ruta, A * puede descartar una ruta tan pronto como el costo estimado exceda el costo total de una ruta conocida.
Con la sobreestimación, A * no tiene idea de cuándo puede dejar de explorar un camino potencial, ya que puede haber caminos con un costo real más bajo pero un costo estimado más alto que el mejor camino conocido actualmente hacia la meta.
Respuesta corta
La respuesta de @chaos es un poco engañosa en mi opinión (se debe resaltar)
Sobreestimar no hace exactamente que el algoritmo sea “incorrecto”; lo que significa es que ya no tiene una heurística admisible, que es una condición para que se garantice que A * producirá un comportamiento óptimo. Con una heurística inadmisible, el algoritmo pueden terminar haciendo toneladas de trabajo superfluo
como @AlbertoPL insinúa
Puede encontrar una respuesta más rápido sobrestimando, pero es posible que no encuentre el camino más corto.
Al final (además del óptimo matemático), la solución óptima depende en gran medida de si considera los recursos informáticos, el tiempo de ejecución, tipos especiales de “Mapas” / Espacios de estado, etc.
Respuesta larga
Como ejemplo, podría pensar en una aplicación en tiempo real en la que un robot llega más rápido al objetivo utilizando una heurística de sobreestimación porque la ventaja de tiempo al comenzar antes es mayor que la ventaja de tiempo al tomar el camino más corto pero esperando más tiempo para calcular esta solución.
Para darte una mejor impresión, te comparto algunos resultados ejemplares que creé rápidamente con Python. Los resultados provienen del mismo algoritmo A *, solo difiere la heurística. Cada nodo (celda de la cuadrícula) tiene bordes para los ocho vecinos, excepto las paredes. Costos de aristas diagonales sqrt (2) = 1.41
La primera imagen muestra las rutas devueltas del algoritmo para un caso de ejemplo simple. Puede ver algunas rutas subóptimas al sobrestimar las heurísticas (rojo y cian). Por otro lado, existen múltiples rutas óptimas (azul, amarillo, verde) y depende de la heurística cuál se encuentre primero.
Las diferentes imágenes muestran todos los nodos expandidos cuando se alcanza el objetivo. El color muestra el costo de ruta estimado usando este nodo (considerando también la ruta “ya tomada” desde el inicio hasta este nodo; matemáticamente es el costo hasta ahora más la heurística para este nodo). En cualquier momento, el algoritmo expande el nodo con el costo total estimado más bajo (descrito anteriormente).
1. Cero (azul)
- Corresponde al algoritmo de Dijkstra
- Nodos expandidos: 2685
- Longitud del camino: 89,669
2. A vuelo de pájaro (amarillo)
- Nodos expandidos: 658
- Longitud del camino: 89,669
- https://i.stack.imgur.com/75eFV.png
3. Ideal (verde)
- Camino más corto sin obstáculos (si sigue las ocho direcciones)
- Estimación más alta posible sin sobrestimar (de ahí “ideal”)
- Nodos expandidos: 854
- Longitud del camino: 89,669
- https://i.stack.imgur.com/VqMtF.png
4. Manhattan (rojo)
- El camino más corto sin obstáculos (si no se mueve en diagonal; en otras palabras: el costo de “moverse en diagonal” se estima en 2)
- Sobreestima
- Nodos expandidos: 562
- Longitud del camino: 92.840
- https://i.stack.imgur.com/gD9t4.png
5. A vuelo de pájaro por diez (cian)
- Sobreestima
- Nodos expandidos: 188
- Longitud del camino: 99,811
- https://i.stack.imgur.com/SZuFH.png