「BFS、DFS、ダイクストラ、A*アルゴリズムの普遍的な実装」

BFS, DFS, Dijkstra, A* algorithms universal implementation.

よく知られているBFS、DFS、Dijkstra、A-Starなどのアルゴリズムは、本質的に同じアルゴリズムのバリエーションであることがわかりました。

つまり、コアコンポーネントの変更を必要とせずに、これらのアルゴリズム間を切り替えることができる汎用的なデータ構造を実装することが可能です。いくつかの制約はありますが、このアプローチを探求することは興味深いです。

これらのアルゴリズムのすべての動作するコードは、こちらの私のGitHubリポジトリで見つけることができます。この記事を読みながらコードを試してみることをおすすめします。実践的な経験は理論的な理解以上に学習を向上させるからです。

グラフの表現

左上のノード0から右下のノード24までのパスを見つけることを目指す、25個のノードが5×5のグリッドに配置されたグラフを考えてみましょう。

• このAI研究は、近くの電話によって記録されたキーストロークを聞くことで、95％の正確さでデータを盗むことができるディープラーニングモデルを紹介しています
• 「フィル・ザ・ギャップス：フィリピンの2022年貿易ネットワークの隠されたつながりを解明する」
• 「生データから洗練されたデータへ：データの前処理を通じた旅 – パート2：欠損値」

これらのアルゴリズムのどれもこれを達成することができますが、それぞれ独自の制約があります。

• BFSとDFSのアルゴリズムは、エッジの重みを無視して非重み付きグラフで動作します。任意のパスを見つけることはできますが、最適なパスを保証しません。
• DijkstraとA-Starのアルゴリズムは、重み付きグラフで動作しますが、負の重みを含むグラフでは使用しないでください。A-Starは最適化により通常よりも高速です。パス探索中にユークリッド座標を組み込んでいます。

この記事では基本的な概念はカバーしていませんので、既にそれらについておなじみであることを期待しています。上記の用語が難しく感じる場合は、基本的な知識も学んでおくことをお勧めします。ただし、これらのコード例で遊ぶことはまだ楽しいです。

これらの制約を考慮するために、各ノード（X、Y）に架空の座標を割り当てましょう。

最後に、グラフ内のすべてのエッジにいくつかの重みを割り当てましょう。

C++では、この構造は次のように表現されます：

グラフ内のエッジリストは、グラフ内の各エッジの出口ノード番号に対応するインデックスの配列によって表されます。その後、各要素は値のペアを含みます：

1. グラフ内の各エッジの入力ノード番号。
2. エッジの重み。

このシンプルな構造を使用することで、グラフ内のすべてのノードをトラバースし、その接続に関するすべての必要な情報を取得できます：

それでは、グラフ内のいくつかのカスタムな接続を作成して、汎用アルゴリズムの動作にどのような影響があるか観察しましょう。このコードはここではメインの焦点ではないため、関連するメソッドへのリンクを提供します：

• ノードのリストを生成する
• カスタムな接続を作成する

また、このグラフ内のすべての接続と重みを遅延生成する方法もありますが、このアプローチはアルゴリズムがグラフをトラバースする方法の実際の違いを包括的に理解することができないかもしれません。

汎用アルゴリズム

汎用の経路探索アルゴリズムの中核には、このプロジェクトでは「キュー」と呼ぶ汎用データ構造があります。ただし、これはクラシックなFIFO（先入れ先出し）データ構造ではありません。代わりに、使用されているアルゴリズムに基づいてキューイングメカニズムを変更できる一般的な構造です。この「キュー」のインターフェースはシンプルです：

キューの詳細に入る前に、トラバースアルゴリズム自体を調べてみましょう。

基本的には、典型的なA-StarやDijkstraアルゴリズムによく似ています。まず、次の操作を可能にするコレクションのセットを初期化する必要があります：

• 処理されていないノード（白色）、現在処理中のノード（灰色）、処理済み/訪問済みのノード（黒色）のリストを維持する。
• 開始ノードから各ノードへの最短パスの現在の距離を追跡する。
• 最終的なパスを再構築するために前後のノードのペアのリストを保存する。

main.cppの18行目：

次に、データ構造を初期化する必要があります。GitHubリポジトリで提供されるコードを使用することで、必要な行のコメントを解除するだけで簡単に初期化できます。パラメータに基づいてデータ構造を選択するようなコードは用意されていません。より良い理解を得るために積極的に実験していただきたいからです（はい、私は厳しいです :D）。

最後に、アルゴリズム自体です。基本的には3つのアルゴリズムの組み合わせで、いくつかの追加のチェックがあります。”customQueue”を初期化し、空になるまでアルゴリズムを実行します。グラフ内の各隣接ノードを調べる際に、次にトラバースする必要があるノードをすべてキューに追加します。次に、アルゴリズム内で次にトラバースするノードを1つだけ取り出す getFirst()メソッドを呼び出します。

main.cpp#L48:

この時点までの実装は、本やインターネットで見つけることができる他の例と大差ありません。しかし、ここが重要なポイントです – getFirst() は、ノードのトラバースの正確な順序を決定するためのメソッドです。

BFS キュー

キューデータ構造の内部動作を詳しく見てみましょう。BFSのキューインターフェースは最もシンプルなものです。bfsQueue.h#L11:

実際のところ、ここでカスタムキューインターフェースを標準のC++キューで置き換えることもできます（STL（Standard Template Library）によって提供される）。しかし、ここでは普遍性を目指しています。今、メインメソッドの行のコメントを解除してこのアルゴリズムを実行するだけです：//bfsQueue customQueue; // UNCOMMENT TO USE BFS

その結果、BFSはパス 24<-19<-14<-9<-8<-7<-6<-1<-0 を見つけます。

重みを考慮すると、このパスの最終コストは11になります。ただし、BFSもDFSも重みを考慮しません。代わりに、グラフ内のすべてのノードをトラバースし、早かれ遅かれ目的のノードを見つけようとします。

DFS キュー

DFSはあまり異なって見えません。ただし、STDキューをスタックに置き換えるだけです。dfsStack.h#L11:

DFSは、コストの最適化を優先することなく、パス 24<-23<-22<-21<-20<-15<-10<-5<-0 を見つけます。興味深いことに、BFSとは逆の方向にトラバースします。

ダイクストラ キュー

ダイクストラのアルゴリズムは、グラフで最もよく知られた貪欲探索アルゴリズムです。負のパス、サイクルなどを処理できないという既知の制約がありますが、それでも人気があり十分に効率的です。

この実装では、getFirst() メソッドが貪欲アプローチを使用してノードを選択するために使われることに注意してください。dijkstraQueue.h#L17:

ダイクストラのアルゴリズムは、コストが最も低く最適なパス 24<-19<-18<-13<-12<-7<-6<-1<-0 を見つけます。

A-Star

A-Star アルゴリズムは、座標を持つユークリッド空間（地図など）でのパス探索に特に適しています。これがゲームで広く使用される理由です。最小の重みに基づく「盲目の」貪欲探索だけでなく、ゴールまでのユークリッド距離も考慮します。その結果、実用的なシナリオでは通常、ダイクストラのアルゴリズムよりもはるかに効率的です（詳細については、他のGitHubプロジェクトを参照してください）。aStarQueue.h#L18:

その結果、最適なルートを提供するため、ダイクストラのアルゴリズムと同じ結果が得られます。

この例では、これらのアルゴリズム間の実際のパフォーマンスの違いを示すには簡素すぎるかもしれません。これらのアルゴリズムの潜在能力を探求する興味がある場合は、テストデータの幅広い範囲を使用し、効率的にこれらのアルゴリズムを実装する他のプロジェクトを参照してください。

デメリット

ただし、ダイクストラとA-Starのアルゴリズムには問題があります…上記の実装では、ユニバーサルデータ構造内でベクター（動的配列 []）が使用されています。 getFirst() の呼び出しごとに、ベクター内で必要なノードを見つけるために O(N) の時間がかかります。したがって、メインアルゴリズムも O(N*M) の時間がかかると仮定すれば、ここで N はノードの数、M は平均の隣接ノード数ですが、全体的な複雑さはほぼ立方になる可能性があります。これにより、大規模なグラフでは著しいパフォーマンスの低下が発生します。

このサンプルは、4つのアルゴリズムが基本的には異なるものではないという全体的なアイデアを把握するのに役立ちますが、詳細には悪魔が潜んでいます。効率的な方法でこれらの4つのアルゴリズムを実装するためには、普遍的なデータ構造を使用することは難しいです。

最適なパフォーマンス（通常は主な関心事）のためには、最適化にもっと力を注ぐべきです。たとえば、ダイクストラとA-Starのアルゴリズムの両方に配列の代わりに優先キューを使用することは非常に合理的です。

A-Star アルゴリズムの最適化について話すなら、いくつかのリンクを紹介することは非常に合理的です：Lucho Suayaによる「A*の最適化と改善」、Steve Rabinによる「JPS+：A*より100倍速い」。

最後の言葉

この記事の目的は、すべてのトラバースアルゴリズムがどれだけ関連しているかを示すことでした。ただし、この記事で使用されたグラフの例は、これらのアルゴリズムのパフォーマンスの実際の違いを示すにはあまりにも単純すぎます。したがって、これらの例は、主に概念的な理解を得るために使用し、実際のプロダクション目的では使用しないでください。

これらのアルゴリズムの潜在能力を探求することに興味がある場合は、私の別のプロジェクトに基づいた次の記事をお読みください。このプロジェクトでは、これらのアルゴリズムを効率的に実装し、さまざまなテストデータを使用した視覚的なアプローチを採用しています。

お楽しみに！

We will continue to update VoAGI; if you have any questions or suggestions, please contact us!