Búsqueda A*
El algoritmo de Dijkstra encuentra el camino más corto hasta un destino, pero busca en todas las direcciones a la vez, incluso alejándose del destino. La búsqueda A* añade un dato, una estimación de lo lejos que aún está el destino, y de pronto la búsqueda va directa hacia él.
La idea
Cuando buscas una ruta en un mapa, no exploras las carreteras que se alejan de tu destino con el mismo cuidado que las que se acercan a él. La búsqueda A* hace lo mismo. Cada nodo recibe una puntuación: la distancia desde el origen hasta ahora, g, más una estimación de la distancia restante, h. La búsqueda sigue siempre desde el nodo con la puntuación más baja, así que los nodos que están hacia el destino van primero.
Paso a paso
Da al origen distancia 0 y ponlo en una cola con puntuación h(origen). Repite: toma el nodo con la puntuación más baja y marca su distancia como definitiva. Si es el destino, para: siguiendo hacia atrás los nodos recordados se obtiene el camino. Si no, para cada vecino que no sea definitivo, calcula su distancia pasando por este nodo. Si es menor que su distancia hasta ahora, bájala, recuerda este nodo como el camino hasta él y da al vecino como puntuación su nueva distancia más su estimación. Cuando dos puntuaciones empatan, tomar primero el nodo con la estimación menor suele llegar antes al destino.
Un ejemplo
Toma un origen A y un destino D. A–B mide 2 y B–D 2, mientras que A–C mide 1 y C–D 5. Las estimaciones en línea recta hasta D son 3 desde A, 2 desde B y 3 desde C. A empieza con puntuación 0 + 3 = 3. Tomar A da a B la puntuación 2 + 2 = 4 y a C la puntuación 1 + 3 = 4. Con un empate, A* toma B, el nodo con la estimación menor, y B da a D la puntuación 4 + 0 = 4. Ahora D tiene la puntuación más baja con la estimación menor, así que se toma: el camino más corto es A → B → D, de longitud 4, y C, que lleva en la dirección equivocada, nunca se hace definitivo. El algoritmo de Dijkstra habría hecho definitivo primero a C, porque es el nodo más cercano a A.
Una buena estimación
La estimación nunca debe ser mayor que la distancia real al destino; una estimación así se llama admisible, y con ella A* siempre encuentra un camino más corto. La línea recta es admisible porque ninguna ruta es más corta que una línea recta. Si además la estimación nunca baja más que la longitud de una arista de un nodo al siguiente, es consistente, y ningún nodo definitivo necesita volver a revisarse. Cuanto más se acerca la estimación a la realidad, menos nodos necesita A*. Una estimación de 0 es admisible pero inútil: A* se convierte entonces en el algoritmo de Dijkstra. Una estimación demasiado grande hace A* más rápido, pero puede perder el camino más corto.
Historia y usos
Peter Hart, Nils Nilsson y Bertram Raphael, del Stanford Research Institute, publicaron A* en 1968, mientras trabajaban en Shakey, uno de los primeros robots móviles. Sus versiones anteriores se llamaban A1 y A2; la estrella marcaba la versión que demostraron óptima. Hoy A* mueve personajes esquivando obstáculos en videojuegos, planifica rutas y movimientos de robots, y resuelve rompecabezas como el 15-puzzle, donde la estimación suma lo lejos que está cada ficha de su sitio.
Pruébalo
Abre la app y pulsa Paso. Los números de las aristas son sus longitudes, que aquí coinciden con lo largas que están dibujadas, y la línea discontinua muestra la estimación en línea recta hasta el destino. La cola bajo el grafo lista los nodos por puntuación, primero la más baja. Cuando el destino es definitivo, la línea de estado compara cuántos nodos hizo definitivos A* con cuántos habría necesitado el algoritmo de Dijkstra. Prueba un destino en una esquina lejana de un grafo grande para ver la mayor diferencia.
Preguntas frecuentes
¿Qué significa la estrella de A*?
Hart, Nilsson y Raphael describieron primero algoritmos que llamaron A1 y A2. A* («A estrella») fue la versión de la que demostraron que encuentra un camino más corto expandiendo el menor número de nodos entre los algoritmos comparables que usan la misma estimación, cuando la estimación es consistente.
¿Cuál es la complejidad temporal de A*?
En el peor caso, con una estimación inútil, A* hace el mismo trabajo que el algoritmo de Dijkstra: O((V + E) log V) con un montículo binario. Con una buena estimación solo hace definitiva una fracción de los nodos, por eso es rápido en la práctica.
¿Qué hace buena a una heurística para A*?
Debe ser rápida de calcular, no sobrestimar nunca la distancia real y acercarse a ella todo lo posible. En una cuadrícula donde solo se puede mover arriba, abajo, a la izquierda y a la derecha, la distancia Manhattan es una opción habitual; en un mapa, la distancia en línea recta.
¿Y si la heurística sobrestima?
Entonces A* puede devolver un camino que no es el más corto, porque puede terminar antes de revisar la ruta mejor. Algunos programas lo hacen a propósito (A* ponderado) para cambiar un poco de calidad del camino por mucha velocidad.
¿Listo para probarlo?
Abre PictorX en tu navegador: sin instalación ni tarjeta de crédito para empezar.
Prueba la búsqueda A*