Implementierung einer A * -Pfadfindung in Java

1. Einleitung

Pfadfindungsalgorithmen sind Techniken zum Navigieren in Karten , mit denen wir eine Route zwischen zwei verschiedenen Punkten finden können. Unterschiedliche Algorithmen haben unterschiedliche Vor- und Nachteile, häufig in Bezug auf die Effizienz des Algorithmus und die Effizienz der von ihm erzeugten Route.

2. Was ist ein Pfadfindungsalgorithmus?

Ein Pfadfindungsalgorithmus ist eine Technik zum Konvertieren eines Diagramms - bestehend aus Knoten und Kanten - in eine Route durch das Diagramm . Dieses Diagramm kann alles sein, was durchlaufen werden muss. In diesem Artikel werden wir versuchen, einen Teil des Londoner U-Bahn-Systems zu durchqueren:

(Die „London Underground Overground DLR Crossrail-Karte“ von sameboat ist unter CC BY-SA 4.0 lizenziert.)

Dies hat viele interessante Komponenten:

  • Möglicherweise haben wir einen direkten Weg zwischen unseren Start- und Endpunkten. Zum Beispiel können wir direkt von "Earl's Court" zu "Monument" gehen, aber nicht zu "Angel".
  • Jeder einzelne Schritt hat bestimmte Kosten. In unserem Fall ist dies der Abstand zwischen den Stationen.
  • Jeder Stopp ist nur mit einer kleinen Teilmenge der anderen Stopps verbunden. Zum Beispiel ist "Regent's Park" nur direkt mit "Baker Street" und "Oxford Circus" verbunden.

Alle Pfadfindungsalgorithmen verwenden als Eingabe eine Sammlung aller Knoten - in unserem Fall Stationen - und Verbindungen zwischen ihnen sowie die gewünschten Start- und Endpunkte. Die Ausgabe ist normalerweise die Menge von Knoten, die uns von Anfang bis Ende in der Reihenfolge bringen, in der wir gehen müssen .

3. Was ist A *?

A * ist ein spezifischer Pfadfindungsalgorithmus , der erstmals 1968 von Peter Hart, Nils Nilsson und Bertram Raphael veröffentlicht wurde. Es wird allgemein als der beste Algorithmus angesehen, der verwendet werden kann, wenn keine Möglichkeit zur Vorberechnung der Routen besteht und keine Einschränkungen für die Speichernutzung bestehen .

Sowohl die Speicher- als auch die Leistungskomplexität können im schlimmsten Fall O (b ^ d) sein. Es wird also immer die effizienteste Route ermittelt, dies ist jedoch nicht immer die effizienteste Methode.

A * ist eine Variation des Dijkstra-Algorithmus, bei dem zusätzliche Informationen zur Auswahl des nächsten zu verwendenden Knotens bereitgestellt werden. Diese zusätzlichen Informationen müssen nicht perfekt sein - wenn wir bereits perfekte Informationen haben, ist die Pfadfindung sinnlos. Aber je besser es ist, desto besser wird das Endergebnis sein.

4. Wie funktioniert A *?

Der A * -Algorithmus wählt iterativ die bisher beste Route aus und versucht, den besten nächsten Schritt zu ermitteln.

Wenn wir mit diesem Algorithmus arbeiten, haben wir mehrere Daten, die wir verfolgen müssen. Die "offene Menge" sind alle Knoten, die wir derzeit in Betracht ziehen. Dies ist nicht jeder Knoten im System, sondern jeder Knoten, von dem aus wir den nächsten Schritt machen könnten.

Wir werden auch die aktuell beste Punktzahl, die geschätzte Gesamtpunktzahl und den aktuell besten vorherigen Knoten für jeden Knoten im System verfolgen.

Als Teil davon müssen wir in der Lage sein, zwei verschiedene Punktzahlen zu berechnen. Eine ist die Punktzahl, um von einem Knoten zum nächsten zu gelangen. Die zweite ist eine Heuristik, um eine Schätzung der Kosten von einem beliebigen Knoten zum Ziel zu erhalten. Diese Schätzung muss nicht genau sein, aber eine höhere Genauigkeit führt zu besseren Ergebnissen. Die einzige Voraussetzung ist, dass beide Bewertungen miteinander übereinstimmen - das heißt, sie befinden sich in denselben Einheiten.

Zu Beginn besteht unser offener Satz aus unserem Startknoten, und wir haben überhaupt keine Informationen über andere Knoten.

Bei jeder Iteration werden wir:

  • Wählen Sie den Knoten aus unserem offenen Satz aus, der die niedrigste geschätzte Gesamtpunktzahl aufweist
  • Entfernen Sie diesen Knoten aus dem offenen Satz
  • Fügen Sie dem offenen Satz alle Knoten hinzu, die wir von dort aus erreichen können

Wenn wir dies tun, berechnen wir auch die neue Punktzahl von diesem Knoten zu jedem neuen, um festzustellen, ob dies eine Verbesserung gegenüber dem ist, was wir bisher haben, und wenn dies der Fall ist, aktualisieren wir das, was wir über diesen Knoten wissen.

Dies wird dann wiederholt, bis der Knoten in unserem offenen Satz mit der niedrigsten geschätzten Gesamtpunktzahl unser Ziel ist. An diesem Punkt haben wir unsere Route.

4.1. Gearbeitetes Beispiel

Beginnen wir zum Beispiel bei „Marylebone“ und versuchen, unseren Weg zur „Bond Street“ zu finden.

Unser offenes Set besteht zu Beginn nur aus „Marylebone“ . Dies bedeutet, dass dies implizit der Knoten ist, für den wir die beste „geschätzte Gesamtpunktzahl“ haben.

Unsere nächsten Haltestellen können entweder die „Edgware Road“ mit einem Preis von 0,4403 km oder die „Baker Street“ mit einem Preis von 0,4153 km sein. Die „Edgware Road“ weist jedoch die falsche Richtung auf, sodass unsere Heuristik von hier zum Ziel eine Punktzahl von 1,4284 km ergibt, während die „Baker Street“ eine heuristische Punktzahl von 1,0753 km aufweist.

Dies bedeutet, dass unser offenes Set nach dieser Iteration aus zwei Einträgen besteht - "Edgware Road" mit einer geschätzten Gesamtpunktzahl von 1,8687 km und "Baker Street" mit einer geschätzten Gesamtpunktzahl von 1,4906 km.

Unsere zweite Iteration beginnt dann in der „Baker Street“, da diese die niedrigste geschätzte Gesamtpunktzahl aufweist. Von hier aus können unsere nächsten Stationen entweder "Marylebone", "St. Johns Wood “,„ Great Portland Street “, Regent's Park oder„ Bond Street “.

Wir werden nicht alle durcharbeiten, aber nehmen wir "Marylebone" als interessantes Beispiel. Die Kosten, um dorthin zu gelangen, betragen erneut 0,4153 km, was bedeutet, dass die Gesamtkosten jetzt 0,8306 km betragen. Zusätzlich ergibt die Heuristik von hier zum Ziel eine Punktzahl von 1,323 km.

Dies bedeutet, dass die geschätzte Gesamtpunktzahl 2,1536 km beträgt, was schlechter ist als die vorherige Punktzahl für diesen Knoten. Dies ist sinnvoll, da wir in diesem Fall zusätzliche Arbeit leisten mussten, um nicht weiterzukommen. Dies bedeutet, dass wir dies nicht als praktikable Route betrachten werden. Daher werden die Details für „Marylebone“ nicht aktualisiert und nicht wieder zum offenen Set hinzugefügt.

5. Java-Implementierung

Now that we've discussed how this works, let's actually implement it. We're going to build a generic solution, and then we'll implement the code necessary for it to work for the London Underground. We can then use it for other scenarios by implementing only those specific parts.

5.1. Representing the Graph

Firstly, we need to be able to represent our graph that we wish to traverse. This consists of two classes – the individual nodes and then the graph as a whole.

We'll represent our individual nodes with an interface called GraphNode:

public interface GraphNode { String getId(); }

Each of our nodes must have an ID. Anything else is specific to this particular graph and is not needed for the general solution. These classes are simple Java Beans with no special logic.

Our overall graph is then represented by a class simply called 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()); } }
    

This stores all of the nodes in our graph and has knowledge of which nodes connect to which. We can then get any node by ID, or all of the nodes connected to a given node.

At this point, we're capable of representing any form of graph we wish, with any number of edges between any number of nodes.

5.2. Steps on Our Route

The next thing we need is our mechanism for finding routes through the graph.

The first part of this is some way to generate a score between any two nodes. We'll the Scorer interface for both the score to the next node and the estimate to the destination:

public interface Scorer { double computeCost(T from, T to); }

Given a start and an end node, we then get a score for traveling between them.

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

In diesem Artikel haben wir gesehen, was der A * -Algorithmus ist, wie er funktioniert und wie er in unseren eigenen Projekten implementiert wird. Warum nehmen Sie das nicht und erweitern es für Ihren eigenen Gebrauch?

Versuchen Sie vielleicht, es zu erweitern, um den Austausch zwischen U-Bahnlinien zu berücksichtigen, und sehen Sie, wie sich dies auf die ausgewählten Routen auswirkt.

Und wieder ist der vollständige Code für den Artikel auf GitHub verfügbar.