Búsqueda A*
Dijkstra con sentido de la orientación. Al coste de cada lugar le suma una estimación del coste que falta, así que prueba primero los lugares que parecen más cerca de la meta.
- tiempo O((V + E) log V)
- espacio O(V)
- usa una cola de prioridad
¿Qué significan estos términos?
- Coste: lo que cuesta un movimiento. En el laberinto, pisar suelo cuesta 1, barro 3 y agua 9; en el grafo, el número de la arista.
- Cola de prioridad: una cola donde pasa primero el más barato, no el que llegó antes.
- Estimación (h): una suposición del coste que falta. A* solo es exacto si nunca se pasa.
- Relajar una arista: comprobar si pasar por el lugar actual da a un vecino un coste menor y, si es así, quedárselo.
- en la cola
- actual
- listo
- camino más barato
- suelo · 1
- barro · 3
- agua · 9
- pared
Nuevo: Inicio en A1 con coste 0 y una estimación de 26 hasta la meta. Es lo único que hay en la cola.
Espacio: reproducir o pausar. Flechas izquierda y derecha: paso a paso. Inicio y Fin: saltar.
Prueba esto: Elige el campo abierto y cambia entre Dijkstra y A*: ambos encuentran un camino del mismo coste, pero A* saca muchas menos casillas de la cola.
Cómo funciona
A* funciona como Dijkstra, pero ordena la cola por f = coste acumulado + h, donde h estima el coste que falta. En el laberinto, h es el número de movimientos hasta M sin contar paredes ni barro; en el grafo, la distancia en línea recta dividida entre 10. Mientras h nunca se pase, el camino que tiene A* al tomar la meta es el más barato, igual que con Dijkstra. Cuanto mejor la estimación, menos lugares tiene que mirar.
Cuándo es una buena opción
Usa A* cuando buscas una sola meta y puedes estimar a qué distancia está: búsqueda de caminos en videojuegos, robots, planificadores de rutas en un mapa. Con h = 0 es exactamente Dijkstra. Una estimación que puede pasarse hace a A* más rápido, pero puede costarte el camino más barato.