経路探索アルゴリズムとコード実装のルート計画分析について議論する

経路探索アルゴリズムは、コンピューター グラフィックスや人工知能の分野で一般的に使用されるアルゴリズムの 1 つで、ある点から地点までの最短経路または最適な経路を計算するために使用されます。別の。 。この記事では、一般的に使用される 2 つの経路探索アルゴリズムを詳しく紹介します。ダイクストラのアルゴリズムと A* アルゴリズム

ダイクストラのアルゴリズム

ダイクストラのアルゴリズム Itグラフ内の 2 点間の最短経路を見つけるために使用される幅優先検索アルゴリズムです。それは次のように機能します:

最短パスを見つけた頂点を保存するためにセット S を作成する必要があります。

最短パスをまだ見つけていない頂点を保存するために使用されるセット Q

距離配列 dist を初期化するときは、開始点から他の点までの距離を無限大に設定する必要があります。 、開始点からそれ自体までの距離は 0

に設定されます。集合 Q が空になるまで次の手順を繰り返します。

• セット Q 頂点 u 内の開始点への最も近い距離を見つけて、それをセット S に追加します。
• 頂点 u の各隣接頂点 v について、dist[v] > dist[u] の場合、始点から v までの距離 dist[v] を更新します。edge(u, v ) を実行し、dist[v] を dist[u]edge(u, v) に更新します。

最後に、dist 配列には始点から各頂点までの最短パスが格納されます。

C# ソースでは次のように記述されます。ダイクストラ アルゴリズムのコード:

class DijkstraAlgorithm
{
    private int[,] graph;
    private int size;

    public DijkstraAlgorithm(int[,] graph)
    {
        this.graph = graph;
        this.size = graph.GetLength(0);
    }

    public int[] FindShortestPath(int start, int end)
    {
        int[] dist = new int[size];
        bool[] visited = new bool[size];

        for (int i = 0; i <h4><span>アルゴリズム</span></h4><p>##アルゴリズムは、グラフ内の 2 点間の最短経路を見つけるために使用されるヒューリスティック検索アルゴリズムです。彼ら。アルゴリズムの考え方は次のとおりです。 <span></span></p><p>探索する頂点を保存する優先キュー openSet を作成します。<span></span></p><p>次のことを行う必要があります。開始点から各頂点までの実際のコストを保存するには、gScore という名前の配列を作成します。<span></span></p><p>開始点から各頂点までの推定コストを保存するには、fScore という名前の配列を作成する必要があります。ターゲット ポイント<span> </span></p><p>開始ポイントを openSet に追加し、gScore[start] を 0 に設定し、fScore[start] を開始ポイントからターゲット ポイントまでの推定コストに設定します。 <span></span></p>openSet が空になるまで次の手順を繰り返します。 <p><span></span></p>

openSet 内で fScore が最も小さい現在の頂点を見つけます。
current がターゲット ポイントと等しい場合、最短経路が見つかったことを意味し、その経路が返されます。
openSet から現在を削除します。
現在の近隣頂点の近隣頂点ごとに、開始点から近隣頂点までの実際のコスト tempGScore を計算します。tempGScore が gScore[neighbor] より小さい場合、gScore[neighbor] を tempGScore に更新します。 、 fScore[neighbor] = gScore[neighbor] 推定コストを計算します。ネイバーが openSet にない場合は、openSet に追加します。

openSet が空の場合は、ターゲット ポイントに到達できないことを意味し、null 値が返されます。

次は、 Java で書かれた A* アルゴリズムのソース コード:

import java.util.*;class AStarAlgorithm {private int[][] graph;private int size;public AStarAlgorithm(int[][] graph) {this.graph = graph;this.size = graph.length;}public List<integer> findShortestPath(int start, int end) {PriorityQueue<node> openSet = new PriorityQueue();int[] gScore = new int[size];int[] fScore = new int[size];int[] cameFrom = new int[size];boolean[] visited = new boolean[size];Arrays.fill(gScore, Integer.MAX_VALUE);Arrays.fill(fScore, Integer.MAX_VALUE);Arrays.fill(cameFrom, -1);gScore[start] = 0;fScore[start] = heuristicCostEstimate(start, end);openSet.offer(new Node(start, fScore[start]));while (!openSet.isEmpty()) {int current = openSet.poll().index;if (current == end) {return reconstructPath(cameFrom, current);}visited[current] = true;for (int neighbor = 0; neighbor  reconstructPath(int[] cameFrom, int current) {List<integer> path = new ArrayList();path.add(current);while (cameFrom[current] != -1) {current = cameFrom[current];path.add(0, current);}return path;}private class Node implements Comparable<node> {public int index;public int fScore;public Node(int index, int fScore) {this.index = index;this.fScore = fScore;}@Overridepublic int compareTo(Node other) {return Integer.compare(this.fScore, other.fScore);}@Overridepublic boolean equals(Object obj) {if (this == obj) {return true;}if (obj == null || getClass() != obj.getClass()) {return false;}Node other = (Node) obj;return index == other.index;}@Overridepublic int hashCode() {return Objects.hash(index);}}}</node></integer></node></integer>

上記は、アルゴリズムのアイデア、プロセス、実装されたソース コードを含む、ダイクストラ アルゴリズムと A* アルゴリズムの詳細な紹介です。 C# または Java で。これら 2 つのアルゴリズムは一般的に使用される経路探索アルゴリズムであり、特定のニーズに応じて選択して使用できます。

もちろん、今日の都市では、ナビゲーション ソフトウェアが計画を立ててくれます。

以上が経路探索アルゴリズムとコード実装のルート計画分析について議論するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。