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)
- cola de prioridad
Cola de prioridad: una cola donde pasa primero el más barato, no el que llegó antes.
Otros términos de esta página
- 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.
- 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.
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.