algorithm - resueltos - ¿A*heurística, sobrestimación/subestimación?
modelo heuristico (4)
Respuesta corta
La respuesta de @chaos es un poco engañosa imo (se puede resaltar)
La sobreestimación 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ápida si sobreestima, pero es posible que no encuentre el camino más corto.
Al final (junto al ó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 más grande que la ventaja de tiempo al tomar el camino más corto pero esperando más tiempo para computar esta solución.
Para darle una mejor impresión, comparto algunos resultados ejemplares que creé rápidamente con Python. Los resultados se derivan 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 sobreestimar las heurísticas (rojo y cian). Por otro lado, hay múltiples rutas óptimas (azul, amarillo, verde) y depende de la heurística que se encuentre 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 la ruta "ya tomada" desde el inicio hasta este nodo también; 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. Como vuela el cuervo (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 sigues las ocho direcciones)
- La estimación más alta posible sin sobreestimar (por lo tanto, "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)
- Sobrestima
- Nodos expandidos: 562
- Longitud del camino: 92.840
- https://i.stack.imgur.com/gD9t4.png
5. Como el cuervo vuela diez veces (cian)
- Sobrestima
- Nodos expandidos: 188
- Longitud del camino: 99.811
- https://i.stack.imgur.com/SZuFH.png
Estoy confundido acerca de los términos sobreestimación / subestimación. Entiendo perfectamente cómo funciona el algoritmo A *, pero no estoy seguro de los efectos de tener una heurística que sobreestime o subestime.
¿Se sobrestima cuando se toma el cuadrado de la línea directa de vista de aves? ¿Y por qué haría el algoritmo incorrecto? La misma heurística se utiliza para todos los nodos.
¿Es la subestimación cuando se toma el squareroot de la línea directa de vista de aves? ¿Y por qué el algoritmo sigue siendo correcto?
No puedo encontrar un artículo que lo explique bien y claro, así que espero que alguien aquí tenga una buena descripción.
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 tenga un valor f más bajo que cualquier otro nodo en la cola (o hasta que la cola esté vacía).
La idea clave es que, con un tiempo insuficiente, A * solo dejará de explorar un camino potencial hacia la meta una vez que sepa que el costo total de la ruta superará el costo de una ruta conocida hacia la meta. Dado que la estimación del costo de una ruta es siempre menor o igual al 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.
Está sobreestimando cuando la estimación de la heurística es más alta que el costo real de la ruta final. Está subestimando cuando es más bajo (no tiene que subestimar, solo tiene que no sobreestimar; las estimaciones correctas están bien). Si los costos de borde de su gráfica son todos 1, entonces los ejemplos que brinde darían sobreestimaciones y subestimaciones, aunque la distancia de la coordenada simple también funciona en un espacio cartesiano.
La sobreestimación 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 al examinar las rutas que debería ignorar, y posiblemente encontrar rutas subóptimas debido a la exploración de esas. Si eso ocurre realmente depende de su espacio problemático. Ocurre porque el costo de la ruta está "fuera de conjunto" con el costo de la estimación, lo que esencialmente le da al algoritmo las ideas desordenadas 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 vinculo) principalmente porque es casi imposible buscarlo en Google.
Por lo que yo sé, usted quiere subestimar típicamente para que pueda encontrar el camino más corto. Puede encontrar una respuesta más rápida si sobreestima, pero es posible que no encuentre el camino más corto. Por eso, la sobreestimación es "incorrecta", mientras que la subestimación puede proporcionar la mejor solución.
Lamento no poder darte una idea de las líneas de vista de pájaro ...