A*: algoritmo heurístico para encontrar la ruta más corta
Aprende A*: algoritmo heurístico eficiente para encontrar la ruta más corta entre dos puntos. Rápido, práctico y más inteligente que Dijkstra gracias a potentes heurísticas.
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.
Los pasos
A* necesita primero una lista de todos los lugares a los que puedes ir, y luego necesita una lista de la distancia que hay entre cada uno de ellos. A continuación, te dirá cuál es el camino más rápido para ir del lugar A al lugar Z.
Como ejemplo, diremos que A está conectado a los lugares B y C, y que B y C están conectados a D y E. D y E están conectados a Z. Hay 4 formas posibles de ir de A a Z. Puedes ir A-B-D-Z, A-C-D-Z, A-B-E-Z, o A-C-E-Z. Un ordenador que utiliza A* primero mira lo difícil que es ir de A a B, y de A a C. Este es el "coste" de esos lugares. El coste de un lugar significa lo difícil que es llegar de A a ese lugar. Después de anotar ambos costes, el ordenador mira lo difícil que es ir de B a D, y lo añade al coste de B. Lo anota como coste de D. A continuación, el ordenador observa lo que cuesta ir de C a D y lo añade al coste de C. Esto es un coste diferente para D, y si es menor que el que ya tiene, reemplazará el antiguo. El ordenador sólo quiere conocer el mejor camino, por lo que ignora el camino con mayor coste. Sólo recordará uno de A-B-D y A-C-D, el que sea más rápido.
El ordenador continúa y encuentra el camino más rápido para llegar a E. Finalmente, va de D a Z, y encuentra un coste, y de E a Z y encuentra un coste. Obtiene un coste final para Z, y éste es el coste más pequeño que puede obtener. Ahora el ordenador sabe qué camino es el más rápido, y tiene la respuesta. El ordenador puede hacer una serie de pasos similares, pero con muchos más lugares. Cada vez, mirará el lugar más cercano a A, y sumará los costes de los vecinos de ese lugar.
La gente llama a esta serie de pasos el algoritmo de Dijkstra. El algoritmo de Dijkstra puede ser lento, porque buscará en muchos lugares que podrían ir en la dirección equivocada desde Z. Si le preguntas al ordenador cómo ir de una ciudad a otra cercana, el algoritmo de Dijkstra podría acabar buscando en otro estado.
A* soluciona este problema. A* te permite decirle al ordenador una estimación de la distancia que habrá desde cada lugar hasta el final. El ordenador puede utilizar la estimación para saber aproximadamente la distancia que se tardará en llegar desde un lugar determinado a Z. En lugar de elegir simplemente el lugar más cercano a A para mirar, mirará el que probablemente tendrá el total más bajo. El total se obtiene sumando el coste a la distancia prevista que queda. De esta manera, puede mirar sólo en la dirección en la que las cosas probablemente mejoren. No pasa nada si la suposición no es perfecta, pero incluso una simple suposición errónea puede hacer que el programa vaya mucho más rápido. Si estás tratando de encontrar un camino entre dos lugares en el mundo real, una buena suposición es sólo la distancia entre ellos en línea recta. El camino real sobre las carreteras será más largo, pero esto permite al programa adivinarlo, y no irá en la dirección equivocada.
En la literatura matemática o informática, esta conjetura suele ser una función del lugar, y se denomina heurística. Cada lugar es un vértice, y cada camino entre dos lugares es una arista. Son palabras de la teoría de grafos.
Autor
AlegsaOnline.com A*: algoritmo heurístico para encontrar la ruta más corta Leandro Alegsa
URL: https://es.alegsaonline.com/art/2