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

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

経路探索アルゴリズムは、コンピュータグラフィックスや人工知能の分野で一般的に使用されるアルゴリズムの 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* アルゴリズムの詳細な紹介です。どちらのアルゴリズムも一般的に使用される経路探索アルゴリズムであり、特定のニーズに応じて選択できます。
もちろん、今日の都市では、ナビゲーション ソフトウェアが私たちに代わって計画を立てることができます。

<<: 

>>: 

ブログ    

推薦する

よく使われる「生成AIフレームワーク」を1つの記事で理解する

こんにちは、皆さん。私は Luga です。今日は、人工知能 (AI) エコシステムに関連するテクノロ...

光害を拒否し、AIがスマートシティの交通安全構築を推進

「ある瞬間、目の前のすべてがぼやけて、前方の道路状況がまったく見えませんでした。とても危険でした!」...

エッジAIがスマートホームの未来である理由

今日では、エッジに接続されるデバイスがますます増えています。さらに良いことに、人工知能と機械学習のお...

...

滴滴出行の米国研究責任者:インテリジェント運転は間違いなく未来を変えるだろうが、そのプロセスは単純ではない

6月20日、滴滴出行研究院副院長兼アメリカ研究院長のゴン・フェンミン博士が、TechCrunch I...

...

ひどい、顔認識の練習のための40行のコード

最近、恐れることなく赤信号を無視していた人々が交通警察署に電話し、交通警察のおじさんに自分の写真を削...

上位 10 の古典的なソート アルゴリズムの詳細な説明: バブル ソート、選択ソート、挿入ソート

[[377307]] 1. アルゴリズムの評価基準ソートアルゴリズムを説明する前に、まずアルゴリズム...

大手各社が相次いで「敗北を認める」。自動運転の実用化に目途は立つのか?

[[263741]]自動運転は短期間で実現できるのか?数年前なら、大手各社はおそらく肯定的な答えを...

AIがコンテンツマーケティングを進化させる方法

デジタル メディアはほぼすべての人の日常生活に浸透し、私たちのあらゆる活動に永続的な影響を及ぼしてい...

...

Microsoft、SAP、Oracle などの世界的なソフトウェア大手は、生成 AI をどのように取り入れているのでしょうか?

2023年は、生成AIテクノロジーが大きな進歩を遂げる年です。ChatGPTなどのAIツールはテク...

...

AI スタートアップの品質を測定するにはどうすればよいでしょうか?

編集者注: Zetta Venture のパートナーである Ivy Nguyen 氏は最近、Tech...

テンセントがまた何か新しいことをやっています!たった一言で絵をアニメの主人公に変身させよう!

執筆者 | Qingzhu制作:51CTO テクノロジースタック(WeChat ID:blog) 2...