Java中实现A*寻路算法

codingman included in Algorithms Java

2020-02-06 3850 words 8 minutes

Contents

1. 简介

寻路算法是导航地图的技术，允许我们找到两个不同点之间的路线。不同的算法有不同的优缺点，通常在算法的效率和它生成的路线的效率方面。

2. 什么是寻路算法？

寻路算法是一种将由节点和边组成的图转换为通过图的路线的技术。这个图可以是任何需要遍历的东西。在本文中，我们将尝试穿越伦敦地铁系统的一部分：

（“伦敦地铁地上 DLR Crossrail 地图 ”由sameboat 获得 CC BY-SA 4.0 许可）

这有很多有趣的组件：

我们的起点和终点之间可能有也可能没有直接路线。例如，我们可以直接从“伯爵府”到“纪念碑”，但不能到“天使”。
每一步都有特定的成本。在我们的例子中，这是车站之间的距离。
每个站点只连接到其他站点的一小部分。例如，“摄政公园”仅与“贝克街”和“牛津马戏团”直接相连。

所有寻路算法都将所有节点的集合（在我们的例子中为站点）和它们之间的连接以及所需的起点和终点作为输入。输出通常是一组节点，它们将按照我们需要的顺序从头到尾引导我们。

3. 什么是 A*？

A* 是一种特定的寻路算法，由 Peter Hart、Nils Nilsson 和 Bertram Raphael 于 1968 年首次发表。当没有机会预先计算路线并且对内存使用没有限制时，它通常被认为是最好的算法。在最坏的情况下，内存和性能复杂度都可能是O(b^d)，因此虽然它总是能找到最有效的路线，但它并不总是最有效的方法。

A* 实际上是Dijkstra 算法的一种变体，其中提供了额外的信息来帮助选择下一个要使用的节点。这些额外的信息不需要是完美的——如果我们已经有了完美的信息，那么寻路是没有意义的。但它越好，最终的结果就会越好。

4. A* 是如何工作的？

A* 算法的工作原理是迭代地选择迄今为止最好的路线，并尝试查看最好的下一步是什么。 使用此算法时，我们需要跟踪几条数据。“开放集”是我们当前正在考虑的所有节点。这不是系统中的每个节点，而是我们可能从中进行下一步的每个节点。

我们还将跟踪系统中每个节点的当前最佳分数、估计总分数和当前最佳先前节点。作为其中的一部分，我们需要能够计算两个不同的分数。一是从一个节点到下一个节点的得分。第二个是启发式方法，用于估计从任何节点到目的地的成本。这个估计不需要准确，但更高的准确度会产生更好的结果。唯一的要求是两个分数彼此一致——也就是说，它们的单位相同。

一开始，我们的开放集由我们的起始节点组成，我们根本没有任何其他节点的信息。

在每次迭代中，我们将：

从我们的开放集中选择具有最低估计总分的节点
从开放集中删除该节点
将我们可以从中访问的所有节点添加到开放集中当我们这样做时，我们还计算出从这个节点到每个新节点的新分数，看看它是否比我们迄今为止所获得的有所改进，如果是，那么我们更新我们对该节点的了解。

然后重复此过程，直到我们的开放集中具有最低估计总分的节点是我们的目的地，此时我们已经有了我们的路线。

4.1. 工作示例

例如，让我们从“马里波恩”开始，尝试找到通往“邦德街”的路。

一开始，我们的开放集仅包含“Marylebone”。这意味着这隐含地是我们获得最佳“估计总分”的节点。

我们的下一站可以是“Edgware Road”，费用为 0.4403 公里，也可以是“Baker Street”，费用为 0.4153 公里。然而，“Edgware Road”的方向是错误的，所以我们从这里到目的地的启发式得分为 1.4284 公里，而“贝克街”的启发式得分为 1.0753 公里。

这意味着在这次迭代之后，我们的开放集包含两个条目——“Edgware Road”，估计总得分为 1.8687 公里，以及“贝克街”，估计总得分为 1.4906 公里。

**然后我们的第二次迭代将从“贝克街”开始，因为这具有最低的估计总分。**从这里开始，我们的下一站可以是“马里波恩”、“圣。John’s Wood”、“Great Portland Street”、Regent’s Park”或“Bond Street”。我们不会处理所有这些，但让我们以“Marylebone”作为一个有趣的例子。到达那里的成本又是 0.4153 公里，但这意味着总成本现在是 0.8306 公里。此外，从这里到目的地的启发式得分为 1.323 公里。 **这意味着估计的总得分为 2.1536 公里，比该节点之前的得分*差。***这是有道理的，因为在这种情况下，我们不得不做额外的工作才能一事无成。这意味着我们不会认为这是一条可行的路线。因此，“Marylebone”的详细信息没有更新，也没有添加回开放集。

5. Java实现

现在我们已经讨论了它是如何工作的，让我们实际实现它。**我们将构建一个通用解决方案，然后我们将实现它为伦敦地铁工作所必需的代码。**然后，我们可以通过仅实现那些特定部分来将其用于其他场景。

5.1. 表示图形

**首先，我们需要能够表示我们希望遍历的图。**这由两个类组成——单个节点，然后是整个图。我们将使用一个名为GraphNode的接口来表示我们的各个节点：

public interface GraphNode {
    String getId();
}

我们的每个节点都必须有一个 ID。其他任何东西都特定于这个特定的图表，一般解决方案不需要。这些类是没有特殊逻辑的简单 Java Bean。

然后，我们的整个图由一个简单地称为 Graph的类表示：

public class Graph<T extends GraphNode> {
    private final Set<T> nodes;
    private final Map<String, Set<String>> 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<T> getConnections(T node) {
        return connections.get(node.getId()).stream()
            .map(this::getNode)
            .collect(Collectors.toSet());
    }
}

**这将所有节点存储在我们的图中，并且知道哪些节点连接到哪些节点。**然后我们可以通过 ID 获取任何节点，或连接到给定节点的所有节点。在这一点上，我们能够表示我们希望的任何形式的图，在任意数量的节点之间有任意数量的边。

5.2. 我们路线上的步骤

接下来我们需要的是通过图表查找路线的机制。

**第一部分是在任意两个节点之间生成分数的某种方式。**我们将为下一个节点的得分和目的地的估计提供Scorer接口：

public interface Scorer<T extends GraphNode> {
    double computeCost(T from, T to);
}

给定一个起点和一个终点节点，然后我们会得到在它们之间旅行的分数。 **我们还需要一个包含一些额外信息的节点包装器。**这不是一个 GraphNode，而是一个RouteNode ——因为它是我们计算的路由中的一个节点，而不是整个图中的一个节点：

class RouteNode<T extends GraphNode> implements Comparable<RouteNode> {
    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;
    }
}

**与 GraphNode 一样，这些是简单的 Java Bean，用于存储每个节点的当前状态以进行当前路由计算。**我们为常见情况提供了一个简单的构造函数，当我们第一次访问一个节点并且还没有关于它的其他信息时。

**不过，这些也需要是Comparable的，这样我们就可以根据估计的分数对它们进行排序，作为算法的一部分。**这意味着添加 compareTo()方法来满足Comparable接口的要求：

@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. 寻找我们的路线

现在我们可以在我们的图表中实际生成我们的路线了。这将是一个名为 RouteFinder的类：

public class RouteFinder<T extends GraphNode> {
    private final Graph<T> graph;
    private final Scorer<T> nextNodeScorer;
    private final Scorer<T> targetScorer;
    public List<T> findRoute(T from, T to) {
        throw new IllegalStateException("No route found");
    }
}

我们有我们正在寻找路线的图表，以及我们的两个计分器——一个用于下一个节点的确切分数，一个用于到我们目的地的估计分数。我们还有一个方法，它会采用一个起点和终点节点并计算两者之间的最佳路线。

这个方法就是我们的A*算法。我们所有其余的代码都在这个方法中。

我们从一些基本设置开始——我们可以将其视为下一步的“开放集”节点，以及到目前为止我们访问过的每个节点的地图以及我们对它的了解：

Queue<RouteNode> openSet = new PriorityQueue<>();
Map<T, RouteNode<T>> allNodes = new HashMap<>();
RouteNode<T> start = new RouteNode<>(from, null, 0d, targetScorer.computeCost(from, to));
openSet.add(start);
allNodes.put(from, start);

我们的开放集最初只有一个节点——我们的起点。没有之前的节点，到达那里的分数为 0，我们估计它离目的地有多远。

对开放集使用PriorityQueue意味着我们可以根据之前的 *compareTo()*方法自动从中获取最佳条目。现在我们迭代直到我们用完节点来查看，或者最好的可用节点是我们的目的地：

while (!openSet.isEmpty()) {
    RouteNode<T> next = openSet.poll();
    if (next.getCurrent().equals(to)) {
        List<T> route = new ArrayList<>();
        RouteNode<T> current = next;
        do {
            route.add(0, current.getCurrent());
            current = allNodes.get(current.getPrevious());
        } while (current != null);
        return route;
    }
    // ...

当我们找到我们的目的地后，我们可以通过反复查看前一个节点来构建我们的路线，直到我们到达我们的起点。 接下来，如果我们还没有到达目的地，我们可以制定下一步该做什么：

    graph.getConnections(next.getCurrent()).forEach(connection -> { 
        RouteNode<T> 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");
}

在这里，我们正在遍历图中的连接节点。对于其中的每一个，我们都获得了我们拥有的RouteNode——如果需要，创建一个新的。

然后我们计算这个节点的新分数，看看它是否比我们迄今为止的便宜。如果是，那么我们更新它以匹配这条新路线并将其添加到开放集以供下次考虑。

**这是整个算法。**我们不断重复这一点，直到我们达到目标或未能达到目标。

5.4. 伦敦地铁的具体细节

**到目前为止，我们拥有的是一个通用的 A* 探路者，**但它缺乏我们确切用例所需的细节。这意味着我们需要GraphNode和 Scorer的具体实现。

我们的节点是地下车站，我们将使用Station类对它们进行建模：

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

名字对于查看输出很有用，经纬度是给我们打分的。在这种情况下，我们只需要一个Scorer的实现。为此，我们将使用Haversine 公式来计算两对纬度/经度之间的直线距离：

public class HaversineScorer implements Scorer<Station> {
    @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;
    }
}

让我们用它来绘制路线。我们将从 Earl’s Court 到 Angel 生成一个。这有许多不同的旅行选择，至少有两条管道：

public void findRoute() {
    List<Station> 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 -> Green Park -> Euston -> Angel 的路线。

许多人会采取的明显路线可能是伯爵伯爵->纪念碑->天使，因为更改较少。相反，尽管这意味着更多的变化，但它采取了更直接的途径。