Автор оригинала: Graham Cox.

Реализация пути A’ в Java

1. Введение

Алгоритмы поиска пути являются методами навигации по картам , что позволяет нам найти маршрут между двумя различными точками. Различные алгоритмы имеют разные плюсы и минусы, часто с точки зрения эффективности алгоритма и эффективности маршрута, который он генерирует.

2. Что такое алгоритм поиска пути?

Алгоритм поиска пути — это метод преобразования графика, состоящего из узлов и краев, в маршрут через график . Этот график может быть что угодно, что нуждается в прохождении. Для этой статьи, мы собираемся попытаться пройти часть системы лондонского метро:

(” Лондонский метрополитен Overground DLR Crossrail карта ” по та же лодка лицензируется в соответствии с CC BY-SA 4.0 )

Это имеет много интересных компонентов к нему:

• Мы можем или не можем иметь прямой маршрут между нашими отправной точкой и точками окончания. Например, мы можем перейти непосредственно от “Earl’s Court” к “Памятник”, но не к “Ангелу”.
• Каждый шаг имеет определенную стоимость. В нашем случае это расстояние между станциями.
• Каждая остановка соединена только с небольшим подмножеством других остановок. Например, «Риджентс-парк» напрямую связан только с «Бейкер-стрит» и «Оксфордским цирком».

Все алгоритмы поиска пути принимают в качестве ввода набор всех узлов – станций в нашем случае – и соединения между ними, а также желаемые отправные и окончание точек. Выход, как правило, набор узлов, которые будут получать нас от начала до конца, в порядке, что мы должны идти .

3. Что такое АЗ?

АЗ является одним конкретным алгоритмом поиска , впервые опубликован в 1968 году Питер Харт, Нильс Нильссон, и Бертрам Рафаэль. Как правило, он считается лучшим алгоритмом для использования, когда нет возможности предварительно вычислить маршруты и нет никаких ограничений на использование памяти .

И память, и сложность производительности могут быть О(бюдом) в худшем случае, так что, хотя он всегда будет работать из наиболее эффективных маршрутов, это не всегда самый эффективный способ сделать это.

АЗ на самом деле является вариацией алгоритма Dijkstra , где есть дополнительная информация, предоставляемая, чтобы помочь выбрать следующий узел для использования. Эта дополнительная информация не должна быть идеальной – если у нас уже есть совершенная информация, то найти путь бессмысленно. Но чем лучше, тем лучше будет конечный результат.

4. Как работает АЗ?

Алгоритм АЗ работает, итеративно выбирая, что является лучшим маршрутом до сих пор, и пытаясь увидеть, что лучший следующий шаг.

При работе с этим алгоритмом, у нас есть несколько частей данных, которые мы должны отслеживать. “Открытый набор” – это все узлы, которые мы рассматриваем в настоящее время. Это не каждый узел в системе, но вместо этого, это каждый узел, что мы могли бы сделать следующий шаг от.

Мы также будем отслеживать текущий лучший результат, предполагаемый общий балл и текущий лучший предыдущий узел для каждого узла в системе.

В рамках этого, мы должны быть в состоянии вычислить два различных баллов. Одним из них является оценка, чтобы добраться от одного узла к следующему. Во-вторых, это хевризм, чтобы дать оценку стоимости от любого узла до места назначения. Эта оценка не должна быть точной, но большая точность даст лучшие результаты. Единственное требование заключается в том, что оба балла соответствуют друг другу, то есть они находятся в одном и том же подразделении.

В самом начале, наш открытый набор состоит из нашего узла старта, и у нас нет информации о каких-либо других узлов на всех.

На каждой итерации мы будем:

• Выберите узел из нашего открытого набора, который имеет самый низкий расчетный общий балл
• Удалите этот узел из открытого набора
• Добавьте в открытый набор все узлы, которые мы можем достичь из него

Когда мы делаем это, мы также работаем над новой партитурой от этого узла к каждому новому, чтобы увидеть, если это улучшение того, что у нас есть до сих пор, и если это так, то мы обновляем то, что мы знаем об этом узел.

Это повторяется до тех пор, пока узел в нашем открытом наборе, который имеет самый низкий расчетный общий балл, является нашим пунктом назначения, после чего мы получили наш маршрут.

4.1. Работал пример

Например, давайте начнем с “Мэрилебон” и попытаемся найти свой путь к “Бонд-стрит”.

В самом начале, наш открытый набор состоит только из “Marylebone” . Это означает, что это неявно узел, что у нас есть лучший “оценочный общий балл” для.

Следующими остановками могут стать либо “Edgware Road” стоимостью 0,4403 км, либо “Бейкер-стрит” стоимостью 0,4153 км. Тем не менее, “Edgware Road” находится в неправильном направлении, так что наш heuristic отсюда до места назначения дает балл 1,4284 км, в то время как “Бейкер-стрит” имеет геристический балл 1,0753 км.

Это означает, что после этой итерации наш открытый набор состоит из двух записей – “Edgware Road”, с оценочной общей оценкой 1,8687 км, и “Бейкер-стрит”, с оценочной общей оценкой 1,4906 км.

Наша вторая итерация будет начинаться с “Бейкер-стрит”, так как это имеет самый низкий расчетный общий балл. Отсюда, наши следующие остановки могут быть либо “Мэрилебон”, “Сент-Джонс-Вуд”, “Великая Портленд-стрит”, Риджентс-парк”, или “Бонд-стрит”.

Мы не будем работать через все это, но давайте возьмем “Marylebone” в качестве интересного примера. Стоимость добраться туда снова 0,4153 км, но это означает, что общая стоимость в настоящее время 0,8306 км. Дополнительно heuristic отсюда к назначению дает счет 1.323 километра.

Это означает, что предполагаемый общий балл составит 2,1536 км, что является хуже чем предыдущий балл для этого узла. Это имеет смысл, потому что мы должны были сделать дополнительную работу, чтобы получить нигде в этом случае. Это означает, что мы не будем считать это жизнеспособным маршрутом. Таким образом, детали для “Marylebone” не обновляются, и он не добавляется обратно на открытый набор.

5. Реализация Java

Теперь, когда мы обсудили, как это работает, давайте на самом деле реализовать его. Мы собираемся создать универсальное решение, а затем мы будем реализовывать код, необходимый для его работы в лондонском метро. Затем мы можем использовать его для других сценариев, реализуя только эти конкретные части.

5.1. Представление графика

Во-первых, мы должны быть в состоянии представлять наш график, который мы хотим пройти. Она состоит из двух классов – отдельных узлов, а затем графика в целом.

Мы будем представлять наши отдельные узлы с интерфейсом под названием ГрафНод :

public interface GraphNode {
    String getId();
}

Каждый из наших узлов должен иметь идентификатор. Все остальное специфичен для этого конкретного графика и не требуется для общего решения. Эти классы являются простыми Java-бобами без особой логики.

Наш общий график затем представлен классом, просто называемым График :

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());
    }
}

Это хранит все узлы в нашем графике и имеет знания о том, какие узлы подключаются к которому. Затем мы можем получить любой узел по идентификатору или все узлы, подключенные к данному узлу.

На данный момент, мы способны представлять любую форму графика мы хотим, с любым количеством краев между любым количеством узлов.

5.2. Шаги по нашему маршруту

Следующее, что нам нужно, это наш механизм поиска маршрутов через график.

Первая часть этого является каким-то образом для создания оценки между любыми двумя узлами. Мы будем Вратарь интерфейс для оценки к следующему узелу и оценки к месту назначения:

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

Учитывая начало и конечный узел, мы получаем балл за путешествие между ними.

Нам также нужна обертка вокруг наших узлов, которая несет некоторую дополнительную информацию. Вместо того, чтобы ГрафНод , это МаршрутНоде – потому что это узел в нашем вычислительном маршруте, а не один во всем графике:

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;
    }
}

Как и в ГрафНод , это простые Java-бобы, используемые для хранения текущего состояния каждого узла для текущей вычисления маршрута. Мы дали этому простой конструктор для общего случая, когда мы впервые посещаем узел и не имеют дополнительной информации о нем еще.

Они также должны быть Сопоставимые хотя, так что мы можем заказать их по расчетной оценке как часть алгоритма. Это означает добавление сравнитьTo() метод выполнения требований Сопоставимые интерфейс:

@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. Поиск нашего маршрута

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);

Наш открытый набор изначально имеет один узел – наша точка . Существует нет предыдущего узла для этого, есть оценка 0, чтобы туда добраться, и у нас есть оценка того, как далеко он от нашего назначения.

Использование ПриоритетКвью для открытого набора означает, что мы автоматически получаем лучший вход от него, на основе наших сравнитьTo() метод от более раннего.

Теперь мы итерировать до тех пор, пока либо мы запускаем из узлов, чтобы посмотреть, или лучший доступный узел является нашим пунктом назначения:

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");
}

Здесь мы итерировать над подключенными узлами из нашего графика. За каждый из них мы получаем МаршрутНоде что у нас есть для него – создание нового, если это необходимо.

Затем мы вычисляем новый балл для этого узла и посмотреть, если это дешевле, чем то, что мы до сих пор. Если это так, то мы обновляем его, чтобы соответствовать этому новому маршруту и добавить его в открытый набор для рассмотрения в следующий раз.

Это весь алгоритм. Мы повторяем это до тех пор, пока не достигнем своей цели или не сможем туда добраться.

5.4. Конкретные подробности для лондонского метро

То, что мы до сих пор является общим A’ следопытом, но это не хватает специфики нам нужно для нашего точного случая использования. Это означает, что нам необходимо конкретное осуществление обеих ГрафНод и Вратарь .

Наши узлы являются станциями в метро, и мы смооем их с Станция класс:

public class Station implements GraphNode {
    private final String id;
    private final String name;
    private final double latitude;
    private final double longitude;
}

Название полезно для просмотра вывода, а широта и долгота для нашего скоринга.

В этом сценарии нам нужна только единая реализация Вратарь . Мы будем использовать Формула Haversine для этого вычислить прямолинейное расстояние между двумя парами широты/долготы:

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;
    }
}

Теперь у нас есть почти все необходимое для расчета путей между любыми двумя парами станций. Единственное, чего не хватает, так это графика связей между ними. Это доступно в GitHub .

Давайте использовать его для отображения маршрута. Мы будем генерировать один из Эрлс Корт до Ангела. Это имеет ряд различных вариантов для путешествий, как минимум на двух линиях метро:

public void findRoute() {
    List route = routeFinder.findRoute(underground.getNode("74"), underground.getNode("7"));

    System.out.println(route.stream().map(Station::getName).collect(Collectors.toList()));
}

Это создает маршрут Earl’s Court -> South Kensington-> Грин-парк -> Euston -> Angel.

Очевидным маршрутом, который многие люди приняли бы, вероятно, будет граф -> -> Ангел, потому что это есть меньше изменений. Вместо этого, это привело к значительно более прямому маршруту, даже несмотря на то, что это означало больше изменений.

6. Заключение

В этой статье мы видели, что такое алгоритм АЗ, как он работает и как реализовать его в наших собственных проектах. Почему бы не взять это и продлить его для собственного использования?

Может быть, попытаться расширить его принять развязки между линиями метро во внимание, и посмотреть, как это влияет на выбранные маршруты?

И опять же, полный код для статьи доступен более на GitHub .