Haz todo lo posible por interpretar el código correctamente previamente a adaptarlo a tu trabajo si ttienes algo que aportar puedes comentarlo.
Solución:
Está sobrestimando cuando la estimación de la heurística es más alta que el costo real de la ruta final. 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 borde de su gráfico son todos 1, entonces los ejemplos que brinde proporcionarán sobreestimaciones y subestimaciones, aunque la distancia de coordenadas simple también funciona de maravilla en un espacio cartesiano.
Sobreestimar no hace exactamente que el algoritmo sea “incorrecto”; lo que significa es que ya no tienes 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 ignorar, 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 confusas sobre qué rutas son mejores que otras.
No estoy seguro de si lo habrá encontrado, pero es posible que desee consultar el artículo de Wikipedia A*. 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).
Él key La idea es que, con la 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 siempre es 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 actualmente conocido 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 garantizar que A* produzca un comportamiento óptimo. Con una heurística inadmisible, el algoritmo puede terminar haciendo toneladas de trabajo superfluo
como @AlbertoPL está insinuando
Puede encontrar una respuesta más rápido sobreestimando, 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, los 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 esperar más para calcular esta solución.
Para darle una mejor impresión, 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 cuadrícula) tiene bordes para los ocho vecinos, excepto las paredes. Los bordes diagonales cuestan 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 por sobrestimar las heurísticas (rojo y cian). Por otro lado, existen múltiples caminos óptimos (azul, amarillo, verde) y depende de la heurística cuál se encuentra primero.
Las diferentes imágenes muestran todos los nodos expandidos cuando se alcanza el objetivo. El color muestra el costo estimado de la ruta usando este nodo (considerando también la ruta “ya tomada” desde el inicio hasta este nodo; matemáticamente es el costo hasta el momento 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 de ruta: 89.669
2. A vuelo de pájaro (amarillo)
- Nodos expandidos: 658
- Longitud de ruta: 89.669
- https://i.stack.imgur.com/75eFV.png
3. ideales (verde)
- Camino más corto sin obstáculos (si sigues las ocho direcciones)
- Estimación más alta posible sin sobreestimar (de ahí “ideales”)
- Nodos expandidos: 854
- Longitud de ruta: 89.669
- https://i.stack.imgur.com/VqMtF.png
4. Manhattan (rojo)
- Camino más corto sin obstáculos (si no te mueves en diagonal; en otras palabras: el costo de “moverse en diagonal” se estima en 2)
- Sobrestima
- Nodos expandidos: 562
- Longitud de ruta: 92.840
- https://i.stack.imgur.com/gD9t4.png
5. Como el cuervo vuela diez veces (cian)
- Sobrestima
- Nodos expandidos: 188
- Longitud de ruta: 99.811
- https://i.stack.imgur.com/SZuFH.png
valoraciones y reseñas
Agradecemos que quieras añadir valor a nuestra información asistiendo con tu veteranía en las interpretaciones.