A*、ダイクストラ、BFS 経路探索アルゴリズムの視覚的な説明

この記事はLeiphone.comから転載したものです。転載する場合は、Leiphone.com公式サイトにアクセスして許可を申請してください。

幅優先探索、ダイクストラ法、A* 法は、グラフ上の 3 つの典型的なパス プランニングアルゴリズムです。どちらもグラフ検索に使用できますが、違いはキューとヒューリスティック関数という 2 つのパラメータにあります。

このプロジェクトでは、選択されたパラメータに基づいてさまざまなアルゴリズムがグラフ検索を実行する方法を調査し、視覚化します。

アルゴリズムの一般原則は次のとおりです。

開始ノードを含むキューへのフロンティアを初期化します。

フロンティア キューが空でない場合、「現在の」ノードが「訪問」されてキューから削除され、訪問されたノードの各隣接ノードがキューに追加されます。そのコストは、現在のノードに到達するコスト、現在のノードから隣接ノードを訪問するコスト、隣接ノードとターゲット ノードのヒューリスティック関数値の合計です。ヒューリスティック関数は、2 つのノード間のパス コストを推定します。

アクセス パス (通常は cameFrom グラフ) を保存すると、後でパスを再構築できるようになります。隣接ノードがすでにリスト内にあり、新しいパスのコストが低い場合は、そのコストを変更します。

ターゲット パスが見つかった場合 (早期終了)、またはリストが空の場合、アルゴリズムは停止します。

ＢＦＳ

先入れ先出しキューを使用して BFS を実装します。このキューは、パス内のリンクのコストを無視し、ホップ数に応じてスケーリングするため、ホップ関連のコストが最小の最短パスが確実に見つかります。ヒューリスティック関数の選択は任意であり、このプロセスでは役割を果たしません。

配列を使用すると、要素が末尾に追加され、先頭から削除される先入れ先出しアプローチを実装できます。

BFS デモアニメーション。境界ノード (黄色) がグリッド内の正方形に拡張されていることに注意してください。ここで、正方形は同じ「ホップ距離」のノードのセットです。

ダイクストラ

グラフ上の優先キューと常に 0 を返すヒューリスティック関数を使用すると、ダイクストラのアルゴリズムが得られます。

BFS と比較した場合、Dijkstra の最大の違いはコストを考慮していることです。このアルゴリズムを使用すると、ノード間のコストに基づいて最短パスを見つけることができます。

優先キューは配列を使用して実装され、新しいノードが挿入されるたびにソートされます。優先キューを実装するより効率的な方法は他にもありますが、このシナリオでは、配列は十分に高速で実装も簡単です。

Dijkstra はアニメーションを示しています。境界が円になっていることに注意してください。

A*

A*アルゴリズムを実装するには、2 つのノード間のユークリッド距離などの実際のヒューリスティック関数を渡す必要があります。ノードは「ノード コスト」+「ノードからターゲット ノードまでの推定コスト」によって重み付けされ、より可能性の高いノードを優先することで検索が高速化されます。

ヒューリスティックの助けを借りて、A* は Dijkstra や BFS よりも速く正しいパスを見つけることができます。

許容されないヒューリスティック関数

A* は、許容されるヒューリスティック関数を適用することによってのみ最短経路を見つけることができます。つまり、アルゴリズムが実際の経路の長さを過大評価することは決してありません。ユークリッド距離は 2 点間の最短距離/経路であるため、ユークリッド距離を超えることはできません。

しかし、定数 k>0 を掛けるとどうなるでしょうか?これにより、距離が過大評価され、許容されないヒューリスティック関数になります。

k 値が大きいほど、アルゴリズムがターゲットに到達しやすくなりますが、同時に精度が低下し、生成されるパスが必ずしも最短にならない場合があります。

アルゴリズムの実装

このプロジェクトは、読者が Web 上でアクセスできるようにJavaスクリプトを通じて実装されています。また、UI のレンダリングには react を使用し、グラフィックのレンダリングには react-konva を使用しています。

パス検出は、キュー タイプとヒューリスティック関数を受け入れ、実際のパス検出 (カリー化と呼ばれる) という別の関数を返すものです。

この方法では、ユーザーが設定を変更するたびに、決定されたパラメータを使用して新しいパス検出関数が作成され、グラフ検索に使用されます。

パス検出の手順を視覚化するために、JavaScript ジェネレーターを使用します。つまり、関数は値だけでなく反復子を返します。したがって、各ステップで、訪問者はアルゴリズムの状態全体を生成し、それを配列に保存し、ページ上部のスライダーを介して特定の状態を表示できます。

このリンクをクリックすると、インタラクティブなデモ ページに移動します: https://interactive-pathfinding.netlify.com/