A* es un conjunto de pasos (un algoritmo) que los ordenadores pueden utilizar para averiguar cómo llegar rápidamente de un punto a otro en un mapa o grafo. Si tienes una lista de nodos (lugares) y conoces el coste para ir de uno a otro (por ejemplo, distancia o tiempo), A* puede decirte el camino más corto. Está relacionado con el algoritmo de Dijkstra, pero añade conjeturas inteligentes (heurísticas) para evitar explorar caminos que probablemente sean largos. A* es una buena opción cuando solo quieres la ruta entre dos sitios concretos; si necesitas todas las rutas entre muchos pares, hay algoritmos diferentes (por ejemplo, Floyd–Warshall). A* tampoco resuelve problemas para visitar muchos lugares en un único viaje, como el problema del vendedor ambulante.

Cómo funciona (explicación simple)

A* mantiene dos conjuntos de nodos: abierto (candidatos por explorar) y cerrado (ya explorados). Para cada nodo n calcula:

  • g(n): coste conocido desde el nodo inicial hasta n.
  • h(n): estimación heurística del coste desde n hasta el objetivo.
  • f(n) = g(n) + h(n): estimación del coste total de la ruta que pasa por n.

En cada paso, A* extrae del conjunto abierto el nodo con el menor f(n), lo expande (genera sus vecinos) y actualiza sus costes. Si h(n) es una buena estimación, A* explora mucho menos que Dijkstra.

Propiedades importantes

  • Óptimo (con heurística admisible): si la heurística no sobreestima el coste real hasta el objetivo (es admisible), A* garantiza encontrar un camino de coste mínimo.
  • Completo: si hay un número finito de nodos y cada paso tiene coste mínimo mayor que cero, A* encontrará una solución si existe.
  • Eficiencia: cuanto más informativa sea la heurística (más cercana al coste real), menos nodos necesitará explorar. En el peor caso, la complejidad puede ser exponencial en el tamaño del problema.
  • Consistencia/Monotonía: si la heurística cumple h(n) ≤ coste(n,n') + h(n') para cada arista (es consistente), entonces f(n) nunca disminuye a lo largo de una ruta y no es necesario reabrir nodos cerrados.

Heurísticas comunes

  • Distancia Euclidiana: para movimiento en espacio continuo o cuando se permite moverse en cualquier dirección en el plano.
  • Distancia Manhattan: para rejillas donde el movimiento se limita a ejes ortogonales (arriba/abajo/izquierda/derecha).
  • Distancia Chebyshev: para rejillas donde se permiten movimientos diagonales a coste igual.
  • Heurística cero (h(n)=0): A* se convierte en Dijkstra.

Ejemplo sencillo

En una cuadrícula con obstáculos, si queremos ir de A a B y solo podemos movernos en las cuatro direcciones, usar la distancia Manhattan como h es admisible y suele guiar la búsqueda hacia el objetivo evitando explorar grandes zonas irrelevantes.

Pseudocódigo breve

 Inicializar abierto con el nodo inicial (g=inicial=0, f=h(inicial)) Mientras abierto no esté vacío:   sacar el nodo n con menor f(n)   si n es el objetivo: reconstruir y devolver la ruta   mover n a cerrado   para cada vecino m de n:     costeTentativo = g(n) + coste(n,m)     si m en cerrado y costeTentativo ≥ g(m): continuar     si m no en abierto o costeTentativo < g(m):       g(m) = costeTentativo       h(m) = heurística(m)       f(m) = g(m) + h(m)       establecer padre(m) = n       si m no en abierto: añadir m a abierto

Variantes y mejoras

  • Weighted A*: pondera la heurística (f = g + w·h) para obtener soluciones más rápidas pero posiblemente subóptimas si w>1.
  • Greedy Best-First Search: usa f = h, priorizando la cercanía al objetivo; es rápido pero no garantiza optimalidad.
  • IDA* (Iterative Deepening A*): versión con menor uso de memoria, adecuada cuando la memoria es limitada.
  • A* bidireccional: busca desde el inicio y desde el objetivo simultáneamente para acelerar la búsqueda en grafos grandes.
  • D* y D* Lite: variantes para grafos dinámicos donde los costes cambian y se necesita replanificar eficientemente.

Limitaciones y consideraciones prácticas

  • El principal consumo de A* suele ser memoria: guarda nodos abiertos y cerrados, lo que puede ser prohibitivo en problemas grandes.
  • Si la heurística no es buena, A* explorará casi tantos nodos como Dijkstra.
  • Para consultas repetidas en el mismo mapa existen algoritmos más adecuados (por ejemplo, preprocesamiento de rutas).
  • A* funciona en grafos y espacios continuos (discretizados) siempre que se pueda definir una heurística adecuada.

Aplicaciones comunes

  • Pathfinding en videojuegos y simulaciones.
  • Navegación para robots y vehículos autónomos.
  • Sistemas de enrutamiento y planificación de rutas en mapas.
  • Problemas de búsqueda en inteligencia artificial donde hay un estado inicial, acciones y un objetivo.

En resumen, A* es un algoritmo potente y versátil para encontrar rutas cortas cuando se dispone de una heurística informativa. Su rendimiento depende en gran medida de la calidad de esa heurística y del tamaño del espacio de búsqueda; en escenarios con memoria limitada o consultas múltiples puede convenir usar variantes o algoritmos alternativos.