ルート計画、経路探索アルゴリズムの導入とコード実装

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

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

ダイクストラのアルゴリズムは、グラフ内の 2 つのポイント間の最短経路を見つけるための幅優先探索アルゴリズムです。アルゴリズムの考え方は次のとおりです。

最短経路が見つかった頂点を格納するためのセット S を作成します。

最短経路がまだ見つかっていない頂点を格納するためのセット Q を作成します。

距離配列 dist を初期化し、開始点から残りの点までの距離を無限大に設定し、開始点から開始点自体までの距離を 0 に設定します。

セット Q が空になるまで、次の手順を繰り返します。

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

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

以下は、C# で実装された Dijkstra アルゴリズムのソース コードです。

 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 < size; i++) { dist[i] = int.MaxValue; visited[i] = false; } dist[start] = 0; for (int count = 0; count < size - 1; count++) { int u = GetMinDistance(dist, visited); visited[u] = true; for (int v = 0; v < size; v++) { if (!visited[v] && graph[u, v] != 0 && dist[u] != int.MaxValue && dist[u] + graph[u, v] < dist[v]) { dist[v] = dist[u] + graph[u, v]; } } } return dist; } private int GetMinDistance(int[] dist, bool[] visited) { int minDist = int.MaxValue; int minIndex = -1; for (int v = 0; v < size; v++) { if (!visited[v] && dist[v] <= minDist) { minDist = dist[v]; minIndex = v; } } return minIndex; } }

アルゴリズム

アルゴリズムは、グラフ内の 2 つのポイント間の最短経路を見つけるためのヒューリスティック検索アルゴリズムです。アルゴリズムの考え方は次のとおりです。

探索する頂点を格納するための優先キュー openSet を作成します。

開始点から各頂点までの実際のコストを格納する配列 gScore を作成します。

各頂点を経由して目標地点に到達するための出発点の推定コストを格納する配列 fScore を作成します。

開始点をopenSetに追加し、gScore[start]を0に設定し、fScore[start]を開始点からターゲット点までの推定コストに設定します。

openSet が空になるまで、次の手順を繰り返します。

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

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

以下は、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 < size; neighbor++) { if (graph[current][neighbor] != 0 && !visited[neighbor]) { int tempGScore = gScore[current] + graph[current][neighbor]; if (tempGScore < gScore[neighbor]) { cameFrom[neighbor] = current; gScore[neighbor] = tempGScore; fScore[neighbor] = gScore[neighbor] + heuristicCostEstimate(neighbor, end); if (!openSet.contains(new Node(neighbor, fScore[neighbor]))) { openSet.offer(new Node(neighbor, fScore[neighbor])); } } } } } return null; } private int heuristicCostEstimate(int start, int end) { // 估计代价的计算方法，例如欧几里得距离、曼哈顿距离等return Math.abs(end - start); } private List<Integer> 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; } @Override public int compareTo(Node other) { return Integer.compare(this.fScore, other.fScore); } @Override public 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; } @Override public int hashCode() { return Objects.hash(index); } } }

上記は、アルゴリズムのアイデア、プロセス、C# または Java で実装されたソース コードを含む、ダイクストラ アルゴリズムと A* アルゴリズムの詳細な紹介です。どちらのアルゴリズムも一般的に使用される経路探索アルゴリズムであり、特定のニーズに応じて選択できます。
もちろん、今日の都市では、ナビゲーション ソフトウェアが私たちに代わって計画を立てることができます。