1. Въведение
Алгоритмите за намиране на път са техники за навигация по карти , позволяващи ни да намерим маршрут между две различни точки. Различните алгоритми имат различни плюсове и минуси, често по отношение на ефективността на алгоритъма и ефективността на маршрута, който той генерира.
2. Какво е алгоритъм за намиране на път?
Алгоритъмът за намиране на път е техника за преобразуване на графика - състояща се от възли и ръбове - в маршрут през графиката . Тази графика може да бъде всичко, което се нуждае от обхождане. За тази статия ще се опитаме да прекосим част от лондонската подземна система:
(„Лондонска подземна надземна DLR Crossrail карта“ от същата лодка е лицензирана под CC BY-SA 4.0)
Това има много интересни компоненти:
- Може да имаме или да не разполагаме с директен маршрут между началната и крайната ни точка. Например, можем да преминем директно от „Графския двор“ към „Паметник“, но не и към „Ангел“.
- Всяка една стъпка има определена цена. В нашия случай това е разстоянието между станциите.
- Всяка спирка е свързана само с малка подгрупа от останалите спирки. Например, „Regent's Park“ е директно свързан само с „Baker Street“ и „Oxford Circus“.
Всички алгоритми за търсене на път приемат като вход колекция от всички възли - станции в нашия случай - и връзки между тях, както и желаните начални и крайни точки. Изходът обикновено е набор от възли, които ще ни отведат от началото до края, в реда, в който трябва да отидем .
3. Какво е A *?
A * е един специфичен алгоритъм за търсене на път, публикуван за първи път през 1968 г. от Peter Hart, Nils Nilsson и Bertram Raphael. Обикновено се смята за най-добрият алгоритъм за използване, когато няма възможност за предварително изчисляване на маршрутите и няма ограничения за използването на паметта .
Както паметта, така и сложността на производителността могат да бъдат O (b ^ d) в най-лошия случай, така че въпреки че винаги ще работи по най-ефективния маршрут, не винаги е най-ефективният начин да го направите.
A * всъщност е вариация на алгоритъма на Dijkstra, където има предоставена допълнителна информация, която да помогне за избора на следващия възел, който да се използва. Тази допълнителна информация не е необходимо да бъде перфектна - ако вече имаме перфектна информация, тогава търсенето на път е безсмислено. Но колкото по-добре е, толкова по-добър ще бъде крайният резултат.
4. Как работи A *?
Алгоритъмът A * работи, като итеративно избира кой е най-добрият маршрут до момента и се опитва да види коя е най-добрата следваща стъпка.
Когато работим с този алгоритъм, имаме няколко данни, които трябва да следим. „Отвореният набор“ е всички възли, които разглеждаме в момента. Това не е всеки възел в системата, но вместо това е всеки възел, от който можем да направим следващата стъпка.
Също така ще следим текущия най-добър резултат, прогнозния общ резултат и текущия най-добър предишен възел за всеки възел в системата.
Като част от това трябва да можем да изчислим два различни резултата. Единият е резултатът, за да стигнете от един възел до следващия. Втората е евристична, за да се даде оценка на разходите от всеки възел до дестинацията. Тази оценка не трябва да бъде точна, но по-голямата точност ще доведе до по-добри резултати. Единственото изискване е и двата резултата да са съвместими помежду си - тоест те са в едни и същи единици.
В самото начало нашият отворен набор се състои от нашия начален възел и изобщо нямаме информация за други възли.
При всяка итерация ще:
- Изберете възела от нашия отворен набор, който има най-ниския прогнозен общ резултат
- Премахнете този възел от отворения набор
- Добавете към отворения набор всички възли, до които можем да достигнем от него
Когато правим това, ние също разработваме новия резултат от този възел до всеки нов, за да видим дали това е подобрение на това, което имаме до момента, и ако е така, тогава актуализираме това, което знаем за този възел.
След това се повтаря, докато възелът в отворения ни набор, който има най-ниския прогнозен общ резултат, не е нашата дестинация, в който момент имаме своя маршрут.
4.1. Работен пример
Например, нека започнем от „Marylebone“ и се опитаме да намерим пътя си към „Bond Street“.
В самото начало нашият отворен комплект се състои само от „Marylebone“ . Това означава, че това по подразбиране е възелът, за който имаме най-добрия „прогнозен общ резултат“.
Следващите ни спирки могат да бъдат или „Edgware Road“, с цена 0,4403 км, или „Бейкър Стрийт“, с цена 0,4153 км. „Edgware Road“ обаче е в грешната посока, така че нашата евристика от тук до дестинацията дава резултат от 1,4284 км, докато „Бейкър Стрийт“ има евристичен резултат от 1,0753 км.
Това означава, че след тази итерация нашият отворен набор се състои от две записи - „Edgware Road“, с прогнозен общ резултат 1,88687 км, и „Бейкър Стрийт“, с очакван общ резултат 1,4906 км.
След това втората ни итерация ще започне от „Бейкър Стрийт“, тъй като това е най-ниският прогнозен общ резултат. Оттук следващите ни спирки могат да бъдат „Marylebone”, „St. John's Wood ”,„ Great Portland Street ”, Regent's Park” или „Bond Street”.
Няма да работим по всичко това, но нека вземем „Marylebone“ като интересен пример. Разходите до там отново са 0,4153 км, но това означава, че общите разходи сега са 0,8306 км. Освен това евристиката от тук до дестинацията дава оценка от 1,332 км.
Това означава, че прогнозният общ резултат ще бъде 2,1536 км, което е по - лошо от предишния резултат за този възел. Това има смисъл, защото в този случай трябваше да свършим допълнителна работа, за да стигнем до никъде. Това означава, че няма да считаме това за жизнеспособен маршрут. Като такива, подробностите за „Marylebone“ не се актуализират и не се добавят обратно към отворения комплект.
5. Внедряване на Java
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
В тази статия видяхме какво представлява алгоритъмът A *, как работи и как да го приложим в нашите собствени проекти. Защо да не вземете това и да го удължите за собствени нужди?
Може би се опитайте да го разширите, за да вземете предвид обменните връзки между тръбните линии и да видите как това се отразява на избраните маршрути?
И отново, пълният код на статията е достъпен в GitHub.