A * heurística, sobreestimación / subestimación?

Question

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 sobreestima cuando toma el cuadrado de la línea directa de vista de pájaro? ¿Y por qué haría incorrecto el algoritmo? Se utiliza la misma heurística para todos los nodos.

¿Se subestima cuando se toma la raíz cuadrada de la línea directa de vista de pájaro? ¿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.

Answer 1

Estás sobreestimando cuando la estimación de la heurística es más alta que el costo final real de la ruta. Estás subestimando cuando es más bajo (no tienes que subestimar, solo tienes que no sobreestimar; las estimaciones correctas están bien). Si los costos de borde de su gráfico son todos 1, entonces los ejemplos que brinde proporcionarían sobrestimaciones y subestimaciones, aunque la distancia de coordenadas simple también funciona a la perfección en un espacio cartesiano.

Sobreestimar no hace exactamente que el algoritmo sea incorrecto lo que significa es que ya no tienes 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 examinando caminos que debería ignorar, y posiblemente encontrando caminos subóptimos debido a la exploración de esos. 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 la Wikipedia A * artículo . Menciono (y enlace) principalmente porque es casi imposible que Google lo haga.

Answer 2

Del artículo 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 nodo en la cola (o hasta que la cola esté vacía).

La idea clave es que, con poca estimación, A * solo dejará de explorar una ruta 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 una sobreestimación, A * no tiene idea de cuándo puede dejar de explorar una ruta potencial, ya que puede haber rutas con un costo real más bajo pero un costo estimado más alto que la mejor ruta conocida actualmente hacia la meta.

Answer 3

Hasta donde yo sé, normalmente desea subestimar para que aún pueda encontrar el camino más corto. Puede encontrar una respuesta más rápido sobreestimando, 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 proporcionar ninguna idea sobre las líneas de vista de pájaro ...

Answer 4

Respuesta corta

La respuesta de @chaos es un poco engañosa imo (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 (al lado 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 mediante el uso de una heurística que sobreestima 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 tiempo para calcular esto 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 la heurística difiere. Cada nodo (celda de cuadrícula) tiene bordes para los ocho vecinos, excepto los muros. 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 algunos caminos subóptimos al sobreestimar 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 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. Mientras el cuervo vuela (amarillo)

• Nodos expandidos: 658
• Longitud del camino: 89.669
• https://i.stack.imgur.com/75eFV.png

3. Ideal (verde)

• El camino más corto sin obstáculos (si sigue las ocho direcciones)
• 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 como 2)
• Sobreestima
• Nodos expandidos: 562
• Longitud del camino: 92.840
• https://i.stack.imgur.com/gD9t4.png

5. Mientras el cuervo vuela multiplicado por diez (cian)

• Sobreestima
• Nodos expandidos: 188
• Longitud del camino: 99.811
• https://i.stack.imgur.com/SZuFH.png