JavaでのA*パスファインディングの実装

投稿日: 2022-11-08 2022-11-08
タグ: Algorithms, Java

1. 序章

パスファインディングアルゴリズムは、マップをナビゲートするための手法です。これにより、2つの異なるポイント間のルートを見つけることができます。アルゴリズムが異なれば、長所と短所も異なります。多くの場合、アルゴリズムの効率と、アルゴリズムが生成するルートの効率の点で異なります。

2. パスファインディングアルゴリズムとは何ですか？

パスファインディングアルゴリズムは、ノードとエッジで構成されるグラフをグラフを通るルートに変換する手法です。このグラフは、トラバースが必要なものであれば何でもかまいません。この記事では、ロンドン地下鉄システムの一部を横断しようとします。

（sameboatによる「LondonUndergroundOverground DLR Crossrail map 」は、 CC BY-SA 4.0 の下でライセンスされています）

これには多くの興味深いコンポーネントがあります。

始点と終点の間に直接ルートがある場合とない場合があります。たとえば、「アールズコート」から「モニュメント」に直接移動することはできますが、「エンジェル」に移動することはできません。
すべてのステップには特定のコストがかかります。私たちの場合、これは駅間の距離です。
各ストップは、他のストップの小さなサブセットにのみ接続されています。たとえば、「リージェンツパーク」は「ベイカーストリート」と「オックスフォードサーカス」にのみ直接接続されています。

すべてのパスファインディングアルゴリズムは、すべてのノード（この場合はステーション）のコレクションとそれらの間の接続、および目的の開始点と終了点を入力として受け取ります。 出力は通常、最初から最後まで、に進む必要がある順序で取得するノードのセットです。

**3. A *とは何ですか？**

A *は、1968年にPeter Hart、Nils Nilsson、およびBertramRaphaelによって最初に公開された特定のパスファインディングアルゴリズムの1つです。 ルートを事前に計算する機会がなく、メモリ使用量に制約がない場合に使用するのが一般的に最適なアルゴリズムであると考えられています。

最悪の場合、メモリとパフォーマンスの両方の複雑さが O（b ^ d）になる可能性があるため、常に最も効率的なルートが機能しますが、常に最も効率的な方法であるとは限りません。

A *は、実際にはダイクストラのアルゴリズムのバリエーションであり、使用する次のノードの選択に役立つ追加情報が提供されています。この追加情報は完全である必要はありません。すでに完全な情報がある場合、パスファインディングは無意味です。しかし、それが優れているほど、最終結果は良くなります。

**4. A *はどのように機能しますか？**

A *アルゴリズムは、これまでの最適なルートを繰り返し選択し、次の最適なステップを確認することで機能します。

このアルゴリズムを使用する場合、追跡する必要のあるデータがいくつかあります。「オープンセット」は、現在検討しているすべてのノードです。これはシステム内のすべてのノードではありませんが、代わりに、次のステップを実行する可能性のあるすべてのノードです。

また、システム内の各ノードの現在の最高スコア、推定合計スコア、および現在の最高の前のノードを追跡します。

この一環として、2つの異なるスコアを計算できる必要があります。 1つは、あるノードから次のノードに取得するスコアです。 2つ目は、任意のノードから宛先までのコストの見積もりを提供するヒューリスティックです。この見積もりは正確である必要はありませんが、精度が高いほど、より良い結果が得られます。唯一の要件は、両方のスコアが互いに一致していること、つまり、同じ単位にあることです。

当初、オープンセットは開始ノードで構成されており、他のノードに関する情報はまったくありません。

各反復で、次のことを行います。

推定合計スコアが最も低いオープンセットからノードを選択します
このノードをオープンセットから削除します
オープンセットに、そこから到達できるすべてのノードを追加します

これを行うときは、このノードから新しいスコアごとに新しいスコアを計算して、これまでのスコアが改善されているかどうかを確認し、改善されている場合は、そのノードについてわかっていることを更新します。

次に、これは、推定合計スコアが最も低いオープンセット内のノードが宛先になるまで繰り返され、その時点でルートが取得されます。

4.1. 実施例

たとえば、「メリルボーン」から始めて、「ボンドストリート」への道を見つけてみましょう。

当初、私たちのオープンセットは「メリルボーン」のみで構成されています。これは、これが暗黙的に、最高の「推定合計スコア」を取得したノードであることを意味します。

次の停車駅は、0.4403kmの「EdgwareRoad」または0.4153kmの「BakerStreet」のいずれかです。ただし、「Edgware Road」の方向が間違っているため、ここから目的地までのヒューリスティックスコアは1.4284 kmですが、「BakerStreet」のヒューリスティックスコアは1.0753kmです。

つまり、この反復の後、オープンセットは2つのエントリで構成されます。推定合計スコアが1.8687kmの「EdgwareRoad」と推定合計スコアが1.4906kmの「BakerStreet」です。

2回目の反復は、推定合計スコアが最も低い「ベイカーストリート」から開始します。ここから、次の停車地は「メリルボーン」、「セント。ジョンズウッド」、「グレートポートランドストリート」、リージェンツパーク」、または「ボンドストリート」。

これらすべてに取り組むわけではありませんが、興味深い例として「メリルボーン」を取り上げましょう。そこに到達するためのコストは再び0.4153kmですが、これは合計コストが0.8306kmになったことを意味します。さらに、ここから目的地までのヒューリスティックにより、1.323kmのスコアが得られます。

これは、推定合計スコアが2.1536 kmになることを意味します。これは、このノードの以前のスコアよりも悪いです。この場合、どこにも行かなくなるために余分な作業を行う必要があったため、これは理にかなっています。これは、これを実行可能なルートとは見なさないことを意味します。そのため、「メリルボーン」の詳細は更新されず、オープンセットに追加されません。

5. Javaの実装

これがどのように機能するかについて説明したので、実際に実装してみましょう。 一般的なソリューションを構築し、ロンドン地下鉄で機能するために必要なコードを実装します。これらの特定の部分のみを実装することで、他のシナリオで使用できます。

5.1. グラフの表現

最初に、トラバースしたいグラフを表現できる必要があります。これは、個々のノードとグラフ全体の2つのクラスで構成されます。

GraphNodeと呼ばれるインターフェースで個々のノードを表します。

public interface GraphNode {
    String getId();
}

各ノードにはIDが必要です。他のものはこの特定のグラフに固有であり、一般的なソリューションには必要ありません。 これらのクラスは、特別なロジックのない単純なJavaBeanです。

全体的なグラフは、単に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. 私たちのルートのステップ

次に必要なのは、グラフからルートを見つけるためのメカニズムです。

これの最初の部分は、任意の2つのノード間でスコアを生成する方法です。次のノードへのスコアと宛先への推定の両方のScorerインターフェースを使用します。

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

開始ノードと終了ノードが与えられると、それらの間を移動するためのスコアを取得します。

追加情報を運ぶノードのラッパーも必要です。GraphNode ではなく、 RouteNode です。これは、計算されたノードであるためです。グラフ全体で1つではなくルート：

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。ノードにアクセスしていて、それに関する追加情報はまだありません。

ただし、これらも比較可能である必要があります。これにより、アルゴリズムの一部として推定スコアで並べ替えることができます。これは、要件を満たすために compareTo（）メソッドを追加することを意味します。 Compareable インターフェースの例：

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

通過するルートを見つけているグラフと、2つのスコアラーがあります。1つは次のノードの正確なスコア、もう1つは目的地までの推定スコアです。また、開始ノードと終了ノードを取得して、2つの間の最適なルートを計算するメソッドもあります。

この方法は、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の実装が1つだけ必要です。これにはHaversine式を使用して、緯度/経度の2つのペア間の直線距離を計算します。

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

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.

ルートのマッピングに使用しましょう。アールズコートからエンジェルまで生成します。これには、少なくとも2本のチューブラインで、さまざまな移動オプションがあります。

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

これにより、アールズコート->サウスケンジントン->グリーンパーク->ユーストン->エンジェルのルートが生成されます。

多くの人がたどる明らかなルートは、変更が少ないため、アールズカウント->モニュメント->エンジェルでしょう。代わりに、これは、より多くの変更を意味するにもかかわらず、大幅に直接的なルートを取りました。

6. 結論

この記事では、A *アルゴリズムとは何か、それがどのように機能するか、そしてそれを私たち自身のプロジェクトに実装する方法を見てきました。これを持って自分の用途に拡張してみませんか？

たぶんそれを拡張して、チューブライン間のインターチェンジを考慮に入れて、それが選択されたルートにどのように影響するかを確認してみてください。

また、この記事の完全なコードは、GitHubでから入手できます。

getdocs

13036