El algoritmo A  * conocido como «A-Star» es una variación optimizada del algoritmo Dijkstra. Este algoritmo posee unas características especiales que permiten estudiar los grafos de forma excepcional y tiene un rango de aplicación especial. A continuación conoceremos cómo funciona este algoritmo, sus principales casos de uso y desarrollaremos un ejemplo práctico en el entorno de Neo4j para comprender mejor la forma en la que trabaja.

¿Qué es el algoritmo A *?

Este algoritmo es una mejora desarrollada a los postulados del algoritmo Dijsktra que se encarga de encontrar rutas más cortas dentro de un grafo. En esta modificación se toma como punto central la observación búsquedas informadas dentro del grafo que nos permitan tomar decisiones óptimas sobre los caminos que deben tomarse para recorrer de forma eficiente el grafo.

El Algoritmo A * tiene su origen en el año 1968 y fue desarrollado principalmente para aportar elementos a la determinación de rutas de costo mínimo. A continuación descubriremos como es su funcionamiento.

Para la aplicación de este algoritmo debemos comprender como se procede a dividir el costo de la ruta. En este caso se divide en dos partes donde g(n) representa el costo de la ruta desde su origen hasta algún nodo n dentro del grafo. También tenemos que  h (n) representa el costo estimado de la ruta desde el nodo n al nodo de destino, calculado por una suposición inteligente.

En el se logra equilibrar g (n) y h (n) mientras itera el gráfico, asegurando así que en cada iteración elija el nodo con el costo total más bajo f (n) = g (n) + h (n).

Casos de uso del algoritmo A *

El algoritmo A * al ser especialmente diseñado para detectar en las rutas menos costosas dentro de un grafo complejo, es normalmente utilizado para encontrar rutas cortas entre pares individuales de ubicaciones. Es por esto que una de sus aplicaciones más usuales es para detectar geo-localizaciones en las que se tiene conocimiento de coordenadas de ubicación por satélite.

Veamos a continuación un ejemplo practico desarrollado en Neo4j para comprender su funcionalidad.

Ejemplo de aplicación

Para conocer más a profundidad el funcionamiento y la aplicación del algoritmo procederemos en primer lugar a construir un grafo donde reflejaremos como nodos diferentes ubicaciones y asignaremos distancias para poder conocer cual es el costo mínimo en cada ruta a recorrer.

MERGE (a:Station{name:"King's Cross St. Pancras"})
SET a.latitude = 51.5308,a.longitude = -0.1238
MERGE (b:Station{name:"Euston"})
SET b.latitude = 51.5282, b.longitude = -0.1337
MERGE (c:Station{name:"Camden Town"})
SET c.latitude = 51.5392, c.longitude = -0.1426
MERGE (d:Station{name:"Mornington Crescent"})
SET d.latitude = 51.5342, d.longitude = -0.1387
MERGE (e:Station{name:"Kentish Town"})
SET e.latitude = 51.5507, e.longitude = -0.1402
MERGE (a)-[:CONNECTION{time:2}]->(b)
MERGE (b)-[:CONNECTION{time:3}]->(c)
MERGE (b)-[:CONNECTION{time:2}]->(d)
MERGE (d)-[:CONNECTION{time:2}]->(c)
MERGE (c)-[:CONNECTION{time:2}]->(e);

Una vez construido el grafo procedemos a ejecutarlo declarando la función como se muestra a continuación:

MATCH (start:Station{name:"King's Cross St. Pancras"}),(end:Station{name:"Kentish Town"})
CALL algo.shortestPath.astar.stream(start, end, 'time', 'latitude', 'longitude', 
{defaultValue:1.0})YIELD nodeId,
 costRETURN algo.asNode(nodeId).name as station,cost

Al ejecutar el cálculo este nos devolverá un cálculo del costo de las rutas que hemos indicado el grafo. Para el caso que hemos utilizado como ejemplo esta seria la tabla de resultados:

Name

Cost

King’s Cross St. Pancras

0

Euston

2

Camden Town

5

Kentish Town

7

Esperamos que esta información sea de utilidad para comprender la utilidad de este interesante algoritmo orientado al análisis de grafos.

Visita más de Grapheverywhere para conocer más sobre algoritmos de calculo de rutas cortas.