1. Introducción
Los algoritmos de búsqueda de caminos son técnicas para navegar por mapas , lo que nos permite encontrar una ruta entre dos puntos diferentes. Los diferentes algoritmos tienen diferentes pros y contras, a menudo en términos de la eficiencia del algoritmo y la eficiencia de la ruta que genera.
2. ¿Qué es un algoritmo de búsqueda de caminos?
Un algoritmo de búsqueda de caminos es una técnica para convertir un gráfico, que consta de nodos y bordes, en una ruta a través del gráfico . Este gráfico puede ser cualquier cosa que necesite atravesar. Para este artículo, intentaremos atravesar una parte del sistema de metro de Londres:
(El "mapa de cruce de DLR de superficie del metro de Londres" del mismo barco tiene licencia CC BY-SA 4.0)
Esto tiene muchos componentes interesantes:
- Es posible que tengamos o no una ruta directa entre nuestros puntos de inicio y finalización. Por ejemplo, podemos ir directamente de "Earl's Court" a "Monument", pero no a "Angel".
- Cada paso tiene un costo particular. En nuestro caso, esta es la distancia entre estaciones.
- Cada parada solo está conectada a un pequeño subconjunto de las otras paradas. Por ejemplo, "Regent's Park" está conectado directamente solo con "Baker Street" y "Oxford Circus".
Todos los algoritmos de búsqueda de caminos toman como entrada una colección de todos los nodos - estaciones en nuestro caso - y conexiones entre ellos, y también los puntos de inicio y finalización deseados. La salida suele ser el conjunto de nodos que nos llevará de principio a fin, en el orden en el que necesitamos ir .
3. ¿Qué es A *?
A * es un algoritmo de búsqueda de rutas específico , publicado por primera vez en 1968 por Peter Hart, Nils Nilsson y Bertram Raphael. En general, se considera que es el mejor algoritmo para usar cuando no hay oportunidad de calcular previamente las rutas y no hay restricciones en el uso de la memoria .
Tanto la complejidad de la memoria como del rendimiento pueden ser O (b ^ d) en el peor de los casos, por lo que aunque siempre resultará la ruta más eficiente, no siempre es la forma más eficiente de hacerlo.
A * es en realidad una variación del algoritmo de Dijkstra, donde se proporciona información adicional para ayudar a seleccionar el siguiente nodo a utilizar. Esta información adicional no necesita ser perfecta; si ya tenemos información perfecta, entonces la búsqueda de caminos no tiene sentido. Pero cuanto mejor sea, mejor será el resultado final.
4. ¿Cómo funciona A *?
El algoritmo A * funciona seleccionando iterativamente cuál es la mejor ruta hasta ahora e intentando ver cuál es el mejor paso siguiente.
Cuando trabajamos con este algoritmo, tenemos varios datos de los que debemos realizar un seguimiento. El "conjunto abierto" son todos los nodos que estamos considerando actualmente. No se trata de todos los nodos del sistema, sino de todos los nodos desde los que podemos dar el siguiente paso.
También realizaremos un seguimiento de la mejor puntuación actual, la puntuación total estimada y el mejor nodo anterior actual para cada nodo del sistema.
Como parte de esto, necesitamos poder calcular dos puntajes diferentes. Uno es el puntaje para pasar de un nodo al siguiente. La segunda es una heurística para dar una estimación del costo desde cualquier nodo hasta el destino. Esta estimación no necesita ser precisa, pero una mayor precisión producirá mejores resultados. El único requisito es que ambas puntuaciones sean coherentes entre sí, es decir, que estén en las mismas unidades.
Al principio, nuestro conjunto abierto consiste en nuestro nodo de inicio, y no tenemos información sobre ningún otro nodo.
En cada iteración, haremos lo siguiente:
- Seleccione el nodo de nuestro conjunto abierto que tenga la puntuación total estimada más baja
- Eliminar este nodo del conjunto abierto
- Agregue al conjunto abierto todos los nodos a los que podemos llegar desde él
Cuando hacemos esto, también calculamos la nueva puntuación de este nodo a cada uno nuevo para ver si es una mejora de lo que tenemos hasta ahora, y si lo es, actualizamos lo que sabemos sobre ese nodo.
Esto luego se repite hasta que el nodo en nuestro conjunto abierto que tiene la puntuación total estimada más baja es nuestro destino, momento en el que tenemos nuestra ruta.
4.1. Ejemplo resuelto
Por ejemplo, comencemos desde "Marylebone" e intentemos encontrar nuestro camino hacia "Bond Street".
Al principio, nuestro set abierto consta solo de “Marylebone” . Eso significa que este es implícitamente el nodo para el que tenemos la mejor "puntuación total estimada".
Nuestras próximas paradas pueden ser “Edgware Road”, con un costo de 0.4403 km, o “Baker Street”, con un costo de 0.4153 km. Sin embargo, "Edgware Road" está en la dirección equivocada, por lo que nuestra heurística desde aquí hasta el destino da una puntuación de 1.4284 km, mientras que "Baker Street" tiene una puntuación heurística de 1.0753 km.
Esto significa que después de esta iteración nuestro conjunto abierto consta de dos entradas: “Edgware Road”, con una puntuación total estimada de 1.8687 km, y “Baker Street”, con una puntuación total estimada de 1.4906 km.
Nuestra segunda iteración comenzará desde "Baker Street", ya que tiene la puntuación total estimada más baja. Desde aquí, nuestras próximas paradas pueden ser “Marylebone”, “St. John's Wood ”,“ Great Portland Street ”, Regent's Park” o “Bond Street”.
No trabajaremos con todos estos, pero tomemos “Marylebone” como un ejemplo interesante. El costo para llegar allí es nuevamente de 0.4153 km, pero esto significa que el costo total ahora es de 0.8306 km. Además, la heurística de aquí al destino da una puntuación de 1.323 km.
Esto significa que la puntuación total estimada sería de 2.1536 km, que es peor que la puntuación anterior para este nodo. Esto tiene sentido porque hemos tenido que hacer un trabajo adicional para no llegar a ninguna parte en este caso. Esto significa que no la consideraremos una ruta viable. Como tal, los detalles de "Marylebone" no se actualizan y no se agrega de nuevo al conjunto abierto.
5. Implementación de Java
Ahora que hemos discutido cómo funciona esto, implementémoslo. Vamos a crear una solución genérica y luego implementaremos el código necesario para que funcione en el metro de Londres. Luego, podemos usarlo para otros escenarios implementando solo esas partes específicas.
5.1. Representando el gráfico
En primer lugar, necesitamos poder representar nuestro gráfico que deseamos atravesar. Este consta de dos clases: los nodos individuales y luego el gráfico en su conjunto.
Representaremos nuestros nodos individuales con una interfaz llamada GraphNode :
public interface GraphNode { String getId(); }Cada uno de nuestros nodos debe tener una identificación. Cualquier otra cosa es específica de este gráfico en particular y no es necesaria para la solución general. Estas clases son Java Beans simples sin lógica especial.
Luego, nuestro gráfico general se representa mediante una clase llamada simplemente Graph :
public class Graph { private final Set nodes; private final Map
connections; public T getNode(String id) { return nodes.stream() .filter(node -> node.getId().equals(id)) .findFirst() .orElseThrow(() -> new IllegalArgumentException("No node found with ID")); } public Set getConnections(T node) { return connections.get(node.getId()).stream() .map(this::getNode) .collect(Collectors.toSet()); } }
Esto almacena todos los nodos en nuestro gráfico y tiene conocimiento de qué nodos se conectan a cuál. Entonces podemos obtener cualquier nodo por ID, o todos los nodos conectados a un nodo dado.
En este punto, somos capaces de representar cualquier forma de gráfico que deseemos, con cualquier número de bordes entre cualquier número de nodos.
5.2. Pasos en nuestra ruta
Lo siguiente que necesitamos es nuestro mecanismo para encontrar rutas a través del gráfico.
La primera parte de esto es una forma de generar una puntuación entre dos nodos. Vamos a la Goleador interfaz, tanto para el marcador al siguiente nodo y la estimación para el destino:
public interface Scorer { double computeCost(T from, T to); }Dado un nodo inicial y final, obtenemos una puntuación por viajar entre ellos.
We also need a wrapper around our nodes that carries some extra information. Instead of being a GraphNode, this is a RouteNode – because it's a node in our computed route instead of one in the entire graph:
class RouteNode implements Comparable { private final T current; private T previous; private double routeScore; private double estimatedScore; RouteNode(T current) { this(current, null, Double.POSITIVE_INFINITY, Double.POSITIVE_INFINITY); } RouteNode(T current, T previous, double routeScore, double estimatedScore) { this.current = current; this.previous = previous; this.routeScore = routeScore; this.estimatedScore = estimatedScore; } }As with GraphNode, these are simple Java Beans used to store the current state of each node for the current route computation. We've given this a simple constructor for the common case, when we're first visiting a node and have no additional information about it yet.
These also need to be Comparable though, so that we can order them by the estimated score as part of the algorithm. This means the addition of a compareTo() method to fulfill the requirements of the Comparable interface:
@Override public int compareTo(RouteNode other) { if (this.estimatedScore > other.estimatedScore) { return 1; } else if (this.estimatedScore < other.estimatedScore) { return -1; } else { return 0; } }5.3. Finding Our Route
Now we're in a position to actually generate our routes across our graph. This will be a class called RouteFinder:
public class RouteFinder { private final Graph graph; private final Scorer nextNodeScorer; private final Scorer targetScorer; public List findRoute(T from, T to) { throw new IllegalStateException("No route found"); } }We have the graph that we are finding the routes across, and our two scorers – one for the exact score for the next node, and one for the estimated score to our destination. We've also got a method that will take a start and end node and compute the best route between the two.
This method is to be our A* algorithm. All the rest of our code goes inside this method.
We start with some basic setup – our “open set” of nodes that we can consider as the next step, and a map of every node that we've visited so far and what we know about it:
Queue openSet = new PriorityQueue(); Map
allNodes = new HashMap(); RouteNode start = new RouteNode(from, null, 0d, targetScorer.computeCost(from, to)); openSet.add(start); allNodes.put(from, start);
Our open set initially has a single node – our start point. There is no previous node for this, there's a score of 0 to get there, and we've got an estimate of how far it is from our destination.
The use of a PriorityQueue for the open set means that we automatically get the best entry off of it, based on our compareTo() method from earlier.
Now we iterate until either we run out of nodes to look at, or the best available node is our destination:
while (!openSet.isEmpty()) { RouteNode next = openSet.poll(); if (next.getCurrent().equals(to)) { List route = new ArrayList(); RouteNode current = next; do { route.add(0, current.getCurrent()); current = allNodes.get(current.getPrevious()); } while (current != null); return route; } // ...When we've found our destination, we can build our route by repeatedly looking at the previous node until we reach our starting point.
Next, if we haven't reached our destination, we can work out what to do next:
graph.getConnections(next.getCurrent()).forEach(connection -> { RouteNode nextNode = allNodes.getOrDefault(connection, new RouteNode(connection)); allNodes.put(connection, nextNode); double newScore = next.getRouteScore() + nextNodeScorer.computeCost(next.getCurrent(), connection); if (newScore < nextNode.getRouteScore()) { nextNode.setPrevious(next.getCurrent()); nextNode.setRouteScore(newScore); nextNode.setEstimatedScore(newScore + targetScorer.computeCost(connection, to)); openSet.add(nextNode); } }); throw new IllegalStateException("No route found"); }Here, we're iterating over the connected nodes from our graph. For each of these, we get the RouteNode that we have for it – creating a new one if needed.
We then compute the new score for this node and see if it's cheaper than what we had so far. If it is then we update it to match this new route and add it to the open set for consideration next time around.
This is the entire algorithm. We keep repeating this until we either reach our goal or fail to get there.
5.4. Specific Details for the London Underground
What we have so far is a generic A* pathfinder, but it's lacking the specifics we need for our exact use case. This means we need a concrete implementation of both GraphNode and Scorer.
Our nodes are stations on the underground, and we'll model them with the Station class:
public class Station implements GraphNode { private final String id; private final String name; private final double latitude; private final double longitude; }The name is useful for seeing the output, and the latitude and longitude are for our scoring.
In this scenario, we only need a single implementation of Scorer. We're going to use the Haversine formula for this, to compute the straight-line distance between two pairs of latitude/longitude:
public class HaversineScorer implements Scorer { @Override public double computeCost(Station from, Station to) { double R = 6372.8; // Earth's Radius, in kilometers double dLat = Math.toRadians(to.getLatitude() - from.getLatitude()); double dLon = Math.toRadians(to.getLongitude() - from.getLongitude()); double lat1 = Math.toRadians(from.getLatitude()); double lat2 = Math.toRadians(to.getLatitude()); double a = Math.pow(Math.sin(dLat / 2),2) + Math.pow(Math.sin(dLon / 2),2) * Math.cos(lat1) * Math.cos(lat2); double c = 2 * Math.asin(Math.sqrt(a)); return R * c; } }We now have almost everything necessary to calculate paths between any two pairs of stations. The only thing missing is the graph of connections between them. This is available in GitHub.
Let's use it for mapping out a route. We'll generate one from Earl's Court up to Angel. This has a number of different options for travel, on a minimum of two tube lines:
public void findRoute() { List route = routeFinder.findRoute(underground.getNode("74"), underground.getNode("7")); System.out.println(route.stream().map(Station::getName).collect(Collectors.toList())); }This generates a route of Earl's Court -> South Kensington -> Green Park -> Euston -> Angel.
The obvious route that many people would have taken would likely be Earl's Count -> Monument -> Angel, because that's got fewer changes. Instead, this has taken a significantly more direct route even though it meant more changes.
6. Conclusion
En este artículo, hemos visto qué es el algoritmo A *, cómo funciona y cómo implementarlo en nuestros propios proyectos. ¿Por qué no tomar esto y extenderlo para sus propios usos?
¿Quizás intentar ampliarlo para tener en cuenta los intercambios entre líneas de metro y ver cómo afecta eso a las rutas seleccionadas?
Y nuevamente, el código completo del artículo está disponible en GitHub.